Turing Machine Instructions


Five Components:

        (current state, current symbol, next state, next symbol, direction)

Meaning:

The instruction**


(S1, C1, S2, C2, D)

means

if currently in state S1 and currently reading symbol C1
   then

        change to state S2

        write symbol
C2
        move the tape one cell in direction
D

 

 





CAVEAT EMPTOR
The textbook uses a very non-standard ordering of the elements of the instructions in a Turing machine, namely
(current state, current symbol, next symbol, next state, head movement)
.

We will be using the sequence
(current state, current symbol, next state, next symbol, tape movement)
as does the emulator provided and most other textbooks. Moreover in examinations and quizzes we will always explicitly provide a description of the order of these instruction elements. NOTE that the exercises in the textbook DO NOT provide this information.

The meaning of the "movement" portion of each instruction is also confusing. We will always deal with the movement of the TAPE, not the movement of the HEAD. However in the diagrams it will appear that the head moves in the opposite direction. This is a prime example of "relative motion"!


CS1104 Main Page
Last Updated 11/10/2000
© L.Heath, 2000, modified by J.A.N. Lee.