Prove multiple cell move instructions don't increase power of Turing Machines

Question

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

Answer 1

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.