Asked By : Fraz
Answered By : Yuval Filmus
- 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