The standard definition of a Turing machine has one tape, one head and deterministic behaviour. One may ask whether these choices limit the model. The answer is no: many apparently more powerful variants recognize exactly the same languages. Proving this is useful for two reasons. First, it confirms that the notion of computability does not depend on technical details. Second, it lets us use whichever variant is most convenient in each proof.
The general pattern: simulate
To show that a variant V is no more powerful than the basic model B, it suffices to prove that every machine of type V can be simulated by a machine of type B. Simulating means that B, on the same input, accepts, rejects or runs forever exactly as V does. The converse is usually trivial, because the basic model is a special case of the variant.
Tape infinite in both directions
In the basic definition the tape has a left end. A variant allows a tape that is infinite both to the left and to the right.
Simulation: "fold" the two-way tape onto the one-way tape. Cells with index 0, 1, 2, … go to the even positions, those with index −1, −2, … to the odd positions. One extra bit of state remembers which half the head is on, and each move becomes a two-cell jump in the appropriate direction. Alternatively, use tracks: the tape alphabet contains pairs of symbols, one per half.
Multitape machines
A k-tape machine has k independent heads; a transition reads k symbols, writes k and moves each head.
Simulation with a single tape:
- Write the contents of the k tapes one after another, separated by a # symbol.
- Mark each head's position with a "dotted" version of the symbol under it (for example, 0̇ instead of 0).
- To simulate one step, the machine scans the whole tape to read the k dotted symbols, then scans it again to update them and move the dots.
- If a head must move beyond the end of its section, shift all later contents one cell to the right to make room.
Cost: if the multitape machine takes t steps, each tape holds at most O(t) symbols, so simulating one step takes O(t) steps and the whole simulation O(t²). The slowdown is polynomial (quadratic): this is why the class P is the same with one tape or many.
Nondeterministic machines
In a nondeterministic machine δ returns a set of possible moves. The computation is a tree: each node is a configuration, its children are the configurations reachable in one step. The machine accepts if some branch reaches the accept state.
Deterministic simulation: explore the tree breadth-first. Not depth-first, because an infinite branch would stall the search and an accepting branch elsewhere would never be found.
A classic construction uses three tapes:
- the first keeps the input, never modified;
- the second is the work tape on which a single branch is simulated;
- the third holds an "address", a sequence of choices (for example 2, 1, 3) identifying a node of the tree.
For each address, in order of increasing length, copy the input to the work tape and simulate the branch following the given choices. If a branch accepts, accept.
Cost: if each configuration has at most b choices and the shortest accepting branch has length t, the simulation may take time on the order of bᵗ, that is exponential. Nobody knows whether one can do much better in general: this is, in technical form, the P vs NP question.
Enumerators
An enumerator is a Turing machine attached to a printer: it receives no input, works and from time to time prints a string. The enumerated language is the set of strings printed sooner or later, possibly with repetitions and in any order.
The theorem is:
a language is Turing-recognizable if and only if some enumerator enumerates it.
- From enumerator to recognizer: given w, run the enumerator and compare each printed string with w; if they match, accept.
- From recognizer to enumerator: you cannot simply run the recognizer on one string after another, because it might never halt on one of them. Instead use dovetailing: for i = 1, 2, 3, … run the recognizer on the first i strings, each for i steps, and print every accepted string. This way every string in the language is printed after a finite time.
This second construction is the reason behind the name "recursively enumerable".
What changes and what does not
| Variant | Languages recognized | Cost of simulation |
|---|---|---|
| Two-way tape | The same | Linear |
| k tapes | The same | Quadratic |
| Nondeterminism | The same | Exponential (with known techniques) |
| Enumerator | The same | Not applicable |
Computability is invariant; complexity is not. This distinction is the bridge between the two great parts of the theory.
In short
- To compare two models, show that each can simulate the other.
- Two-way tapes and multiple tapes add no power, costing at most a quadratic slowdown.
- Nondeterministic machines are simulated by breadth-first exploration of the computation tree, at known exponential cost.
- Enumerators characterize the Turing-recognizable languages, thanks to dovetailing.
- Variants leave computability unchanged but can change complexity.
