[Overview] [Previous] [Next]

Programming a Turing Machine

Important!Just as the productions are the "heart" of a grammar, in that most of the other components can be figured out by looking at the productions, the transitions are the heart of a Turing machine. These transitions are often given as a table or list of 5-tuples, where each tuple has the form

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

Creating such a list is often spoken of as "programming" a Turing machine.

A Turing machine is often defined to start with the read head positioned over the first (leftmost) input symbol. This isn't really necessary, because if the Turing machine starts anywhere on the nonblank portion of the tape, it's simple to get to the first input symbol. For the input alphabet sigma = {a, b}, the following program fragment does the trick, then goes to state q1.

    (q0, a, a, L, q0)
    (q0, b, b, L, q0)
    (q0, #, #, R, q1)

Copyright 1996 by David Matuszek
Last modified Mar 25, 1996