Where we are in the series
In chapter 1, we walked through the four diagonal theorems of self-reference: Gödel 1, Gödel 2, Löb, Tarski. They closed one whole family of fantasies about AI – the fantasy of a model that is its own complete theory, its own consistency proof, its own truth predicate. In this chapter, we walk the family that closes the next set: the fantasy of a model that can universally predict, verify, or contain the behaviour of arbitrary programs – including, eventually, other AI.
The same caveat as in Chapter 1 applies. None of what follows is anti-AI. It is anti-oracle. The math below is about the universal case, not the typical case. Knowing the difference is the difference between using a tool and worshipping it.
The halting problem (Turing, 1936)
What the theorem says.
There is no general algorithm that decides, for every program and every input, whether the program eventually halts.
Why it is true.
Turing’s proof is diagonal and is worth re-walking. Suppose there were such an algorithm H. So H(P, x) returns 1 if program P halts on input x, and 0 otherwise. Now define a new program D that, on input P, simulates H(P, P):
- If H(P, P) = 1, then D(P) deliberately enters an infinite loop.
- If H(P, P) = 0, then D(P) halts immediately.
Now run D on its own code: D(D). If D(D) halts, then by D’s definition H(D, D) must have returned 0 – meaning D(D) doesn’t halt. Contradiction. If D(D) doesn’t halt, then H(D, D) must have returned 1 – meaning D(D) halts. Contradiction either way. So H cannot exist.
The argument is genuinely diagonal: the contradiction is forced by D applying itself to its own code. It is therefore not avoidable by adding hardware, by switching to a more powerful programming language, by allowing parallelism, or by tolerating probabilistic error. The Recursion Theorem guarantees that the diagonal construction can be carried out in any Turing-equivalent system, so the result is universal across models of computation.
What it rules out for AI.
The dream of a universal predictor of program behaviour. An AI can be extraordinarily good at predicting halting behaviour for well-structured programs. There will always be, provably, an infinite class of cases on which any specific AI must err. Adding parameters, training data, or compute does not change this. The halting problem is undecidable at every level of computational power below an oracle for the halting problem itself, which – per the physical Church-Turing thesis – we cannot build.
A subtle but important corollary: the undecidability of halting is preserved under probabilistic computation. A probabilistic machine that always halts and decides halting with bounded error could be converted into a deterministic decider by exhaustively computing its acceptance probability over all coin-flip paths. There is no probabilistic loophole.
Rice’s theorem (1953) – every interesting question is undecidable
What the theorem says.
Henry Rice generalised Turing’s result with one of the most consequential theorems in computability theory. Informally, every non-trivial semantic property of programs is undecidable.
Two definitions matter:
- A property P of programs is semantic (or extensional) if it depends only on the function the program computes, not on the syntactic form of the code. For example, “this program computes the constant function 0” is semantic. “This program contains a goto statement” is syntactic, not semantic.
- A property P is non-trivial if some programs satisfy it and some don’t.
Rice’s theorem: for any non-trivial semantic property P, the decision problem “does this program satisfy P?” is undecidable.
Why it is true.
The proof is a reduction from the halting problem. Pick any non-trivial semantic property P. We may assume, without loss of generality, that the everywhere-undefined function (the program that never halts on any input) does not satisfy P; otherwise, run the argument on the complement of P. Since P is non-trivial, there is at least one program f₀ that does satisfy it. Given an instance ⟨e, x⟩ of the halting problem, construct a new program M as follows: on input y, M first simulates e on x; if that simulation halts, M goes on to compute f₀(y). If e on x never halts, M never produces any output – so M computes the everywhere-undefined function. Therefore M satisfies P exactly when e halts on x. If you had a decider for P, you could now decide halting by asking whether M satisfies P. Since halting is undecidable, P must be too.
What it rules out for AI.
Rice’s theorem is the right tool for thinking about AI safety. The following are all non-trivial semantic properties of programs, and therefore all formally undecidable when stated universally over the class of arbitrary AI systems:
- Will this AI always produce truthful outputs?
- Will this AI ever cause harm?
- Will this AI agent always refuse unsafe tool calls?
- Will this AI preserve its intended objective under self-modification?
- Will this AI behaviour remain within the bounds of any specified policy?
Manuel Alfonseca, Manuel Cebrian and collaborators made the connection rigorous in 2021 for the containment problem and the harming problem (Journal of Artificial Intelligence Research, vol 70). Mario Brcic and Roman Yampolskiy systematised the broader programme of impossibility results in AI in a 2023 survey for ACM Computing Surveys. The pattern is consistent: every interesting universal safety question reduces, via Rice or a Rice-style argument, to the halting problem.
What it does not rule out: bounded verification of specific systems under specific assumptions. Decidable safety lives at the level of well-typed sub-problems: this asset, this property, this window of operation. The right verification strategy is therefore scoped, evidence-based, and continuous. Universal certification is not in the cards.
Machines that halt (Castro González et al., 2024-2025)
A natural reaction to Rice’s theorem is: surely we can do something? The recent paper “Machines that halt resolve the undecidability of artificial intelligence alignment” (Castro González et al., arXiv:2408.08995, published in Scientific Reports 2024-2025) makes this constructive.
The observation is that Rice’s theorem applies to the class of all Turing-equivalent programs. It does not apply to restricted classes for which the relevant property is decidable by construction. So the proposed path is to restrict AI architectures to provably halting machines, built from a finite library of provably aligned primitives. Within that library, alignment becomes a guaranteed property of the architecture rather than a contingent property to be tested after the fact.
The architectural restriction is real progress, but it does not abolish the Rice barrier; it relocates it. The burden moves from “verify this AI’s behaviour” to “choose the right library of primitives.” That second burden is no longer a computational problem. It is a design and governance problem, which by definition humans have to solve.
This is, in fact, the pattern across the entire series. Each impossibility result has the same shape: you cannot have universal X by computation alone. Restricting the domain rescues some version of X. But the restriction is supplied by someone outside the system.
The Busy Beaver function (Tibor Radó, 1962)
What the function is.
The Busy Beaver function provides one of the most dramatic illustrations of how quickly the limits bite. BB(n), the Radó function, is the maximum number of steps a Turing machine with n states can take before halting, over all n-state machines that halt at all on a blank tape.
Why it is special.
BB(n) is well-defined for every n (there are only finitely many n-state machines). But it is provably non-computable, and it grows faster than every total computable function. For any function f that a computer can compute, there is some n₀ such that BB(n) > f(n) for all n ≥ n₀.
Known values:
- BB(1) = 1
- BB(2) = 6
- BB(3) = 21
- BB(4) = 107
- BB(5) = 47,176,870 (bbchallenge community, Coq-verified proof, 2024)
BB(6) is known to exceed 10↑↑15 in Knuth up-arrow notation – a number whose decimal expansion has more digits than there are atoms in the observable universe, by an unimaginable margin. And independence from the axioms of set theory arrives at a fixed, known size: Adam Yedidia and Scott Aaronson (2016) constructed an explicit 7,910-state Turing machine whose halting behaviour is independent of ZFC; Stefan O’Rear reduced the construction to 748 states, and Johannes Riebel (2023) refined it to 745. The value of BB(745) is therefore already unknowable within standard mathematics.
What it rules out for AI.
Even very small formal machines can exhibit behaviour whose runtime exceeds the resolving power of all formal systems we know how to write down. An AI that aspires to predict the behaviour of arbitrary programs must, in the limit, decide questions that the strongest mathematical theories cannot. No quantity of training data or parameter count compensates for the gap between intractable and non-computable.
The Busy Beaver function also has a clean philosophical use. Whenever someone says “given enough compute, AI will figure it out,” the right response is: figure out BB(7). BB is not a problem of resources. It is non-computable in principle.
The thread
The behaviour frontier is bounded by three layered theorems. Turing’s halting problem says there is no universal halt-predictor. Rice’s theorem says there is no universal predictor of any non-trivial semantic property. Busy Beaver says that even at small machine sizes, the behaviour space outruns every computable predictor.
Each of the three closes a specific fantasy:
- The fantasy of an AI that can decide, for every program and input, whether the program will eventually do something.
- The fantasy of an AI that can decide, for every program, whether it is safe, truthful, aligned, or behaviourally compliant.
- The fantasy that more compute will eventually exhaust the space of small-program behaviour.
None of these closures says we cannot use AI to make program behaviour easier to reason about, to spot real anomalies, to draft test cases, to assist verification, or to ground human judgement in evidence. They say only that the universal version of the dream is not available.
Coming next
Chapter 3 turns from the undecidability of behaviour to the limits of learning. We will walk Chaitin’s incompleteness, the No-Free-Lunch theorem, the 2024 Goldblum-Finzi-Rowan-Wilson refinement that explains why deep learning works anyway, Solomonoff induction’s incomputability, and the Merrill-Sabharwal circuit-complexity ceiling that places modern transformers inside the class TC⁰. None of those results says AI cannot learn well. They say something more precise: AI cannot learn universally well, and the path to learning well in any specific domain is the supply of human-chosen inductive bias.
