Alan Turing · Mathematics
Turing’s proof that some problems can never be solved by any computer - the unsolvability of the Halting Problem - and how it settled a great question in the foundations of mathematics and revealed a permanent boundary to the mechanical.
There is a natural and widespread assumption that computers, given enough power, memory, and time, can eventually solve any well-defined problem - that the only limits are practical ones of speed and resources, and that a sufficiently advanced machine could in principle compute anything. Turing’s most startling discovery, in the very same 1936 paper that defined the Turing machine, was that this assumption is false. There exist problems that are perfectly precise, perfectly well-defined, with definite yes-or-no answers, that no algorithm and no computer can ever solve - not because we are not clever enough, not because our machines are too slow, but because solving them is mathematically impossible. This is a result of a completely different character from saying a problem is hard. It is a proof of a permanent, absolute boundary to the power of computation, as unbreachable as the impossibility of a largest prime number or of trisecting an angle with compass and straightedge. The existence of such uncomputable problems is one of the deepest facts about the universe of mathematics, and Turing was the first to prove it cleanly, by exhibiting a specific, natural problem - whether a program will ever halt - and showing that no program can decide it.
Turing’s proof that the Halting Problem is unsolvable is a beautiful argument by contradiction, in the family of self-referential paradoxes. Suppose, for the sake of argument, that a halting-detector did exist - call it H. H takes the description of any program P and any input, and always correctly outputs ‘halts’ or ‘runs forever.’ Now Turing constructs, using H, a new and mischievous program - call it D (for ‘diagonal’ or ‘defeater’). D is designed to take the description of any program as input, and to do the opposite of what H predicts that program would do when run on its own description: specifically, D first asks H, ‘will program P, run on P’s own description, halt?’ - and then, if H says ‘yes, it halts,’ D deliberately goes into an endless loop (does not halt); but if H says ‘no, it runs forever,’ D immediately halts. So D always does the reverse of H’s prediction. Now comes the fatal question: what happens when we run D on its own description? If D halts, then H must have predicted D would run forever (since D halts precisely when H predicts ‘runs forever’) - so H predicted wrongly. But if D runs forever, then H must have predicted D would halt - so again H predicted wrongly. Either way, H gives the wrong answer about D. This contradicts our assumption that H is always correct. The assumption must be false: no such perfect halting-detector H can exist. The Halting Problem is unsolvable.
Turing did not prove the Halting Problem unsolvable as an isolated curiosity; he did it to answer a great open question in the foundations of mathematics, named in the very title of his paper: the Entscheidungsproblem, German for ‘decision problem.’ This problem, posed by the great mathematician David Hilbert, asked whether there exists a definite, general, mechanical procedure - an algorithm - that could decide, for any mathematical statement expressed in formal logic, whether it is provable or not. Hilbert, the leading mathematician of his age, hoped the answer was yes: that mathematics could be, in this sense, fully mechanised, every question settled by a universal decision procedure grinding out ‘provable’ or ‘not provable.’ It was a dream of completeness and finality - a vision of mathematics as a domain where, in principle, no question need ever remain genuinely open, because a procedure existed to decide them all. Turing’s answer, arrived at independently and almost simultaneously with Alonzo Church, was a decisive no. Using his machine and the unsolvability of the Halting Problem, Turing showed that no such universal decision procedure can exist: there is no algorithm that can decide the provability of every mathematical statement. The Entscheidungsproblem was answered in the negative, Hilbert’s dream of a fully mechanisable mathematics was refuted, and a permanent limit to the reach of algorithmic method was established. The Turing machine had been invented, in the first place, precisely as the tool to prove this profound impossibility.
This is the opening of the lesson. The rest — the dialogue, the primary source, and the recall — is in the app.
You learned how Turing proved that some problems are uncomputable - the Halting Problem cannot be solved by any algorithm. Explain what the Halting Problem is, the idea of Turing’s proof, and why it shows a permanent limit to computation.
Leads to Bertrand Russell.
Begin this lesson →epoché — a humanities education that remembers you.