Iain Harper's Blog

In the last years of his life, Kurt Gödel starved himself to death. Convinced that someone was poisoning his food, he would eat 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 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 the Institute and back. 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 is provable, consistent, and free of contradictions. You could hand the whole enterprise to a clerk following instructions. This was called Hilbert's programme, and for three decades it was the organising ambition of the field. Then Gödel demolished it in one stroke in 1931, at the age of 25.

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 building this sentence out of 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 says it has no proof. A system that proves false things is a system with contradictions, and contradictions in mathematics are fatal. Because 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 that it is free of contradictions, using only its own rules. 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, and not a claim about consciousness or creativity. It is a precise result about rule-based systems, the kind of systems that all software, including AI, is 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 take any mathematical statement and settle, in a finite number of steps, whether it 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 previously done. 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 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 is what 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 into 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, another 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 iron 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, in the way you prove 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.

Then in May 2025, the Japanese AI lab Sakana released a system they called the Darwin Gödel Machine. It kept 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 scoring 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 like patch validation and error memory that nobody 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 just 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, and the rule is then let loose on data it has never seen. That is the basis of pretty much every model we commonly use. For any given type of problem, learning theory asks whether some sample size guarantees 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 depends, in their framework, on how many different kinds of visitor 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, shows up across almost every AI product on the market, not just advertising. Training data is always finite. The world a system is deployed into is not. Ben-David's question is whether that leap can ever carry a guarantee, and everything hangs 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 that 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, 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. The rules of mathematics simply contain no answer. Take every rule of arithmetic and logic we have and follow it as far as it goes, in any direction you like. You will never arrive at yes and you will never arrive at no. The question is open in both directions, permanently.

Now the chain closes. Whether the advertising problem is learnable depends on the size of that infinity. The size of that infinity is a question mathematics cannot answer. So whether the advertising problem is learnable is a question mathematics cannot answer. The strange silence at the very bottom of mathematics travels up the chain and surfaces in a question about showing adverts to shoppers.

Obviously no practical everyday ad campaign hangs on the continuum hypothesis. But the casualty was the promise. Learning theory is supposed to sort every problem into neat buckets: learnable or not, and Ben-David found a problem it can never sort. Not a problem waiting for better mathematicians. A problem where the sorting itself is impossible. The University of Waterloo, Ben-David's institution, described the result as “important and almost troubling.” No budget fixes this one, the way a budget can fix training costs or patchy data. It is a hole in the floor, a place where the mathematical ground itself gives way.

The neural network that exists and cannot be built

A complementary result, published in 2022, is narrower and stranger. Training a neural network is, at bottom, an exercise in trial and error. You show the network examples and measure how wrong its answers are, then nudge its millions of internal settings to make them slightly less wrong. Repeat this billions of times and, often, the network converges on something remarkably good. The Cambridge mathematician Matthew Colbrook and colleagues showed in a 2022 paper in PNAS that this process has a hard boundary nobody expected.

The place where the boundary turned up is medical imaging. An MRI scanner does not take a photograph. It collects measurements, and to keep patients in the incredibly claustrophobic machine for minutes rather than hours it collects far fewer than a complete image needs. Software has to rebuild the full picture from the partial data. Neural networks became the favoured tool for the rebuilding because they do it faster and more sharply than the older mathematical methods.

Then researchers started probing the results and found something unnerving. Nudge the input slightly, with a trace of noise or a small movement by the patient, and the output could change out of all proportion. Sometimes the rebuilt scan came back looking perfect but wrong, showing details that were never in the body. Worse, it is a failure that does not look like a failure. A blurry image warns you. A crisp fabricated one does not.

A demonstration of the capability may indicate nothing is amiss, and not because anyone is cheating. A demo runs the network on typical inputs, the kind it trained on, where it genuinely is good. The failures live in the near-misses, a typical input plus a whisker of noise. Near-misses are endless and a demo can show only a handful of scenarios. The demo is honest, and the danger sits exactly where it cannot look.

The natural presumptive diagnosis is undertraining. Feed it more scans and buy a bigger model, and surely the wobble irons itself out. That hope is what Colbrook's theorem takes off the table. What the paper proved has two halves. First, for certain reconstruction problems, a network that is both accurate and stable exists. Somewhere in the space of all possible settings sits a configuration immune to the wobble. Second, no training procedure can find it. Not the ones we have. Not any. None at all, ever.

The second half is what kills the more-data hope. A training procedure is itself a program, a step-by-step recipe running on the machine Turing described, and the proof covers every recipe there could ever be. More data does not change that. Data is what you feed a recipe, and the theorem is about the recipes. It is like knowing a winning lottery ticket is in a barrel whilst simultaneously holding a proof that no way of drawing from the barrel will ever pull it out. The ticket is real. the searching is futile.

As Colbrook put it, the paradox Turing and Gödel identified has now been “brought forward into the world of AI”, and for certain problems the algorithms needed simply cannot exist.

For the overwhelming majority of real-world problems, training works. But there is no general way to tell in advance which problems will defeat us, and the assumption that enough data and compute will always get us there over the line is, in certain corners of the problem space, provably false.

The machine you cannot contain

The most provocative extension of Gödel's legacy into AI concerns a question that sounds simple. Can we guarantee that a sufficiently powerful AI will not cause harm?

In 2021, Manuel Alfonseca and colleagues published a paper in the Journal of Artificial Intelligence Research arguing that the answer, for a general-purpose superintelligent system, is provably no. Their argument leans on the halting problem, the impossibility Turing established on his way to inventing the computer. You can check specific programs for specific bugs. What you cannot build is the universal checker, the one that works for any program in any situation.

Alfonseca's team showed that asking “will this AI harm humans?” is, mathematically, the same type of question as asking “will this program halt?” Both require predicting the complete future behaviour of a system from its current state. To guarantee a system will never cause harm you would need to trace every possible sequence of actions it could take and confirm none of them is harmful. That is the halting problem in different clothes, and Turing proved that this class of prediction is impossible to guarantee. You cannot build a general-purpose AI safety monitor for the same reason you cannot build a general-purpose program-behaviour predictor. The task is not difficult. It is formally, provably, impossible.

The authors went further, showing that we may not even be able to recognise when a superintelligent system has arrived, because deciding whether a machine is smarter than a human falls into the same class of unanswerable questions.The argument is grounded, not speculative, though it does assume more generality than any AI system possesses today. No system currently available is general enough to face any possible input the way a true Turing machine can.

What it establishes still matters though. Certain safety guarantees are not engineering problems awaiting a sufficiently clever solution. They are mathematical impossibilities, like trying to square the circle or list every real number between 0 and 1. The safety community can build better guardrails and better kill switches. What it cannot build, given the computational framework we share, is a system that certifies another system as unconditionally safe.

What Gödel would recognise

These four threads share a common ancestor in what Gödel proved in 1931 and Turing sharpened in 1936. Rule-based systems cannot fully account for themselves. A system cannot certify its own trustworthiness. A learning framework cannot determine its own boundaries. A safety strategy cannot verify its own completeness.

None of this is softened by the fact that a neural network feels organic rather than rule-like. A model's weights are numbers and its training is arithmetic, all of it running on von Neumann's rendering of Turing's imaginary device. AI is not adjacent to this mathematics. AI is made of it.

The AI industry, understandably, would rather not dwell on this. The commercial logic of scaling requires that intelligence be treated as a problem of sufficient resources, more data, more compute, more parameters, more money. Hard limits are a vibe-killer, and for the overwhelming majority of commercial applications, the limits Gödel identified are irrelevant. Your chatbot will not run into the continuum hypothesis while re-drafting an email.

But whether a self-improving agent can guarantee its improvements are improvements, and whether anyone can prove a system will not cause harm, are questions that sit squarely in the territory Gödel mapped. His inheritance is the precise framework that shows certain guarantees about thinking machines are provably unavailable, which is a different and narrower thing than saying machines can never think.

Einstein's eccentric walking companion saw it before anyone else. Formal systems cannot fully certify themselves. That was a logician's problem in 1931. It became an engineer's problem when Turing turned the proof into a machine. It is now a commercial problem, because the industry betting trillions on those machines is implicitly selling guarantees the mathematics has never supported, guarantees generated by systems that cannot check themselves any more than Gödel’s own warped internal logic could check itself. He died trapped inside it.

I am a partner in Better than Good. We help companies make sense of technology and build lasting improvements to their operations. Talk to us today: https://betterthangood.xyz/#contact