A Triple Jump Turing machine, denoted Ti,j,k is similar to an ordinary Turing ma

Question

A Triple Jump Turing machine, denoted Ti,j,k is similar to an ordinary Turing machine, except that in addition to the ability to move left and right, this machine can jump to i th, jth , and k th positions of the tape as well. For example, the M5,7,17 can move left one cell, move right one cell, jump to the 5th cell on the tape, jump to the 7th cell on the tape, or jump to the 17th cell on the tape. Is this Turing machine variant equivalent to the standard Turing machine? Namely, can any language recognized by one be recognized by the other? Prove your answer.

Explanation / Answer

These two models of Turing Machine are equivalent.

Let us call oridnary Turing Machine as T1 and triple jump turing machine as T2.

To show that both turing machines T1 and T2 are equivalent, we have to show that extra steps which can be performed by T2 can also be performed by T1.

A jump at ith cell can be simulated by one or more left/right jump depending upon the current cell of TM T1. As all moves of TM T2 can also be performed by T1 both TM's are equivalent.

As far as acceptability of any input string is concerned, TM T2 is non deterministic, as it can have multiple transition from current state, this can be simulated by TM T1 in breadth first search way, by trying all possible ways until one way accept or TM exhaust all possbile moves in that case TM does not accept the input string.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.