0
$\begingroup$

I have the following Turing machine: A 2R-3L-TM is similar to a standard TM with the change in which the head can only move either 3 cells to the left or 2 cells to the right (those are the only possible moves). and I want to prove equivalence between 2R-3L-TM and standard TMs (one tape and the head can move single cell right or left only). I only want to prove one side, meaning that for every standard TM M_1, there is a $2R-3L-TM, M_2, s.t L\left(M_1\right)=L(M_2)$. I started the proof on the right side but not sure how to prove the triple left side, my proof so far:

Let M2, a TM with 2R-3L, a set of states Q and transition function \delta. Let us define an equal standard machine, M2. We would do so by describing how TM M1 works in the implementation level:

  1. If M1 moves to the right, do the same for M2 however mark the position with ‘ * ‘ transition to a new state at which the machine always moves to the right and then transitions to the original target of the RR transition
  2. If M1 moves to the left...

How can I continue my proof and is my proof for the right side correct?

$\endgroup$
5
  • $\begingroup$ There seems to be no question here... $\endgroup$
    – Steven
    Nov 10 '20 at 16:55
  • 2
    $\begingroup$ You can simulate a "right" movement with the movements: right, right, left. You can simulate a "left" movement with the movements: left, right. You can simulate a "stay" movement with the movements (if needed) with the movements: right, right, right, left, left. $\endgroup$
    – Steven
    Nov 10 '20 at 17:01
  • $\begingroup$ So basically: If M1 moves to the left, M2 moves 2 lefts however mark the position with ‘ * ‘ transition to a new state at which the machine always moves to the left and then transitions to the original target of the LLL transition and that is the only change? $\endgroup$
    – Rika
    Nov 10 '20 at 17:48
  • $\begingroup$ @Steven: on a half-way tape that extends only to the right, the moves "left, right" might fall off the tape. So I think it's safer to simulate a "left" with "right, left". $\endgroup$ Aug 8 at 9:37
  • $\begingroup$ There is no marking of positions, you use new auxiliary states to make sure the machine does the correct sequence of moves. For example, if there is a state $S$ in which the machine wants to move left and transition to state $T$, you insert one new auxiliary state $S_1$ and modify the machine thus: in $S$ move right and transition to $S_1$, in $S_1$ move left and transition to $T$. (Depending on the details of your Turing machines, you might have to insert $S_{1,a}$ for every possible symbol $a$.) $\endgroup$ Aug 8 at 9:40
0
$\begingroup$

The main idea behind your proof is correct.

Note that (assuming the tape is infinitely sized on the right only) in the operator algebra of tape movements on the right-infinite tape we have identy $xR^kyL^kz = xyz$.

Using that we can prove: $$R = R^4L^3 = (R^2)^2L^3$$ $$L = R^2L^3 $$

And since the right hand side consists only of unit moves in your model, you can do the effective moves on the left hand side. And you already know how, you replace every transition $T(x, S_i) = (y, S_o, m)$ where $m \in \{L,R\}$ with series

\begin{align} &&T(x, S_i) &= (y, s_1(m), m'_1(m))\\ &\forall z\in \Sigma :\quad &T(z, s_1(m)) &= (z, s_2(m), m'_2(m))\\ &&&\cdots\\ &\forall z\in \Sigma :\quad &T(z, s_{k-1}(m)) &= (z, S_o, m'_k(m)) \end{align}

where $s_i$ are new temporary states and $m'_i$ are the appropriate series of moves from $\{R^2, L^3\}$.

$\endgroup$
2
  • $\begingroup$ If I understand you correctly, this is what is should write instead of my 1&2? $\endgroup$
    – Rika
    Nov 11 '20 at 10:31
  • $\begingroup$ If you copy this answer to your homework solution, the professor will know. $\endgroup$ Aug 8 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.