Variants and Universal Turing Machines
Robustness, enumeration, simulation, and encoding
Why study Turing-machine variants?
The standard one-tape deterministic Turing machine is intentionally austere. It is natural to ask whether additional features allow us to compute fundamentally more.
Examples include:
- extra finite storage;
- multiple tracks on one tape;
- a tape infinite in both directions;
- multiple tapes and tape heads;
- nondeterministic choices;
- multidimensional tapes; and
- several heads scanning one tape.
For each variant, the proof strategy is the same:
Show that an ordinary Turing machine can simulate every step of the enhanced machine.
If such a simulation exists, the variant recognizes and decides exactly the same languages as the standard model.
These features can make algorithms much easier to describe and may change running time dramatically. They do not change computability.
The phrase “nothing can beat a Turing machine” should be interpreted as a claim about which functions are computable—not about speed. Alternative models can be substantially more efficient, and the equivalence proofs themselves may introduce computational overhead.
Finite storage
Suppose a machine has a finite register or finite control memory in addition to its ordinary state. Because the register has only finitely many possible contents, combine the machine’s state with the register value:
\[ Q'=Q\times R, \]
where \(R\) is the finite set of register configurations.
The additional memory is absorbed into the finite control, so it adds no computational power.
Multiple tracks
A multitrack tape treats each cell as containing several aligned components. For example, a two-track cell might contain
\[ (a,X), \]
where the first track stores an input symbol and the second stores a marker.
An ordinary one-track TM simulates this by using a product tape alphabet:
\[ \Gamma'=\Gamma_1\times\Gamma_2\times\cdots\times\Gamma_k. \]
One compound symbol stores all track values for a cell.
A tape infinite in both directions
A standard semi-infinite tape can simulate a tape extending infinitely left and right.
One encoding interleaves the two sides:
0, 1, -1, 2, -2, 3, -3, ...Another uses two tracks, with one representing nonnegative positions and the other representing negative positions. The simulator translates each virtual left or right move into movement within the encoding.
Thus, two-way infinitude changes convenience but not computability.
Multitape Turing machines
A \(k\)-tape TM has \(k\) tapes and \(k\) independently positioned heads. One transition reads all scanned symbols, writes on each tape, moves each head, and changes state.
A one-tape TM can simulate it by storing all virtual tapes on one physical tape, separated by delimiters. Marked symbols record the locations of the virtual heads.
To simulate one multitape step, the one-tape machine:
- sweeps across the encoding to discover the symbols under all virtual heads;
- stores this finite tuple in its state;
- sweeps again to update symbols and head markers; and
- expands the encoded region if a virtual tape moves into a previously unused cell.
The simulation is slower because one virtual step may require several complete tape sweeps, but it computes the same result.
Multihead and multidimensional tapes
Multiple heads can be simulated by marking each virtual head position on one tape. A multidimensional tape can be encoded as a one-dimensional sequence of coordinates and contents.
The bookkeeping may be elaborate, but every finite local operation can be represented by an ordinary TM. Again, these variants alter efficiency and notation rather than computability.
Nondeterministic Turing machines
A nondeterministic Turing machine may permit several transitions from one state-symbol pair. Its computation on an input forms a tree:
- the root is the initial configuration;
- each child is a possible next configuration; and
- the machine accepts if at least one branch reaches an accepting configuration.
The central question is whether a deterministic TM can find an accepting branch whenever one exists.
Why breadth-first search is essential
A depth-first simulation can become trapped forever on one infinite branch even though another branch accepts after only a few steps.
Breadth-first search avoids this problem by exploring the tree level by level:
- examine all branches of length zero;
- then all branches of length one;
- then all branches of length two; and
- continue until an accepting branch is discovered.
Because the transition relation has finite branching, every finite accepting path is eventually examined.
A multitape description of the simulator might use:
- Tape 1 for the original input;
- Tape 2 for the simulated branch’s working tape; and
- Tape 3 for a finite sequence encoding nondeterministic transition choices.
The simulator enumerates choice sequences in length-first order, such as
ε, 1, 2, 3, 11, 12, 13, 21, 22, 23, ...For each sequence, it resets the simulated tape and follows the prescribed choices. If one simulation accepts, the deterministic simulator accepts.
Therefore,
\[ \mathcal{L}(\mathrm{NTM}) = \mathcal{L}(\mathrm{DTM}) \]
for recognizability and decidability.
Nondeterminism changes complexity—it motivates classes such as \(NP\)—but not computability.
Enumerators
Turing machines as language generators
An enumerator is a Turing machine equipped with an output device. It runs without input and prints strings, usually separated by a marker such as #.
The language enumerated by \(E\) is
\[ L(E)=\{w:E\text{ eventually prints }w\}. \]
An enumerator may:
- run forever;
- print the same string more than once;
- print strings in any order; and
- pause for arbitrarily long periods between outputs.
If desired, additional bookkeeping can suppress duplicates or sort outputs by length and lexicographic order.
Example: enumerating \(\{0^n1^n:n\ge0\}\)
An enumerator can maintain a counter \(n\) and repeatedly:
- print \(n\) copies of
0; - print \(n\) copies of
1; - print a separator
#; - increment \(n\); and
- repeat forever.
Its output begins
#01#0011#000111#...where the first empty field represents \(\varepsilon\).
The same idea can enumerate positive integers, prime numbers, syntactically valid programs, proofs in a formal system, or any other effectively generable set.
Recognizers and enumerators are equivalent
Theorem. A language is Turing-recognizable if and only if some enumerator enumerates it.
This is why Turing-recognizable languages have historically been called recursively enumerable languages.
From an enumerator to a recognizer
Given an enumerator \(E\) for \(L\), build a recognizer \(M\):
- on input \(w\), run \(E\);
- compare every printed string with \(w\); and
- accept if \(E\) prints \(w\).
If \(w\in L\), it is eventually printed and accepted. If \(w\notin L\), the recognizer runs forever.
From a recognizer to an enumerator
Given a recognizer \(M\) for \(L\), list all strings
\[ s_1,s_2,s_3,\ldots \]
and dovetail the simulations:
- run \(M\) for one step on \(s_1\);
- run \(M\) for two steps on each of \(s_1,s_2\);
- run \(M\) for three steps on each of \(s_1,s_2,s_3\);
- continue this diagonal schedule; and
- print a string whenever its simulation accepts.
Running \(M\) to completion on one string before trying the next would fail because a nonmember might cause \(M\) to loop forever. Dovetailing gives every simulation continuing attention.
Decidable languages can be enumerated in order
If \(L\) is decidable, enumerate every string in standard length-lexicographic order and run the decider on each. Print precisely those it accepts.
Because the decider always halts, the outputs appear in the same order. Conversely, if a language can be enumerated in standard order, that ordering can often be used to decide membership: wait until the target appears or until the enumerator passes the point where it could appear.
The Universal Turing Machine
Machines as data
A Turing machine has a finite description:
- a finite set of states;
- finite input and tape alphabets;
- a finite transition table; and
- designated start, accept, and reject states.
We can encode this description as a string, written
\[ \langle M\rangle. \]
The pair consisting of a machine and an input is encoded as
\[ \langle M,w\rangle. \]
Once a machine can be represented as data, another machine can interpret and simulate it.
Definition of a universal machine
A universal Turing machine \(U\) takes \(\langle M,w\rangle\) as input and simulates machine \(M\) running on input \(w\).
Its behavior mirrors the simulated machine:
- if \(M\) accepts \(w\), then \(U\) accepts \(\langle M,w\rangle\);
- if \(M\) rejects \(w\), then \(U\) rejects \(\langle M,w\rangle\); and
- if \(M\) loops on \(w\), then \(U\) also loops.
A convenient multitape implementation uses:
- Tape 1 for the encoded transition table of \(M\);
- Tape 2 for \(M\)’s simulated tape; and
- Tape 3 for \(M\)’s current state.
For each simulated step, \(U\) finds the applicable encoded transition, updates the simulated tape and head, and records the new state.
Why universality resembles a modern computer
The universal machine separates a fixed interpreter from a variable encoded program. This is the essential idea behind a stored-program computer:
- instructions and data can both be represented in memory;
- one general-purpose machine can execute many different programs; and
- changing the computation does not require rebuilding the hardware.
A multitape TM can similarly simulate a conventional computer by using tapes for:
- encoded instruction and data memory;
- the current instruction address;
- an operand address; and
- temporary workspace.
The universal TM is a conceptual ancestor of interpreters, virtual machines, emulators, and general-purpose programmable computers.
Encoding Problems as Languages
Why encoding matters
A Turing machine receives a string, but many computational problems concern structured objects:
- graphs;
- trees;
- automata;
- grammars;
- equations; or
- polynomials.
To process such an object, choose a finite representation. We write \(\langle X\rangle\) for the encoding of object \(X\).
A decision problem then becomes a language. For graph connectedness:
\[ CONNECTED = \{\langle G\rangle:G\text{ is a connected graph}\}. \]
A decider accepts valid encodings with the property and rejects valid encodings without it. The algorithm should also specify what happens on malformed encodings—usually reject.
Example encodings
Graph
Number the vertices and encode an adjacency matrix or edge list, together with delimiters separating fields.
Binary tree
Use a recursive preorder encoding with a special marker for an empty child, or number nodes and list their child relationships.
Finite automaton
Encode the state set, alphabet, transition table, start state, and accepting states.
Context-free grammar
Encode variables, terminals, the start variable, and each production with separators.
Polynomial
Encode each coefficient and exponent in a fixed positional or delimited format.
The exact format is usually less important than three properties:
- every valid object has a finite encoding;
- the encoding can be parsed effectively; and
- the represented operations can be performed algorithmically.
Reasonable encodings generally change running time only by polynomial factors and do not change decidability.
Describing Algorithms with Turing Machines
Algorithms and deciders
An algorithm is a finite, unambiguous procedure that halts on every valid input and produces the required result.
In the TM model, an algorithm corresponds to a decider. If a decider exists for a decision problem, the problem is decidable.
A recognizer that may loop on negative instances captures partial computational information but is not a terminating decision algorithm.
Three levels of description
A Turing machine can be specified at several levels.
Formal description
List every transition in \(\delta\). This is precise but becomes unreadable for large machines.
Implementation-level description
Describe how the head moves and how the tape is used, often in state-oriented pseudocode.
High-level description
Give an algorithm resembling ordinary pseudocode. It must still:
- define the input encoding;
- specify the major computational steps;
- state when to accept and reject; and
- make clear why every branch halts.
For decidability proofs, a clear high-level description is usually preferable to hundreds of low-level transitions.
High-level example: graph connectedness
Input: an encoded undirected graph \(\langle G\rangle\).
- Verify that the input is a valid graph encoding; reject otherwise.
- Mark one vertex.
- Repeatedly mark every unmarked vertex adjacent to a marked vertex.
- When a complete pass adds no new marks, accept if every vertex is marked; otherwise reject.
The procedure halts because each productive pass marks at least one previously unmarked vertex and the graph has finitely many vertices.
High-level example: primality
Input: a positive integer \(n\).
- Reject malformed inputs and values below two.
- For each integer \(d\) from \(2\) through \(\lfloor\sqrt n\rfloor\), test whether \(d\) divides \(n\).
- Reject if a divisor is found.
- Accept otherwise.
This need not be the fastest primality algorithm to establish decidability. The loop has a finite bound, so it always halts.
High-level example: DFA acceptance
Define
\[ A_{DFA} = \{\langle B,w\rangle:B\text{ is a DFA that accepts }w\}. \]
A decider:
- checks that \(\langle B,w\rangle\) is a valid encoding;
- simulates \(B\) on \(w\) one symbol at a time; and
- accepts if the final state is accepting, otherwise rejects.
The simulation always halts after exactly \(|w|\) DFA transitions.
This style—encode a machine and input, simulate the machine, then inspect the outcome—will recur throughout decidability theory.
Summary
Turing machines can be used to:
- recognize languages;
- decide languages;
- compute partial and total functions;
- implement reusable computational subroutines;
- enumerate sets;
- encode structured mathematical objects; and
- simulate other machines, including encoded Turing machines.
Two distinctions remain central:
- A decider halts on every input.
- A recognizer may run forever on inputs outside its language.
Machine variants make algorithms easier to express, but standard simulation arguments show that they do not expand the class of computable problems.
Check your understanding
- Why does a multitrack tape add no computational power?
- Why can depth-first search fail when simulating an NTM?
- What does dovetailing accomplish in the recognizer-to-enumerator proof?
- Why are Turing-recognizable languages called recursively enumerable?
- What does \(\langle M,w\rangle\) represent?
- How does a universal TM resemble a stored-program computer?
- Why must a high-level decidability proof explain termination?
- Which aspects of a Turing-machine variant may change even when computability does not?