Euler's Eyes
2026-10-16
The universal machine: the program is data too
Each Turing machine does one thing only. The one that adds 1 adds 1; the one that writes $\frac17$ writes $\frac17$. To do a different calculation, you would need a different machine. In 1936 that was normal: mechanical calculators, punched-card tabulators and tide-predicting machines were built for one task, and changing task meant changing machine or rewiring.
In the same paper, Turing showed that this is not necessary.
A machine that reads machines
The table of rules of any machine can be written as text on a tape. Turing then described a special machine, $U$, the universal machine, which does the following:
- On the tape it receives the description of a machine $M$ and, after it, an input $x$.
- It looks up in the description the rule that matches the current state of $M$ and the symbol $M$ would be reading.
- It carries out that rule on the part of the tape that stands for $M$’s tape, notes the new state and goes back to step 2.
In this way $U$ imitates any machine step by step, as long as it receives its table. In symbols:
$$U(\langle M\rangle,x)=M(x)\quad\text{for every machine }M\text{ and every input }x.$$The price is slowness: each step of $M$ costs $U$ many steps of searching and copying. But what $U$ can calculate is exactly what all the machines together can calculate.
The program in memory
The practical consequence is the idea of the stored program. Instead of building one machine for each task, you build just one, and the task goes in as data, in the same memory that holds the numbers. Changing task becomes changing text. That is what happens when you open an app on your phone: the device is always the same, and what changes is the description it reads.
What is more, if the program is data, a program can read, write and modify other programs. That is what compilers and operating systems do, and in a way so does the machine $D$ from the proof of the halting problem, which receives its own description.
From paper to metal
After the war, in 1945–1946, Turing wrote the complete design of a stored-program computer, the ACE (Automatic Computing Engine), at the National Physical Laboratory. It was bold: memory in mercury delay lines, a speed of a million pulses a second, and even the idea that the machine could be programmed to modify its own instructions. Bureaucracy and a shortage of engineers delayed construction. A scaled-down version, the Pilot ACE, only ran in 1950, and for a while it was one of the fastest computers in the world.
Meanwhile, in Manchester, Frederic Williams and Tom Kilburn ran, on 21 June 1948, the first program stored in an electronic memory, on a machine nicknamed the Baby. Turing arrived in Manchester a few months later and worked on the machines that followed.
Exercise: write a machine as text
Encode the machine that adds 1 as a sequence of quintuples (state, reads, writes, moves, next state), using A for add, H for halt, B for blank, L for left and N for no move.
$$\text{A1 0 L A}\quad\text{A0 1 N H}\quad\text{AB 1 N H}$$That is 15 symbols. Written on a tape, they are the description $\langle M\rangle$ that the universal machine reads in order to imitate the original machine.
Exercise: how many steps does imitating cost?
Suppose that, to imitate a single step of $M$, the universal machine has to run through the whole description of $M$, with $d$ squares, and back. If $M$ takes $t$ steps, roughly how many steps does the universal machine take?
Each step of $M$ costs about $2d$ steps of $U$, so the total is about $2dt$. For the machine that adds 1, with $d=15$ and $t=4$ steps for $111+1$, that would be about 120 steps: thirty times slower, but the same result.
Sources: Alan Turing, “On computable numbers” (1936) and “Proposed electronic calculator” (1946) · B. Jack Copeland (ed.), Alan Turing’s Automatic Computing Engine (2005) · The Manchester Baby, Science and Industry Museum.
All topics on Alan Turing · ← Computable numbers: almost every number is impossible to calculate · The Enigma: 159 quintillion keys and one flaw →