[Overview] [Previous] [Next]

Informal Definition of Turing Machines

A Turing machine is a lot like a pushdown automaton. Both have a finite-state machine as a central component; both have additional storage. But where a pushdown automaton uses a stack for storage, a Turing machine uses a tape, which is considered to be infinite in both directions. The tape consists of a series of squares, each of which can hold a single symbol. The tape head, or read-write head, can read a symbol from the tape, write a symbol to the tape, and move one square in either direction.

Turing machines can be deterministic or nondeterministic. We will consider only deterministic machines.

Unlike the other automata we have discussed, a Turing machine does not read "input." Instead, there may be (and usually are) symbols on the tape before the Turing machine begins; the Turing machine might read some, all, or none of these symbols. The initial tape may, if desired, be thought of as "input."

We have defined acceptors, which produce only a binary (accept/reject) output, and transducers, which can produce more complicated results. However, all our work so far has been with acceptors. A Turing machine also accepts or rejects its input. More importantly, the results left on the tape when the Turing machine finishes can be regarded as the "output" of the computation; thus, a Turing machine is a transducer.