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

  • 1
    $\begingroup$ What have you tried and where, specifically, did you get stuck? Have you read similar simulation proofs, e.g. for multi-tape vs single-tape or one-sided-infinite tape vs double-sided-infinte tape? $\endgroup$ – Raphael Nov 6 '14 at 15:26

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.