# Proving equivalence of two Turing machines

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?

• 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. Commented Nov 10, 2020 at 17:01
• 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?
– Rika
Commented Nov 10, 2020 at 17:48
• @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". Commented Aug 8, 2021 at 9:37
• 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$.) Commented Aug 8, 2021 at 9:40

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\}$$.

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