Gödel's incompleteness: the truths no machine can reach

Imagine you could build a truth machine. You hand it some starting axioms and a few rules of deduction, you switch it on, and it prints out, one by one, every mathematical truth — never wrong, never forgetting one. This is not a science-fiction fantasy. It was, very nearly word for word, the program that one of the greatest mathematicians in history, David Hilbert, set for his entire discipline at the start of the twentieth century. His dream was to put mathematics on fully mechanical rails: a system in which “being true” and “being provable” would be one and the same thing. A mind could then be replaced, for the purpose of doing mathematics, by a blind procedure.

In 1931 a 25-year-old Austrian logician, Kurt Gödel, demolished that dream — and he did it with an elegance that still commands respect today. He did not say “this is hard” or “we have not managed it yet.” He proved, in the hardest mathematical sense, that it is impossible in principle. The way he did it is one of the most beautiful tricks the human mind has ever pulled.

The secret weapon is self-reference

You already know the basic ingredient — everyone does, without naming it. It is the liar paradox: “This sentence is false.” Try to give it a value. If it is true, then what it says is the case, so it is false. If it is false, then what it says is wrong, so it is true. The sentence spins forever, because it talks about itself. Self-reference is a short circuit: a statement that takes itself as its own object.

Gödel’s genius was to turn that word-game into a logical bomb. Instead of “this sentence is false” — which talks about truth, a slippery notion — he built a sentence that talks about provability, a mechanical, checkable notion:

G: “This sentence is not provable in the system S.”

Keep it in view; the whole theorem fits inside that one line. But before we see why it is devastating, there is a mystery to solve: how can a mathematical formula, which only knows how to talk about numbers, say something about itself?

The answer is the single technical idea worth carrying away, and it has a homely image. Gödel gave every mathematical statement a unique number, like a barcode. “2 + 2 = 4” gets a number; “there are infinitely many primes” gets another; and the sentence G above gets one too. Suddenly a claim about sentences (“such-and-such a sentence is not provable”) becomes a claim about numbers — and numbers are exactly what the system knows how to discuss. Picture giving an ISBN to every book in a library, including the catalogue itself. The catalogue can then list itself among the books, and even write an entry that refers to its own entry. Numbering is the mirror slipped inside the system so that it can look at itself.

The coup de grâce

Now that G genuinely exists inside the system, watch what happens. There are two cases, and only one survives.

Case 1 — the system proves G. But G asserts “I am not provable.” If the system proves it, it has just proved something false. A system that proves falsehoods is inconsistent — fit for the bin, since it can prove anything at all. We discard it.

Case 2 — the system is sound (consistent). Then it cannot prove G (otherwise we fall back into Case 1). So G is not provable. But that is exactly what G says. Therefore G is true. You have just obtained a sentence that is true, yet the system cannot prove it.

This is the first incompleteness theorem: any formal system rich enough to do arithmetic, if it is consistent, contains truths it cannot reach. Hilbert’s dream — “true equals provable” — is dead. The provable is a strict subset of the true. There will always be truth that overflows. And if you add G to the axioms to catch it? The new, bigger system immediately manufactures its own unreachable G′. The crescent never closes.

A system cannot certify itself

Gödel followed with a second theorem, even more unsettling for our truth machine. We have just seen that “if S is consistent, then G is true.” That implication can be written inside S. So if S could prove its own consistency, it could deduce G — which we showed to be unprovable. Contradiction. The conclusion:

No consistent system can prove its own consistency. To be sure a system never contradicts itself, you must step outside it, into a larger system — which, in turn, cannot vouch for itself.

The image to keep: nobody can prove their own sanity by reasoning only from inside their own head. If you were mad, your reasoning would be mad too, and would cheerfully “prove” to you that you are perfectly fine. The certainty of being consistent can only come from the outside. No formal system can pull itself up by its own bootstraps to the certainty of its own coherence. There is always a blind spot exactly where it looks at itself.

The big leap: is the mind a machine?

Here is where the result reaches its most charged question. In the 1960s the philosopher John Lucas, and later the physicist Roger Penrose (Nobel laureate, 2020), drew a spectacular conclusion from Gödel. Their reasoning, in one sentence:

For any machine (any formal system) there is a Gödel sentence G that the machine cannot prove — but that we humans can see to be true. So the human mind can do something no machine can. So the mind is not a machine.

This is the Lucas–Penrose argument, and it is dangerously seductive: it seems to offer a mathematical proof that you are more than a program, that something in you escapes mechanisation by construction.

Except the argument leaks, and it is worth seeing where, because the leak is instructive. Re-read the coup de grâce: “if S is consistent, then G is true.” Our ability to “see” that G is true rests entirely on one assumption — that the system is consistent. But what about us? If we are ourselves some kind of formal system (very large, very messy), then by the second theorem we can no more prove our own consistency than S can. We only “see” the truth of G by freely assuming something we cannot establish about ourselves. Stuart Russell and Peter Norvig — authors of the standard AI textbook — put it bluntly: nothing shows that Gödel does not apply to humans too, and the argument ultimately rests on “an intuition that humans could perform superhuman feats of mathematical insight.”

The debate is not settled, and that is what makes it alive rather than closed. Penrose goes all the way: if the mind really is non-computable, then there must be non-computable physics somewhere in the brain — hence his (heavily contested) theory of quantum effects in neurons. Most logicians think instead that the argument bites its own tail. What to keep is not “who is right” but the shape of the chasm: Gödel does not prove that mind surpasses machine; he proves that every system — machine or mind-seen-as-a-system — has a horizon it cannot cross from the inside. Incompleteness is not a shameful weakness of machines. It is the price of richness. Anything powerful enough to talk about itself is, by the same stroke, condemned not to know everything about itself.

Where this stands in 2026

Three recent threads show the theorem is anything but a museum piece.

First, machines are proving more than ever — under the ceiling. In November 2025, DeepMind published in Nature the method behind AlphaProof, a system that teaches itself, by reinforcement learning, to write proofs in the formal language Lean, and reached medal level at the International Mathematical Olympiad — it even cracked Problem 6, which only 5 of 609 human contestants solved. It is the exact flip side of this essay: the machine excels inside the circle of the provable, but it does not move Gödel’s ceiling by a millimetre. The power rises; the ceiling does not.

Second, the limit has migrated into AI safety. A 2025 paper, “Limitations on Safe, Trusted, Artificial General Intelligence,” applies undecidability- and incompleteness-style arguments to advanced AI: some guarantees we would love to have — a system that certifies itself fully reliable and consistent — run straight into the second theorem. A sufficiently powerful system cannot also vouch entirely for its own harmlessness from the inside. Oversight will always have to come, at least in part, from the outside.

Third, Penrose’s physical wager keeps resurfacing — and stays contested. A 2025 article in Neuroscience of Consciousness offers experimental arguments for a quantum substrate of consciousness in neuronal microtubules (the Orch-OR theory of Penrose and Hameroff). Read with caution: the central objection — quantum decoherence within femtoseconds, far too fast for neurons — has not been answered, and this is a claim from authors invested in the theory, not a consensus.

What the incompleteness theorems leave us with, in the end, is a single thread running through logic, computation, the design of trustworthy machines, and the oldest question about the mind: build a system powerful enough to speak of itself, and you have built one that cannot, from within, see all the way to its own edge.

Further reading

• Wikipedia — “Penrose–Lucas argument” — the cleanest overview: the argument, its two storeys (Gödel, then physics), and the main objections. The right entry point.
• Internet Encyclopedia of Philosophy — “The Lucas-Penrose Argument about Gödel’s Theorem” — the serious philosophical version, dissecting the consistency assumption that is precisely where the argument leaks.
• David Chalmers — “Minds, Machines, and Mathematics” — the reference rebuttal, by one of the leading philosophers of mind: why the jump from “I see it” to “I surpass the machine” does not hold.
• Google DeepMind — “AI solves IMO problems at silver-medal level” (AlphaProof) — see a machine prove theorems in Lean, and keep in mind that it works under Gödel’s ceiling.