Where we are in the series
Chapter 1 walked the four self-reference theorems: Gödel 1, Gödel 2, Löb, Tarski. Chapter 2 walked the three behavioural-undecidability theorems: halting, Rice, Busy Beaver. Both chapters closed specific fantasies of an AI oracle – the fantasy of complete self-knowledge, and the fantasy of universal behavioural prediction.
This chapter closes a third family of fantasies: the fantasy of a universal learner. We will walk through five results, four classical and one from 2024: Chaitin’s incompleteness, Wolpert-Macready’s No-Free-Lunch, Goldblum et al.’s simplicity-prior refinement, Solomonoff’s incomputable universal predictor, and Merrill-Sabharwal’s circuit-complexity ceiling on modern transformers.
The recurring point is the same. None of these theorems says modern AI does not work. They say AI works under specific assumptions, and removing those assumptions removes the guarantees with them.
Kolmogorov complexity in one paragraph
Many of the results in this chapter are phrased in terms of Kolmogorov complexity, so it pays to fix the definition. Fix a universal Turing machine U. The Kolmogorov complexity K(x) of a string x is the length of the shortest program that, when run on U, outputs x. Equivalently, it is the size of the most compressed possible description of x. A string is algorithmically random, or incompressible, if K(x) ≥ |x| – that is, the shortest description of x is not shorter than x itself. Most strings are algorithmically random in this sense; a fact often misunderstood, since the structured strings we usually encounter are exactly the non-typical ones.
Chaitin’s incompleteness theorem (1974)
What the theorem says.
Gregory Chaitin recast Gödel’s incompleteness in the language of algorithmic information theory. The statement is striking: for every consistent, recursively axiomatizable formal system T, there exists a constant c(T) such that for no string x can T prove the statement K(x) > c(T). That is, every formal system can prove only finitely many lower bounds on Kolmogorov complexity.
Why it is true.
The proof is short. Suppose T could prove K(x) > c for some c much larger than the length of T’s own description. Enumerate proofs in T until the first proof of any statement of the form K(x) > c is found; output the corresponding x. This procedure is itself a program whose length is roughly |⟨T⟩| + O(log c). But it produces an x with K(x) > c, contradicting K(x) > c whenever c is sufficiently larger than |⟨T⟩|.
The constant c(T) is essentially a measure of how much information T can certify. The bound is brutally quantitative: any model with description length n bits can certify, at best, complexity bounds of size around n. Doubling parameters buys you a constant. The world is bigger than n bits, almost everywhere.
What it rules out for AI.
Every realised AI is a finite artefact. There exist phenomena whose true algorithmic complexity simply outruns what a given model can compress. The model cannot fully represent them, and cannot certify that they are irreducible. Doubling parameters does not abolish this. It buys a constant on the bound. The world is bigger.
Closely related to Chaitin’s theorem is the celebrated Ω-number, the halting probability of a randomly chosen program on U. Ω is well-defined, but it is also algorithmically random in Martin-Löf’s sense (Solovay, 1975). Its first n bits encode the halting behaviour of all programs of length up to n, and no formal system can prove the values of more than finitely many of its bits. Ω is the most compact possible illustration that algorithmic information has hard ceilings.
The No-Free-Lunch theorem (Wolpert and Macready, 1997)
What the theorem says.
The No-Free-Lunch theorems for search and supervised learning prove that, averaged over the uniform distribution on all possible problems, every learning or optimisation algorithm performs identically.
Restricted to supervised learning: let X be a finite input space, Y a finite output space, and F = Y^X the set of all possible functions from X to Y. Let U be the uniform distribution on F. Then for any two learning algorithms A₁ and A₂ that produce m distinct samples without replacement,
E_{f ~ U} [Loss(A₁, f, m)] = E_{f ~ U} [Loss(A₂, f, m)].
Equivalently, any performance advantage A has over B on some class of problems is exactly compensated by inferiority on the complementary class.
What it rules out for AI.
The dream of a universal learner: a single algorithm that is the best learner for every conceivable problem. There is no such thing. There are learners whose inductive biases are well-aligned with a particular slice of problems, and there are learners whose biases are poorly aligned.
The misleading flavour of NFL is the word “uniform.” It is a theorem about the uniform distribution on all possible functions. The space of all possible functions includes vastly more structureless functions than structured ones, and the uniform distribution puts most of its mass on the structureless ones. Learning is impossible on structureless functions essentially by definition. The mystery is that real learning seems to work anyway. That brings us to the 2024 refinement.
The 2024 refinement (Goldblum, Finzi, Rowan, Wilson)
The 2024 ICML paper “The No Free Lunch theorem, Kolmogorov complexity, and the role of inductive biases in machine learning” gives the cleanest modern reconciliation between NFL and the practical success of deep learning.
The argument has two parts. First, the data distributions that arise in the actual world are not uniform over all possible functions. They are concentrated on a sub-manifold of functions of low Kolmogorov complexity. Natural images, natural language, protein structures, and most other real-world signals are not algorithmically random; they are highly structured.
Second, modern deep learning architectures – convolutional networks, transformers, diffusion models – inherit a simplicity prior that approximates Solomonoff’s universal prior on low-complexity functions. This is partly a consequence of stochastic gradient descent’s implicit regularisation, partly a consequence of architectural choices that bias toward smooth, locally consistent functions.
So NFL does not say AI cannot learn well. It says AI cannot learn universally well. The reason deep learning generalises across vision, language, code, and biology is not that it has escaped NFL; it is that the simplicity prior of modern architectures happens to align with the low-complexity structure of the real-world data we care about.
The structural consequence: every empirical success of AI is the consequence of a happy match between the inductive bias of the architecture and the structure of the data. When the data drifts, the bias becomes a liability. Out-of-distribution generalisation, adversarial robustness, and the long tail of edge cases are exactly the regimes where the simplicity prior stops cooperating with the world. NFL guarantees that some such regime always exists. There is no architecture that escapes it.
Solomonoff induction and AIXI
What the framework says.
Ray Solomonoff defined, in 1964, what is widely regarded as the formal gold standard of inductive inference. The Solomonoff universal prior assigns to every binary string x a probability roughly proportional to 2^{-K(x)}, weighted across all computable hypotheses. The resulting posterior, updated by Bayes’ rule on observed data, is the formally optimal predictor under the assumption that the data-generating process is computable.
Marcus Hutter extended Solomonoff’s framework in 2005 with AIXI, a Bayes-optimal sequential decision agent that uses Solomonoff’s universal prior to choose actions in an unknown environment. Hutter proved optimality properties for AIXI – most notably Pareto optimality – though in technical senses that turned out to be weaker than they first appear.
What it rules out for AI.
The catch is that both Solomonoff’s predictor and AIXI are uncomputable. The universal prior involves summing over all computable hypotheses, weighted by their description length, and that sum is not effectively computable. Equivalently, the Bayesian posterior cannot be computed in finite time; only approximated from below. AIXI is therefore a mathematical ideal rather than an implementable algorithm.
Jan Leike and Marcus Hutter (COLT 2015) sharpened the picture with the notion of bad universal priors. The choice of universal reference machine U is supposedly innocuous – all universal priors differ from one another only by a multiplicative constant. But Leike and Hutter showed that, depending on the choice of U, the convergence of the AIXI agent’s posterior can be made arbitrarily slow, and even ill-behaved in standard environments. The theoretical gold standard is therefore not only uncomputable; in the wrong reference machine, it is also pathological.
The implication is that real systems must approximate. Approximation is not, by itself, a flaw; it is the price of being implementable. But the ceiling is not where the ceiling appeared to be.
The transformer ceiling (Merrill and Sabharwal, 2023-2024)
The most recent layer of the information-ceiling result is structural, not statistical. William Merrill and Ashish Sabharwal, in two papers (TACL 2023 and ICLR 2024), established a tight upper bound on the expressive power of constant-depth, log-precision transformers.
The result, in compressed form: every constant-depth log-precision transformer is simulable by a uniform constant-depth threshold circuit family. In complexity-theory terms, such transformers compute languages in uniform TC⁰. The known containments are TC⁰ ⊆ NC¹ ⊆ L ⊆ P, and each of them is believed – though not yet proven – to be strict.
What this means in practice: no transformer of constant depth and logarithmic precision, regardless of parameter count, can solve P-complete problems in a single forward pass. Classical P-complete problems include the Boolean circuit value problem, Horn-satisfiability, and linear programming. Empirical findings about the limits of LLMs on long-form arithmetic, multi-step planning, and unbounded recursion (Dziri et al., NeurIPS 2023; Liu et al., 2024) are exactly the symptoms of this ceiling.
Chain-of-thought reasoning partially lifts the ceiling. Polynomial-length chains of thought give the model a polynomial-length scratchpad, which raises the expressive class to P (Feng et al., NeurIPS 2023). Unbounded chain-of-thought scratchpads make the model Turing-complete, which is good for expressiveness and immediately bad for undecidability – everything we walked in Chapter 2 applies. There is no free lunch on this dimension either.
For AI this rules out the implicit assumption that scaling a fixed-architecture transformer indefinitely produces a universal computer in a single forward pass. It doesn’t. Universal computation, in the transformer paradigm, requires either unbounded scratchpads or recursive invocation – both of which open the door to all the earlier impossibility results.
The thread
The information ceiling is established by five layered theorems:
- Chaitin says no finite model can certify arbitrarily complex objects.
- NFL says no algorithm is universally best.
- Goldblum et al. say modern architectures work because the world is simple, not because biases come free.
- Solomonoff and AIXI say even the theoretical ideal predictor is uncomputable.
- Merrill-Sabharwal say constant-depth transformers live below P.
Together they describe what real AI is: a remarkable, useful, irreducibly bounded approximation to an unreachable ideal. The bound is structural, not engineering. Doubling parameters does not abolish it; it buys a constant.
Coming next
Chapter 4 closes the series with the value problem. Even granted perfect reasoning, perfect prediction, and perfect learning – none of which we have shown to be available – there remains the question of what AI should optimise. Arrow’s impossibility theorem and the Gibbard-Satterthwaite manipulation theorem will show that the value-aggregation step cannot be reduced to optimisation, ever. The final piece of the ceiling is not technical. It is structural to the very idea of aggregating human preferences.
