An ordinary Turing machine solves a single problem: it is like a circuit designed for one fixed task. The universal Turing machine is different: it receives as input the description of another machine together with an input for it, and simulates its behaviour. In modern terms it is an interpreter. The idea that a program can be treated like any other piece of data, read and executed by another program, underlies both programmable computers and every undecidability result.
Step one: encode a machine as a string
To give a machine as input to another, we need to represent it as a string over a fixed alphabet. A Turing machine is a finite object: finitely many states, symbols and transitions. So it can be encoded.
A simple scheme over the alphabet {0, 1}:
- Number the states q₁, q₂, …, qₙ, with the convention that q₁ is the start state, q₂ the accept state and q₃ the reject state.
- Number the tape symbols a₁, a₂, …, aₘ, with a₁ the blank.
- Number the directions: D₁ left, D₂ right.
- Write each transition δ(qᵢ, aⱼ) = (qₖ, aₗ, Dₘ) as 0ⁱ 1 0ʲ 1 0ᵏ 1 0ˡ 1 0ᵐ, that is five blocks of zeros separated by a 1.
- Concatenate the transitions, separating them with 11.
The result is a binary string, written ⟨M⟩. The pair "machine and input" is written ⟨M, w⟩, for instance with a 111 separator. The specific scheme does not matter: all that counts is that it is unambiguous and mechanically decodable.
An immediate consequence: Turing machines are countable. Each machine corresponds to a finite binary string, and finite binary strings can be listed one after another. This seemingly harmless fact will be decisive in diagonal arguments.
Step two: the universal machine
The universal machine U receives ⟨M, w⟩ and behaves as follows:
U accepts ⟨M, w⟩ if M accepts w; rejects if M rejects w; runs forever if M runs forever on w.
It is convenient to describe it with three tapes, knowing they can later be reduced to one:
- program tape: holds ⟨M⟩, the transition table;
- work tape: holds M's simulated tape, initially w, with symbols encoded as blocks of zeros;
- state tape: holds the encoding of M's current state, initially q₁.
U's main loop repeats:
- read the current state on the state tape and the symbol under the simulated head on the work tape;
- search the program tape for the transition beginning with that pair;
- rewrite the symbol on the work tape, move the simulated head in the given direction and update the state tape;
- if the new state is q₂ accept, if it is q₃ reject, otherwise start again.
U is one single machine, with a fixed number of states, yet it can imitate any other machine, even one with many more states and symbols. The trick is that M's states and symbols are not U's states and symbols: they are strings written on U's tapes.
Cost of the simulation
Each step of M requires U to search the transition table and make a few moves on the tape. With a sensible encoding and several tapes, the cost per step depends on the size of ⟨M⟩ but not on the number of steps already performed. As a result U simulates t steps of M in time on the order of t times a factor tied to the size of M, or at most t log t with a careful construction. This technical detail underlies the time hierarchy theorems.
The acceptance language
The existence of U shows that the language
A_TM = {⟨M, w⟩ : M is a Turing machine that accepts w}
is Turing-recognizable: just run U. If M accepts w, U notices after finitely many steps. But if M never halts, neither does U. U recognizes A_TM but does not decide it. One can prove that no machine decides it: this is the starting point of undecidability.
Why the idea is so important
- General-purpose hardware: instead of building a machine for every problem, build one and supply the program as data. This is exactly the principle of the stored-program computer.
- Software that handles software: compilers, interpreters, emulators, virtual machines and static analyzers are all programs that read other programs as input.
- Self-reference: if a program can receive programs, it can also receive itself. This possibility is what generates the paradoxes behind the halting problem and Rice's theorem.
In my software analysis work this idea is an everyday matter: malware analysed in a sandbox, bytecode run by a virtual machine, a script evaluated by an interpreter. All are cases of one program being given to another.
In short
- Every Turing machine can be encoded as a finite string; machines are therefore countable.
- The universal machine U receives ⟨M, w⟩ and simulates M on w step by step.
- U has a fixed number of states: M's states and symbols are data written on its tapes.
- U recognizes the language A_TM but does not decide it.
- The idea of program as data underlies programmable computers and undecidability.
