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
Does stay put TM recognizes same languages as standard TM
computability;turing machines;undecidability;turing completeness
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 transitionsOn 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.