Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Proving equivelance of a multijump turing machine and a turing machine

, ,
Problem Detail:

I'm having trouble getting started on this proof, and I was hoping you guys could give me a couple hints/point me in the direction of where to start? Here's the problem:

Consider a multijump Turing machine, which is like an ordinary Turing machine except the transition function is δ : Q × Γ → Q × Γ × {LL, L, R, RR} In other words, the multijump TM can move left or right either one or two times. Show that a language can be recognized by a multijump TM if and only if it can be recognized by a TM.

I'm trying to answer it formally in terms of the 7-tuple and show that the TM and multijump TM are equivelant, but I'm having trouble getting started on that.

Any and all tips are appreciated, thanks

#### Answered By : Yuval Filmus

The basic idea is to simulate every LL and RR move using an extra state. Whenever the machine wants to move twice to the right, instead make it move once to the right, and transition to a new state, at which the machine always moves to the right and then transitions to the original target of the RR transition. Implementing this idea using the 7-tuple representation is a routine but tedious exercise.