[Solved]: Deterministic Turing Machine with infine tape in both directions

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

 Download Related Notes/Documents