A machine that only reads, writes and moves
In 1936 Alan Turing asked what it means to compute something by following rules. He pictured a clerk working with pencil and paper and stripped the job down to its smallest moves. The clerk looks at one square of paper at a time, can write a symbol there or rub it out, can move one square left or right, and keeps track of only a small amount in their head: their state.
The machine in the Scene is that clerk built as a bench instrument. A paper tape, divided into cells, runs between two reels. The head sits over one cell: its lamp reads the symbol there, its stamp can print a new one, and the tape slides one cell at a time beneath it. The display on the head shows its state, a single letter.
That is the whole machine. It has no arithmetic unit, no memory except the tape and no instructions beyond what is on its rule card. It still turns out to be able to carry out any calculation that any computer can.
The rule card is the program
Behind the head stands the rule card. It has a row for each state and a column for each symbol the head can read. Each entry says three things: the symbol to write, which way to move, and the state to switch to. A step is always the same: read the cell, find the entry for the current state and that symbol, then write, move and change state. The entry the machine will use next is lit.
The Adder adds 3 and 2 written as tally marks, 111_11. In state A it runs right over the first number. At the gap it writes a 1, joining the two numbers into six marks, and switches to B. B runs to the end, steps back and switches to C, which rubs out one mark and switches to HALT. HALT has no row on the card, so there is nothing more to do: the machine stops with five 1s on the tape.
Try it: with Program on Adder, drag Steps run back to 0, then forward one step at a time. Watch the lit entry on the rule card and the letter on the head’s display, and see the stamp fill the gap at step 4 and rub out the last mark at step 8.
Some programs stop, some never do
Running a program is the obvious way to find out what it does, but it gives only half an answer.
The Busy beaver starts on a blank tape with three states. It wanders back and forth, writes six 1s and halts at step 14. Tibor Radó asked in 1962 how many steps a machine with a given number of states can run before halting. The answers grow absurdly fast: the record for five states, 47,176,870 steps, was proved in 2024 by a large online collaboration, and for six states the record is a number far too long to write out.
The Ping-pong machine steps right and back for ever. After its first step it shows the same two pictures over and over. A deterministic machine that comes back to a picture it has already shown must repeat itself for ever, so this one can be caught.
The Counter counts in binary: 1, 10, 11, 100 and on. It never halts, and it never repeats either, because every pass leaves a bigger number on the tape. Watching it for 500 steps or 500 years shows only that it has not halted yet.
Try it: switch Program between the four and slide Steps run to 20, then all the way to 500. The counter on the bench says whether the machine has halted or is still running.
Could a program check for us?
For these four you can tell what happens by reasoning about each rule card. The real question is whether one method works for every card. Imagine a machine H, a halt checker, that takes any rule card and the tape it starts on and always answers correctly, in a finite time, HALTS or RUNS FOREVER.
H would be enormously useful. A machine that searches the even numbers for one that is not the sum of two primes halts only if Goldbach’s conjecture is false, so H would settle that famous open problem in an afternoon. Many other unsolved problems in mathematics could be settled the same way.
Try it: step Try a halt checker to Halt checker. H takes a copy of the loaded rule card and lights its answer, and for these four cards it is right.
Why the halt checker cannot exist
A rule card is itself just symbols, so it can be written on a tape and given to another machine as input, even to itself. Turing used this to show that H cannot exist. Suppose it did. Build a new machine, D, that takes a rule card P, asks H whether P halts when given its own card, and then does the opposite: if H says HALTS, D loops for ever; if H says RUNS FOREVER, D halts.
Now give D its own card. If H says D halts, D loops for ever, so H was wrong. If H says D runs forever, D halts, so H was wrong again. Every possible answer is wrong, so the assumption fails: no machine can decide, for every program and input, whether it halts. This is the halting problem, and it is undecidable. Turing’s 1936 argument was about a slightly different property, but this is the modern way of telling it.
Try it: step Try a halt checker to No checker. The board walks through D fed its own card, and H’s lamps cannot settle on either answer.
What this means for computers
Turing also described a universal machine: one fixed rule card that reads another machine’s rule card from its tape and does whatever that machine would do. That is the idea behind every computer since, which keeps its programs in the same memory as its data. Alonzo Church reached the same limits in 1936 by a different route, and the claim that these machines capture everything that can be computed by following rules is called the Church–Turing thesis.
The halting problem has company. Rice’s theorem says that every non-trivial question about what a program does, such as whether it ever prints a 7 or whether two programs always give the same answer, is undecidable in the same way. Tools that check software for bugs or viruses still work, but they have to settle for answering yes, no or “can’t tell” on some programs. The busy beaver numbers are uncomputable too: if you could compute them, you could solve the halting problem by running a machine for that many steps.
What this model leaves out
A Turing machine is a mathematical idea, not a device; Turing never built one, and the reels, stamp and lamp are drawn to make the idea concrete. Its tape is unlimited, while every real computer has finite memory, so in principle a real computer must eventually repeat itself. That is no help in practice: a machine with a few gigabytes has more possible states than there are atoms in the universe. The four rule cards are tiny examples, each step is slowed down and eased so you can watch it, and the slider stops at 500 steps although the ping-pong machine and the counter never stop. The halt checker H is imaginary, and the board compresses Turing’s proof to its core: feeding D “its own card” means writing a description of D’s rule card on its tape.