**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