I have this Turing machine example given in my book:

enter image description here

For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine.

But what I want to know is the following:

enter image description here

What is the $|-$ symbol is for what are the states $q_0$, $q_1$ doing in middle of everything. Unfortunately my textbook doesn't explain any of it.

  • 2
    $\begingroup$ Look up "configuration" in your textbook. We can guess at what your textbook means by these things but, if it doesn't explain the basic notation it uses, it's an extremely bad textbook. $\endgroup$ – David Richerby Apr 1 '16 at 20:00

The state marks the position of the head (as well as the current state): for example, in $q_00011$, the head is to the left of $0011$, and in $xq_1011$, it is to the left of $011$.

The notation $\sigma \vdash \tau$ means that the configuration $\sigma$ leads, after one step of the Turing machine, to the configuration $\tau$.

As David Richerby mentions in his comment, all of this is explained in your textbook at some point.


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.