Suppose that we have a Turing Machine that can only move for multiples of n cells at a time. In other words it can jump from one cell to another with jumping $n, 2n, 3n$, and so on with a single move. Is this machine equivalent to a standard Turing machine? I assume it could be equal since we can model it with a multi tape Turing machine and the equivalence between multi tape Turing machine and single tape Turing machine. We would assume that we have n tapes for each possible remainders of dividing by $n : 0, 1, 2, ..., n-2$, and $n-1$. Then we place these tapes on top of each other to have the equivalent cells on each tape in similar columns. then we can move from any possible cell to another one. For example if we $n = 3$ and we want to go from $0$ to $1$ we make three tapes : one for $(k = 0 \mod 3)$, one for $(k = 1 \mod 3)$, and another one for $(k = 2 \mod 3)$. so in the first tape we have the cells of the original string on cells $0, 3, 6$, and so on and so forth. the same applies for the other tapes. If we want to move from $0$ to $1$, we go from $0$ to $3$, then move to the tap $k = 1 ( mod 3)$ and go back a $3$ steps on this tape from $4$ to $1$. so we reach $1$ from $0$. It is noteworthy to say that on the tapes created we have $k$ distance between cells so we can jump.
1 Answer
$\begingroup$
$\endgroup$
2
If a TM can only move $n$ spots at a time then $n-1$ spots on the tape may as well not exist.
If you can't touch those spots on the tape then you don't need consider them at all.
At that point the amount of tape moved becomes a detail of the implementation. Whether it's $1$ unit or $n$ per step as long as the distance each time is constant and you can perfectly revisit previous locations on the tape.
-
$\begingroup$ So in other words, it is equivalent to a standard Turing machine, right? $\endgroup$ Commented 9 hours ago
-
$\begingroup$ yeah, there's functionally no difference other than how you fill the initial state of the tape $\endgroup$ Commented 8 hours ago