[Overview] [Previous] [Next]

Variations on Turing Machines I

According to our textbook, two automata are said to be equivalent if they accept the same language. I will use a somewhat more general definition: two transducers are equivalent if they compute the same function.

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.