[Overview] [Previous] [Next]

Variations on Turing Machines II

A Turing machine may have a semi-infinite tape; the nonblank input is at the extreme left end of the tape.

Theorem. Turing machines with semi-infinite tape are equivalent to standard Turing machines.


An off-line Turing machine has two tapes. One tape is read-only and contains the input; the other is read-write and is initially blank.

Theorem. Off-line Turing machines are equivalent to standard Turing machines.


A multitape Turing machine has a finite number of tapes, each with it's own independently controlled tape head.

Theorem. Multitape Turing machines are equivalent to standard Turing machines.


A nondeterministic Turing machine is one in which the dfa controlling the tape is replaced with an nfa.

Theorem. Nondeterministic Turing machines are equivalent to standard Turing machines.


Copyright © 1996 by David Matuszek
Last modified Mar 27, 1996