◄ UD0   ← Gödel   LOGIKĒ · XI
LOGIKĒ · XI · the machine & the limits of computation

Alan Turing

1912 – 1954 · London & Cambridge & Bletchley Park · "On Computable Numbers", 1936 · founder of computer science
Gödel proved the dream of a complete formal system impossible. Turing, a 23-year-old in Cambridge, asked the next question and answered it with a machine. To pin down what "mechanically computable" even means, he imagined the simplest possible computer: a head reading a tape, one square at a time, following a tiny table of rules. That stripped-down device — the Turing machine — can compute anything that can be computed at all. And one special machine can simulate every other: the universal machine, the stored-program computer on paper, a decade before the electronics existed. Then he proved its limit: no machine can decide, in general, whether an arbitrary program will ever halt.
✓ STRONG

Foundational and exact. The Turing machine, universality, and the undecidability of the halting problem are rigorous results — the bedrock definition of computation and the literal blueprint of the stored-program computer.

◐ A MODEL, NOT THE BRAIN

It defines computability, not mind. The Church–Turing thesis (this captures all mechanical computation) is a well-supported thesis, not a theorem; and "a machine can think" was Turing's conjecture/test, not something he proved.

◔ OFTEN MISREAD

Undecidable ≠ "computers can't". The halting problem is a precise general-case impossibility; plenty of specific programs are easy to analyse. And the "Turing test" is a thought experiment, not a verdict on consciousness.

I · A running machine — computation, stripped to the bone

Here is the whole of a computer: an infinite tape of cells (each 0 or 1), a head on one cell, a state, and a rule table — "in this state reading this symbol: write a symbol, move left or right, go to that state." Nothing else. Pick a program and run it. The busy beaver is a tiny machine that writes as many 1s as it can before halting — its growth becomes literally uncomputable, the bridge to Module II. The incrementer adds 1 to a binary number. Watch the head crawl the tape; the active rule lights up.

state Astep 0 1s on tape 0
Six cells, three states, and it halts after writing six 1s — yet decide in advance how many 1s an n-state beaver writes, and you are computing the uncomputable. This little device is the exact thing John von Neumann turned into the stored-program architecture every computer still uses.

II · The halting problem — a question no machine can answer

Could one master program H take any program P and input x and always correctly answer "does P halt on x, or loop forever?" Turing proved: no — and he did it with Gödel's diagonal trick made mechanical. Suppose H exists. Build a contrary machine D: D runs H on the question "does this very machine halt?" and then does the opposite of H's answer. Now ask D to judge itself.

D asks H: “will D(D) halt?” — then D does the opposite.
if H says “halts” → D loops  ·  if H says “loops” → D halts
Pick H's prediction about D(D) — and watch it refute itself.
Whatever H predicts, D is built to do the opposite — so H is wrong about D. The only escapable assumption is that H existed at all. No general halting-decider can exist. This is the same diagonal that gave Gödel his unprovable sentence — now it says some questions are not just unprovable but uncomputable.
"We can only see a short distance ahead, but we can see plenty there that needs to be done." — Alan Turing, 1950

III · The two gifts, the war, the man

THE UNIVERSAL MACHINE

One Turing machine can read the description of any other off its tape and simulate it. Hardware and program become separable — the idea of software, and of the general-purpose computer, born on paper in 1936.

THE HALTING LIMIT

No program decides halting for all programs. Computation has a hard horizon — an exact echo of Gödel's incompleteness, recast as a fact about what machines can and cannot decide.

The lineage closes its loop here. Leibniz wanted reasoning reduced to calculation; Boole made logic an algebra of 0 and 1; Gödel showed the formal dream has a ceiling — and Turing gave that ceiling a machine, then showed the machine is universal. Everything in PSĒPHOS — every processor, every program — is a physical Turing machine. One sphere remains: Shannon, who in 1937 noticed Boole's algebra is the algebra of switches, soldering this whole lineage onto the gate.

Gate kept on. Two honesties. First, the scope: "undecidable" means no single method works for every case — it does not mean computers are weak or that your particular program can't be analysed; and the famous Turing test and "machines can think" were Turing's provocations and predictions (1950), not theorems — open questions to this day, not settled results. The Church–Turing thesis — that this captures all effective computation — is overwhelmingly supported but is a thesis about an informal notion, not something provable. Second, the man: at Bletchley Park, Turing's Bombe and methods broke the German naval Enigma, work credited with shortening WWII and saving very many lives — kept secret for decades, so he was never publicly honoured in his lifetime. In 1952, prosecuted under Britain's gross-indecency law simply for being gay, he was forced to choose prison or chemical castration; he chose the hormone treatment, lost his security clearance, and in 1954 died of cyanide poisoning at 41, ruled a suicide. A formal apology came in 2009 and a royal pardon in 2013 — the "Alan Turing law" later pardoned thousands more. The man who defined the machine, and helped win the war with one, was destroyed by the state he saved. The logic stands; the injustice is named.