Problem Detail: Consider a deterministic Turing Machine $D$ which has an infinite tape in both directions. We don’t have exact information about it; what we know is that its alphabet is ${a, b, c}$ and there are at least three states $q_1, q_s, q_f$ where $q_s$ is the start state, $q_f$ is the final state. At some step of the computation, all the tape is blank except one cell containing the symbol $a$, the state is $q_1$ and the head is currently at a blank cell. I need to write states and transitions that will guarantee to enter to final state from state $q_1$ but I have difficulties since $D$ is both deterministic and with infinite tape in both directions.
Asked By : Kudayar Pirimbaev
Answered By : Denis
You can design a Turing Machine that goes one step left, then two right, then 3 left and so on… You don’t need too much states for that: just put two markers on the tape: $b$ for the current left boundary and $c$ for the current right boundary of what you explored, and push them back from one cell each time you reach them. You have one state $q_b$ going left until $b$ is reached, and one state $q_c$ going to the right until $c$ is reached. Plus special states to shift them by one position. You will eventually find the $a$ letter, at which point you just go to $q_f$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12415 3.2K people like this
