Discuss briefly how to prove that multiple-cell move instructions, such as (x,y,

Question

Discuss briefly how to prove that multiple-cell move instructions, such as (x,y,5R) and (x,y,17L) mentioned on page 502 do not increase the power of a TM

Explanation / Answer

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 -> write , move R, goto state_x3 on state_x3: if read symbol -> write , 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

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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