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.

Copyright © 1996 by David Matuszek

Last modified Mar 23, 1996