[Overview] [Previous] [Next]

Variations on Turing Machines III

A multidimensional Turing machine has a multidimensional "tape;" for example, a two-dimensional Turing machine would read and write on an infinite plane divided into squares, like a checkerboard. Possible directions that the tape head could move might be labeled {N, E, S, W}. A three-dimensional Turing machine might have possible directions {N, E, S, W, U, D}, and so on.

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.