💻 computer science

Auto formalisation of Chaitin and of the surprise incompleteness Theorem

This paper presents a case study using an LLM (Claude) to autoformalize Chaitin's proof of the first incompleteness theorem and the Kritchman-Raz surprise examination paradox version of the second incompleteness theorem in Agda, demonstrating the model's ability to construct complex computational simulations and produce machine-checked proofs while highlighting current strengths and limitations in mathematical reasoning.

Original authors: Thierry Coquand

Published 2026-06-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Thierry Coquand

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Teaching a Robot to Do Math

Imagine you have a very smart robot (an AI named Claude) and a very strict, rule-bound math textbook called "Basic Recursive Arithmetic." This textbook is like a game with very specific rules: you can only use basic counting and simple logic, no fancy shortcuts or "magic" tricks.

The goal of this paper is to see if the robot can read a complex, famous mathematical proof (about why math has limits) and rewrite it entirely in the strict language of that textbook, without a human writing a single line of code.

The answer is yes. The robot successfully translated two deep mathematical ideas into this strict language, creating a proof that a computer can check to be 100% correct.

The Two Main Ideas

The paper focuses on two famous concepts: Chaitin's Proof (related to the first incompleteness theorem) and the Surprise Examination Paradox (a version of the second incompleteness theorem).

1. The "Short Description" Game (Chaitin's Proof)

Imagine you have a library of every possible story you could write using a limited set of letters.

The Rule: Some stories are very short and easy to describe. Others are so complex that the shortest way to describe them is to just write the whole story down.
The Problem: Chaitin's proof tries to find a story that is so complex that it cannot be described by a short program.
The Robot's Challenge: To prove this, the robot had to build a "machine" inside the math textbook that could read a story, run it, and see what it does.
The Hurdle: The math textbook is too simple to naturally handle "running a program" because that usually requires a complex function (like the Ackermann function) that the textbook doesn't allow.
The Solution: The human author suggested a trick called "Gandy/Howard majorisation." Think of this as giving the robot a fuel tank. Instead of asking the machine to run forever, the robot calculates exactly how much "fuel" (steps) a program needs to finish. It builds a special "fuel gauge" that guarantees the program will stop before the tank runs out.
The Result: The robot built this fuel gauge on its own. It proved that if you try to describe a number that is "too complex to be described simply," you end up creating a logical contradiction (like proving that 0 equals 1).

2. The "Surprise Exam" and the Heap of Sand

The second part of the paper deals with a famous paradox: A teacher announces there will be a surprise exam next week. The students reason it can't be Friday (because if they haven't had it by Thursday, they'd know it's Friday), so it can't be Thursday, and so on... until they conclude there can be no exam at all. But then the teacher gives it on Wednesday, and it is a surprise.

The paper uses a version of this logic (by Kritchman and Raz) to prove that a math system cannot prove its own consistency (that it doesn't contain contradictions).

The Old Way: Previous proofs counted the number of days or numbers to find a contradiction.
The New Way (The Sorites/Heap of Sand): The authors compare this to the Heap of Sand Paradox.
- If you have a heap of sand and remove one grain, it's still a heap.
- If you remove another, it's still a heap.
- If you keep removing grains one by one, eventually you have zero grains left. But at what exact point did it stop being a "heap"?
The Application:
- Imagine a list of numbers from 0 to a huge number $N$ .
- The logic tries to prove: "It is impossible for all these numbers to have a short description."
- The robot proves this step-by-step. It says, "If we assume numbers 0 through $N$ all have short descriptions, we get a contradiction."
- Then it removes 0. "Okay, if 1 through $N$ have short descriptions, we still get a contradiction."
- It keeps removing one number at a time (like removing grains of sand).
- Eventually, it reaches a point where the list is empty, but the logic forces a contradiction anyway.
The Twist: The paper argues this isn't a "vicious circle" of self-reference; it's more like the sand heap. You can take away one grain (one number) safely, but if you keep doing it, the whole structure collapses. This collapse proves that the math system cannot prove it is safe (consistent) without breaking itself.

Why This Matters (According to the Paper)

AI as a Math Assistant: The paper shows that current AI (like Claude) is now good enough to handle the tiny, tedious details of complex math proofs. It can build parsers, evaluate machines, and handle logic steps that humans usually have to do manually.
Constructive Math: The paper highlights that in "constructive mathematics" (where you must actually build the thing you are talking about), the idea of a "partial function" (a program that might run forever) is tricky. The robot had to use a "looping" program that might run forever, but the proof guarantees it stops. This is a subtle but crucial distinction that the AI handled correctly.
No Magic Tricks: The robot didn't use any "tactics" (shortcuts) or fancy libraries. It built everything from scratch using only the basic rules of the math system. This makes the proof very robust and easy for a computer to verify.

The Conclusion

The paper is a case study showing that AI can now act as a powerful partner in formal mathematics. It can take a high-level idea (like "math has limits") and translate it into a rigid, machine-checkable format.

The authors note that while the AI needs a human to guide it (like suggesting the "fuel tank" trick), the AI can then autonomously write the code, build the logic, and document the entire process. The result is a fully verified proof that clarifies exactly how these deep logical paradoxes work, stripping away ambiguity and leaving only the hard, logical facts.

Technical Summary: Auto Formalisation of Chaitin and the Surprise Incompleteness Theorem

Problem and Context
This report extends a previous experiment in the autoformalisation of Gödel's second incompleteness theorem using the large language model (LLM) Claude and the proof assistant Agda. The primary objective is to investigate the capabilities and limitations of current LLMs in formalising complex mathematical proofs, specifically those involving the internal representation of computation. The paper focuses on two specific targets: Chaitin's proof of the first incompleteness theorem and the Kritchman-Raz "surprise examination paradox" version of the second incompleteness theorem.

A central technical challenge addressed is the encoding of computation within Basic Recursive Arithmetic (BRA), a system (formulated by Guard) that lacks object quantifiers and standard tactics. In such a system, defining an internal evaluation function is impossible as it would exceed primitive recursive bounds (similar to the Ackermann function). The problem requires representing programs and their execution steps entirely within the object language without relying on meta-level functions or external libraries.

Methodology
The project employs a "spartan" approach where no lines of Agda code were written by the human author; the formalisation was generated autonomously by Claude based on high-level mathematical descriptions. The methodology relies on the following technical strategies:

Ternary String Encoding: Programs are represented as natural numbers interpreted as ternary strings (digits 1, 2, 3). This allows the set of programs of length at most $L^*$ to be treated as a simple initial segment of natural numbers $\{p < N\}$ , where $N = 3^{L^*+1}$ , avoiding complex enumeration mechanisms.
CK Machine Implementation: To bypass the need for a global evaluation function, Claude autonomously constructed a continuation stack small-step evaluation machine (a Landin CK machine). This machine decomposes expressions and manages a stack of continuations, allowing computation to be simulated step-by-step.
Gandy/Howard Majorisation: A critical hurdle was proving that the machine halts within a specific number of steps for a given function $f$ inside the logic. Since the step count cannot be a meta-level natural, the authors guided Claude to use the Gandy/Howard majorisation method. This involves defining a closed combinator fuel(f) via primitive recursion that provably majorises the actual running time of $f$ . This allows the completeness of the interpreter to be stated and proved internally within BRA.
Surprise Examination as Sorites: The proof of the second incompleteness theorem avoids the counting arguments used by Kritchman and Raz. Instead, it models the argument as a Sorites (heap of sand) paradox. It proceeds by external induction on a stage $r$ , proving that it is impossible for all numbers in the interval $[r, N]$ to have short descriptions.

Key Contributions and Results
The paper presents a fully machine-checked proof in Agda of the following results for Church's Basic Recursive Arithmetic:

Auto-formalised Chaitin's Theorem: The system successfully formalised Chaitin's proof, which replaces the liar sentence with Kolmogorov complexity. The formalisation produces an explicit proof-transformer $G$ . The theorem states that if a term $w$ codes a proof of the incompressibility statement $K(out(w)) > L^*$ , then $G \cdot w$ codes a proof of $0=1$ . This is formulated as a positive object-level implication rather than a meta-theoretic negation of provability.
Internalised Second Incompleteness: The paper formalises the Kritchman-Raz argument to show that if $T$ proves its own consistency ( $Con_T$ ), then $T$ is inconsistent ( $0=1$ ). The proof proceeds by a descent from $S(0)$ (the pigeonhole principle) to $S(N+1)$ (a contradiction), where each step $S(r) \to S(r+1)$ consumes the consistency hypothesis exactly once.
Constructive Insights: The formalisation highlights the role of partial functions in constructive mathematics. Specifically, the diagonal program enumerates derivable formulas until a target is found. While the program is proven to terminate externally, its size is calculated without internalising the termination proof. This demonstrates a manifestation of Blum's speed-up phenomenon, where allowing a partial recursive program (kept total by external proof) allows for unboundedly shorter programs compared to those that must internally certify halting.

Significance and Claims
The paper claims that current coding LLMs, such as Claude, are effective tools for understanding the granular details of mathematical papers, provided they operate under constant supervision. The project serves as a case study demonstrating that:

LLMs can autonomously generate complex syntactic machinery (parsers, evaluation machines) and logical arguments (majorisation) when guided by high-level structural hints.
Type theory (specifically Agda without tactics) is well-suited for expressing concrete mathematics involving computation and coding, as proofs can be represented directly without needing function extensionality or quotient types.
The "surprise" argument, when formalised, aligns more closely with the Sorites paradox than the traditional surprise examination paradox, as the contradiction arises from the iteration of sound steps rather than a single self-referential loop.

The authors conclude that while the language of type theory is perfect for this combinatorial, computational mathematics, a key research question remains: how to design formal systems capable of handling non-combinatorial objects with similar automation. The formalisation clarifies implicit details in the original presentations of Chaitin and Kritchman-Raz and provides a rigorous, machine-verified foundation for these arguments within a minimal arithmetic framework.