Infinities, impossibilities, and the man in the white linen suit

Gödel's final months and the walk home

In the last years of his life, Kurt Gödel starved himself to death. Convinced that someone was poisoning his food, he ate only what his wife Adele had tasted first. When she was hospitalised after a stroke in late 1977, he stopped eating altogether. He died in Princeton Hospital on January 14th 1978, weighing 29 kilograms. The death certificate read “malnutrition and wasting from neglect caused by personality disturbance.” The greatest logician since Aristotle, a man who had proved that mathematics itself contained truths it could never reach, was killed by a distorted inner logic he could not escape.

Almost nobody outside mathematics knows his name. Einstein did. The two were faculty at Princeton’s Institute for Advanced Study from the 1940s onward, and Einstein, by then ageing and isolated from the mainstream of physics, told colleagues that he went to his office “just to have the privilege of walking home with Kurt Gödel.” They made an odd pair on the Princeton sidewalks, Einstein rumpled and laughing, Gödel dapper in a white linen suit, talking animatedly in German on their daily walk to and from the Institute. John von Neumann, who cancelled an entire lecture series on David Hilbert’s programme after reading Gödel’s 1931 paper, called his work “singular and monumental, a landmark which will remain visible far in space and time.”

So what did Gödel prove, and why does it matter now, in the middle of an AI boom that is spending trillions of dollars, much of it resting on the assumption that intelligence is a scaling problem?

What incompleteness means

Put simply, Gödel proved that mathematics cannot fully explain itself. The longer version requires a little patience.

In 1900, the German mathematician David Hilbert challenged the field to build what amounted to a perfect machine for mathematics. Start with a set of basic rules (called axioms), things so obviously true they need no argument, and then derive every mathematical truth from those rules, step by mechanical step. If you could do that, mathematics would be complete - meaning every true statement would be provable, consistent, and free of contradictions. You could hand the whole enterprise over to a clerk who follows instructions. This was Hilbert’s programme, and for three decades it was the organising ambition of the field.

Then, in 1931, at the age of 25, Gödel demolished it in one stroke.

Gödel’s first incompleteness theorem proved that any set of rules powerful enough to handle basic arithmetic will contain true statements it cannot prove - not because the rules were poorly chosen, but as a structural feature of rule-based systems themselves. His trick was to construct a mathematical sentence that refers to itself. Consider the sentence, “This sentence has no proof.” Gödel’s technical feat, the part that fills his 1931 paper, was to build this sentence from pure arithmetic, by encoding statements about numbers as numbers themselves. It is not English smuggled into maths. It is pure maths.

There are only two possibilities. Either the system can prove it, or it cannot. If the system can prove “This sentence has no proof,” there is an immediate problem. We have just proved a sentence that claims to have no proof. A system that proves false things is contradictory, and contradictions in mathematics are fatal. Once you allow a single one, you can use it to prove anything, including that 1 equals 2. The system becomes useless. If the system cannot prove “This sentence has no proof,” there is a different problem. The sentence said it had no proof, and it turns out to be right. It is a true statement. But the system has no way to prove it. So we have a truth the system cannot reach, which means Hilbert’s rulebook has a blind spot. Any sensible mathematical system would rather have blind spots than contradictions. So the sentence (logicians call it a Gödel sentence) is true but unprovable, and Hilbert’s dream of a rulebook that can prove every true thing was dead.

Gödel’s second theorem twisted the knife. It showed that no set of mathematical rules can prove, using only its own rules, that it is free of contradictions. If you want to check whether your system is trustworthy, you always need a bigger system to do the checking, and that bigger system inherits the same limitation. Turtles all the way down.

This is not mysticism, nor is it a claim about consciousness or creativity. It is a precise result about rule-based systems, the kind of systems that all software, including AI, are built from. That is what makes it relevant today.

The failed dream that built the computer

Hilbert had asked for one more thing, and Gödel’s paper left it wounded rather than dead. Alongside completeness and consistency, he wanted decidability - a mechanical method that could, in a finite number of steps, determine whether any mathematical statement follows from the rules. No genius required: crank the handle and read the verdict.

In 1936, a 23-year-old Cambridge fellow named Alan Turing killed that too. To prove that no mechanical method could exist, he first had to pin down what “mechanical method” meant, which nobody had done before. His answer was an imaginary device - a paper tape and a head that moves along it, reading and writing symbols according to a fixed table of rules. Anything a human clerk could work out by rote, this device could also work out. Then he showed the device has a blind spot of its own.

Imagine a fortune-teller who is never wrong, and a stubborn customer determined to sabotage every forecast. “You will leave by the door.” He climbs out the window. “You will take the window.” He strolls out the door. She is not bad at her job. The job is impossible because her prediction feeds back into the very behaviour it is trying to predict. Turing turned that scene into code.

The checker plays the fortune-teller. It is a program whose job is to read any other program the way you might read a recipe, then predict its fate: either “this one finishes” or “this one grinds on forever.” The saboteur plays the stubborn customer. It is a short program with a copy of the checker tucked inside, plus one standing rule. Ask the checker what I am predicted to do, then do the opposite. If the prediction is that it finishes, it deliberately loops forever. If the prediction is that it runs forever, it stops dead.

So what does the checker predict for the saboteur? “Finishes” is wrong, because the saboteur hears that and loops. “Grinds on forever” is wrong, because the saboteur hears that and stops. The saboteur is assembled entirely from the checker’s own parts, which makes it inevitable rather than a fluke. Build a perfect checker, and you have, in the same afternoon, built the plans for the thing that breaks it. A perfect checker is therefore a contradiction in terms. Programs that predict how other programs will behave most of the time are unremarkable - static analysers and type checkers are used routinely. The program that cannot exist is the one that is never wrong. This is the so-called halting problem: Gödel’s self-referential sentence, rebuilt from machinery, a machine then forced to ask a question about itself.

To show what machines cannot do, Turing had to invent the machine. His imaginary device is the theoretical blueprint of the general-purpose computer - a single machine that can run any program you feed it as data. Nine years later, John von Neumann, who knew Turing’s paper well and admired it, wrote the First Draft of a Report on the EDVAC, which is, in logical terms, Turing’s universal machine rendered in vacuum tubes. Essentially every computer built since follows that design. The laptop on your desk and the datacentre GPU training the next frontier model are, once the engineering is stripped away, the same device from a 1936 logic paper.

Gödel himself thought Turing had done him a favour. It was Turing’s definition of a mechanical procedure, he wrote, that made a “precise and unquestionably adequate” general version of his own theorems possible. And the machine in the theorem turned out to be the thing every business now runs on, born as a stepping stone in a proof about what it could never do.

The Gödel machine and the guarantee that vanished

Once you have a machine that can run any program, the next question is whether it can improve itself autonomously. In 2003, the German computer scientist Jürgen Schmidhuber proposed a thought experiment he called the Gödel machine. It was an AI agent designed to rewrite its own code, with one ironclad constraint: it would change itself only when it could first prove, with mathematical certainty, that the change would make it better. Not “test and see.” Prove it, as you would a theorem, before running the new version. No proof, no rewrite.

Nobody ever built one. To prove that a code change will improve future performance, you need to search through all possible mathematical arguments that could establish that fact. For any interesting problem, the number of candidate proofs is so astronomically large that the search would take longer than any improvement could ever be worth. It is the computational equivalent of insisting on a signed certificate from every possible future before crossing the road. The Gödel machine was provably optimal but completely impractical.

In May 2025, the Japanese AI lab Sakana released a system called the Darwin Gödel Machine. It retained the self-improvement loop but dropped the proof requirement. Instead of proving that a code change would help, the Darwin Gödel Machine proposes changes using a large language model, tests them against SWE-bench (a benchmark that scores whether an AI can fix real bugs in real software), and keeps what works. The name still invokes Gödel, but the mechanism is Darwinian - natural selection, not formal proof. Fitness measured by benchmark scores, not mathematical certainty.

Judged purely on the scoreboard, it delivered. The system improved its SWE-bench score from 20% to 50% through autonomous self-modification. It developed emergent behaviours, such as patch validation and error memory, that no one had designed. Schmidhuber’s original machine, though, had exactly one property that made it safe by construction: the proof. Every modification was guaranteed to be an improvement before it ran. The Darwin Gödel Machine replaced that guarantee with something weaker: passing the benchmarks. The difference between “provably better” and “scored higher on the benchmark test” is the difference between an aircraft type certified against a spec and one that simply hasn’t crashed yet.

This is, compressed into one system’s evolution, the trajectory of AI safety. The formal guarantee was too expensive, so the industry replaced it with empirical validation and hoped nobody would notice the difference. “Self-improving” went from a mathematical statement about proof-carrying code to a softer description of an agent that rewrites itself and checks whether the benchmarks improve. Gödel was gone.

Things mathematics cannot learn

Some problems in machine learning are mathematically unanswerable. In 2019, Shai Ben-David and colleagues published a paper in Nature Machine Intelligence under the understated but devastating title “Learnability can be undecidable.” They took a straightforward question - “given this type of problem, can a machine learn to solve it?” - and proved that the deepest rules of mathematics cannot always settle it. The answer is neither yes nor no. It is silence.

The word “learnable” has an exact meaning here. A machine studies a sample and produces a rule, which is then applied to data it has never seen. That is the basis of pretty much every model we commonly use. For any given problem type, learning theory asks whether a sample size guarantees that the rule will work. If such a guarantee exists, the problem is learnable. If none does, it is not. A simple question with two possible answers. Every type of problem is supposed to get an answer.

Ben-David’s team asked it about a mundane task: choosing which adverts to show a website’s visitors based on a sample of past ones. Was this learnable or not? The answer, in their framework, depends on how many different kinds of visitors there could possibly be. That pool is not the eight billion people alive today. The model reduces each visitor to a profile of measurements, and measurements vary enormously. A visitor might linger on a page for three seconds or for a shade over three, and between any two possible profiles there is always room for a third. The pool of possibilities therefore has no end.

That arrangement - a finite sample making predictions about an endless pool - appears across almost every AI product on the market, not just in advertising. Training data is always finite. The world into which a system is deployed is not. Ben-David’s question is whether that leap can ever carry a guarantee, and everything hinges on how big the infinity is. That sounds like it must have an answer, but it does not.

Georg Cantor proved in the 1870s that infinity comes in sizes. Whole numbers form one infinity. The points on a line form a strictly bigger one, and the proof is surprisingly simple. Try to pair every whole number with a point on the line, and Cantor showed you will always miss some, no matter how clever your pairing. Two collections are both endless, yet one permanently outruns the other. The continuum hypothesis asks a follow-up so obvious it would occur to a child: is there any size of infinity between those two?

Gödel proved in 1940 that the standard rules of mathematics can never prove the answer is no. Later, Paul Cohen proved in 1963, using a technique he invented for the purpose, that we can never prove the answer is yes (his proof is dense, and we’re already covering a lot of theoretical mathematics). The upshot is that no cleverer generation is coming to settle this one.