1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is $\{a,b,c,u\}$ the input alphabet? In that case the blank symbol shouldn't be there because by definition. (At least if it is "another" blank, different from the blank symbol of the tape alphabet) $\endgroup$ – Alejandro Sazo Jun 1 '13 at 20:27
  • 1
    $\begingroup$ no, not different i guess blank symbol has confused you, {a, b, c} is an input alphabet, editted $\endgroup$ – Kudayar Pirimbaev Jun 1 '13 at 20:30
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.