# Turing Machine states

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!

• 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.
– Raphael
Jan 22, 2014 at 9:30