Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How can you prove that multiple-cell-move instructions, for example (X, Y, 5R) and (X, Y, 17L), do not increase the power of a Turing Machine?

share|cite|improve this question
up vote 9 down vote accepted

A quick answer: the control of every TM is finite, so given a TM $M$, the jumps in its transition table are finite. Suppose that it has the following jump transition:

on state_x: if read symbol a -> write b, jump 3R, goto state_y

then you can simulate it using 3 single step transitions :

on state_x: if read symbol a  -> write b, move R, goto state_x2
on state_x2: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_x3
on state_x3: if read symbol <anysymbol> -> write <anysymbol>, move R, goto state_y

In general if $len$ is the length of the jump of a transition, you can simulate it adding $len-1$ new states to $M$ and the new states are used simply to move the head for $len-1$ more steps and finally enter the same target state of the original jump transition.

To be pedantic, you need to add additional states only for distinct triples (jump length, jump direction, target state). For example if a transition has (jump 5, right, and goto state z) the added single step states can be reused on every transition with the same value of jump length, jump direction and target state.

share|cite|improve this answer
ahh ok, cheers! – user3115 Nov 16 '12 at 23:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.