When defining a Turing Machine formally, you enumerate its states. But I don't understand what states a TM can be in. Reading, Writing, and moving the head are the only ones that come to mind.

Specifically, the turing I am trying to describe behaves like this:

    WHILE the symbol under the FH head is not $ DO
        IF this symbol is not marked 0 THEN write it on the tape
        ELSE write the symbol 1 on the tape
            Read the next symbol (which is a 0) and write a marked 0 on the tape
    Write $ on the tape

Where FH is the reading head which begins on the far left of the tape, and BH is the writing head which begins on the blank space after the last symbol on the tape. Once a cell is read or written into, the head in question moves one cell to the right.

The starting configuration for the TM is this: 100!0110\$ where the 0! indicates that the 0 is a marked symbol. The FH head begins on the first 1, and the BH head begins on the blank cell after the \$. The ending configuration for that TM with that input is then 100!0110\$1010!110\$

So, when describing this TM, what would its states be? Thanks!

  • 4
    $\begingroup$ Have you read any introduction to TMs? WHILE-programs is not how you "program" them; you have a state transition diagram. Given such a thing, it's obvious what states are. What you are asking is for someone to compile your WHILE-program to a transition table. $\endgroup$
    – Raphael
    Commented Jan 22, 2014 at 9:30

1 Answer 1


Raphael is correct in stating the states of a TM is a theoretical construct defining the operating program. What you are thinking of ("reading", "writing", and "moving") are operations the machine can do out of a particular state.

Wikipedia has a nice little write up about it. Explaining that each state, tells the machine what next operation to perform based off of a current state.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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