When defining a Turing Machine formally, you enumerate its states. But I don\'t

Question

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!

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.