[Solved]: Does stay put TM recognizes same languages as standard TM

Problem Detail: I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or symbols). I am trying to figure that out.. But so far, no luck. I think the key here is “recognizes” rather than “decides”? How do i prove this? Thanks

Asked By : Fraz

Answered By : Yuval Filmus

No, the key terms are not “recognizes” and “decides”, but rather “simulates”. Given a Turing machine that can stay put, you can simulate it using a Turing machine that doesn’t stay put. Given a transition of the form:

  • On state $s_1$, if the symbol under the head is $alpha_1$ then change it to $alpha_2$, stay put and transition to state $s_2$

you replace it with a pair of transitions

  • On state $s_1$, if the symbol under the head is $alpha_1$ then change it to $alpha_2$, move right and transition to $s’$
  • For every symbol $beta$: On state $s’$, if the symbol under the head is $beta$ then change it to $beta$, move left and transition to state $s_2$

Here $s’$ is a new state that is used only to handle this transition. The new Turing machine doesn’t stay put but simulates the original Turing machine. As the OP points out, we can actually improve this simulation by not adding new states at all (except for possibly one more state, a “stuck” state). Suppose we are at state $s_1$, see the symbol $alpha_1$, and stay put. Let us continue to follow the machine. Either the machine never moves away from its spot, or it eventually moves either left or right, transitioning to state $s_2$ after changing the original symbol to $alpha_2$. In the latter case, we can change the transition to a simple transition to $s_2$. In the former case, we can move instead to a special “stuck” state in which the Turing machine finds itself in an infinite loop; this state can be common for all “stuck” situations. If we are guaranteed that the original Turing machine never gets stuck, and this is probably the assumption in your textbook, then we can do away with the “stuck” state, so that no new states are needed at all.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37297  Ask a Question  Download Related Notes/Documents