Turing machine modification -- allowing n steps left or right

Question

Prove that the class of computable functions does not change if we consider Turing machines that in each computation step can move $n$ steps left/right for any integer $n$.

I guess the solution is to memorize the number of steps as different states of the head, but the problem is the set of different states should be finite.

Answer 1

You have the exact right idea. I will be slightly relaxed in my description here, because working through the gory details of these kinds of problems is not worth as much as knowing intuitively how to solve the problem.

First, it is clear that multi-step turing machines can compute everything that a classical turing machine can compute. Simply ignore the bonus power, and always move left/right by one step.

Now we want to show that anything a multi-step turing machine can compute can already be computed by a classical turing machine. To do this, we will take a description of a multi-step turing machine, and we will convert it into a classical turing machine that does the same computation. First, the intuition:

We're going to add a bunch of extra states which move left/right and copy their input character. This way, anytime the multi-step turing machine would immediately jump $n$ places, we can imitate that behavior by moving to a chain of $n$ dummy states that leave everything unchanged, but move $1$ step each. Then the last state in this chain transitions to the state the the multi-step turing machine would have jumped to.

Ok, now let's do this a bit more formally:

We look at the multi-step transition function $\delta$ which takes a state and an input letter, and gives a new letter and a number of steps left/right to move. Then there are $\# \{ \text{states} \} \times \# \{ \text{letters in alphabet} \}$ possible things $\delta$ can do. Importantly, this is a finite number of things.

So for every pair $(q,a)$ with $q$ a state and $a$ a letter, if $\delta(q,a)$ says to move $n$ places to the left, we add $n-1$ states $(q,a,i)$ for $1 \leq i < n$ all of which ignore their input and:

• leave the tape unchanged
• move one step to the left
• $(q,a,i)$ transitions to $(q,a,i+1)$, and $(q,a,n-1)$ transitions to $q'$, the state that $(q,a)$ would have transitioned to in the original multi-step turing machine.

As I said, the details of verifying that this turing machine does what we say it does are rather tedious, but hopefully it is intuitively clear what's happening. Moreover, this description is concrete enough that checking that it actually does what it's supposed to is more annoying than it is difficult.

---

I hope this helps ^_^