Turing Machine Instructions

Five Components:

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


The instruction**

(S1, C1, S2, C2, D)


if currently in state S1 and currently reading symbol C1

        change to state S2

        write symbol
        move the tape one cell in direction



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.