A class of automata (e.g. standard Turing machines) is equivalent to another class of automata (e.g. nondeterministic Turing machines) if, for each transducer in one class, an equivalent transducer can be found in the other class.

At each move of a Turing machine, the tape head may move either
left or right.
We may augment this with a *stay option:* we will add
"don't move" to the set {L, R}.

**Theorem.** Turing machines with a stay option are equivalent
to standard Turing machines.

An *n-track Turing machine* is one in which
each square of the tape holds an ordered n-tuple
of symbols from the tape alphabet.
You can think of this as a Turing machine with
multiple tape heads,
all of which move in lock-step mode.

**Theorem.** N-track Turing machines
are equivalent to standard Turing machines.

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996