Member-only story
The Napkin Proof That Limits Every Computer Ever Built
Cantor’s diagonal argument shows some infinities are bigger than others, and the same trick fixes what no program will ever do.
Between 0 and 1 there are more numbers than there are whole numbers in the whole of arithmetic. Not more in a loose poetic sense: more in the sense that any attempt to pair them off, one real number assigned to each counting number, must leave real numbers unclaimed, and the argument that proves it is short enough to write on a napkin. Georg Cantor published it in 1891, and it has been known ever since as the diagonal argument. Forty-five years later Alan Turing ran that same diagonal over a table of computer programs instead of a table of decimals, and came away holding the outer boundary of what any machine will ever be able to calculate.
The claim ought to be meaningless. Infinity is not a quantity one can put on a scale, and asking how big an infinity is, or which of two endless collections is larger, sounds like asking which of two empty rooms is emptier. Everything turns on what “the same size” is taken to mean, and the honest worry about Cantor’s answer is that he chose the definition that handed him the theorem he wanted. The reason to think otherwise is that his definition draws blood: it exports a hard…
