Proving equivalence of two Turing machines

Question

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?

Answer 1

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