Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

Thanks

share|improve this question

1 Answer 1

up vote 8 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|improve this answer
    
ahh ok, cheers! –  user3115 Nov 16 '12 at 23:51

Your Answer

 
discard

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