Ada wrote a program. In 1936 Turing wrote the machine that runs every program: a tape, a head, a table of states. From that toy he defined exactly what a "computable number" is — and proved there are questions no machine can answer. Here the tape actually moves.
source A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem (1936), via Petzold, The Annotated Turing — archive.org/details/annotatedturingg0000petz. Rendered, not quoted.
Turing's a-machine: an endless tape of cells, a head that reads and writes one symbol, and a finite table of rules. Each rule says: in this state, seeing this symbol — write that, move left or right, change state. That is all a computer is.
A number is computable if some such table prints its digits. Almost all real numbers are not — there are only countably many tables. Then the twist: one table, the universal machine, reads any other table off the tape and imitates it.
To see a machine halt, use Radó's busy beaver: among all N-state machines that stop, the one that writes the most 1s. These are exact, known landmarks —
| machine | halts in | writes |
|---|---|---|
| BB(2) | 6 steps | 4 ones |
| BB(3) | 14 steps | 6 ones |
Small tables, provably terminating — the perfect thing to run and check. BB(5) already runs 47,176,870 steps; BB(6) is beyond reach.
Every cell, the head, and the state change only by the table's rules — one step at a time. The beavers halt; the increment machine computes a number. Nothing is scripted.
Ada's Note G was one algorithm, wired to one task. Turing's leap: put the table itself on the tape. Then a single universal machine reads any program and carries it out — the same hardware runs the beaver, the increment, or a word processor.
That identity — program is just more data — is the whole idea of software, of the stored-program computer, of everything downstream. Ada's program is this machine's input.
The machine that can run everything cannot know everything about itself. Turing proved the halting problem: no machine decides, for every machine and input, whether it will stop.
The busy-beaver numbers make it concrete — BB(N) grows faster than any computable function, so it is uncomputable: no program can output it in general. The model that defined the computable also drew the line no computation can cross. That edge is the sharpest thing on the spine.
Runs BB(2) and BB(3) to completion and checks the halt, the step count, and the ones against Radó's known values; also checks the increment computes n+1. Then corrupt a rule.
Change a single transition and BB(3) no longer halts at 14 with 6 ones — the audit compares to the known landmark and turns red.
"The tape is finite / it's a real computer." Cut. The a-machine has an unbounded tape — that is the idealization that makes it a definition of "computable," not a physical device. Real computers are finite-state; strictly they are less than Turing machines.
"Turing built this computer in 1936." Cut. The a-machine is mathematics, a proof about the Entscheidungsproblem. Turing later built real machines (Bombe, ACE) — different objects; this sphere runs the math.
"Busy-beaver values are conjectural." Kept, corrected. BB(2)=4 and BB(3)=6 are proven; the machines here run to those exact numbers. BB(5) was only settled in 2024; BB(6) remains open.
The strongest case against, stated fairly:
And the model is one of several equivalent definitions (λ-calculus, recursion) — the Church–Turing thesis that they capture "effective computation" is a thesis, not a theorem. What is proven is the boundary itself and that the halting question sits outside it. The engine shows the inside; the adversary marks the wall.