**Theorem.** Multidimensional Turing machines
are equivalent to standard Turing machines.

A *binary Turing machine* is one whose tape
alphabet consists of exactly two symbols.

**Theorem.** Binary Turing machines
are equivalent to standard Turing machines.

A *two-state Turing machine* is one that
has only two states. (It makes up for this
by having a large, albeit finite, alphabet.)

**Theorem.** Two-state Turing machines
are equivalent to standard Turing machines.

Copyright © 1996 by David Matuszek

Last modified Mar 27, 1996