The cycle’s central commitment is to seeing the machine clearly—without either hype or panic. The computability limit is the most rigorous instrument available for one half of that seeing: what the machine can never be. When a claim is made that a sufficiently scaled AI will be able to do ‘anything,’ the Church–Turing thesis allows a precise response: not anything. There is a vast, sharply bounded class of the computable, and the most powerful AI that will ever be built lives entirely inside it. The boundary does not move with parameters, and the problems outside it are not merely hard—they are provably inaccessible to any procedure, which AI is.
The cycle pairs this limit with two other permanent structural properties. Computational irreducibility—Wolfram’s argument that for most complex systems, there is no shortcut—locates a class of problems that are computable but cannot be predicted without running every step. The computability limit locates a class of problems that are not computable at all. Together they map the ceiling of what any AI could ever achieve: powerful within the computable, humbled by irreducibility within it, and bounded absolutely by the limit itself. Understanding where each boundary falls is the beginning of honest assessment.
The limit also clarifies a specific failure mode that recurs in AI discourse: the confusion of ‘hard’ with ‘impossible in principle.’ When an AI system fails at a complex reasoning task, the failure could reflect insufficient training, insufficient architecture, insufficient data, or a provably uncomputable sub-task. Only the last kind of failure is permanent; the others are engineering challenges. Kleene’s hierarchies provide the diagnostic tool for distinguishing them: a problem in the arithmetical hierarchy is computable in principle and the question is whether current systems have learned the relevant function; a problem above the hierarchy is not computable in principle and no improvement of current systems will change that.
The limit was discovered in the 1930s by a group of logicians working independently and converging on the same result. David Hilbert had proposed, in his 1928 Entscheidungsproblem, that there should be a definite procedure for determining the truth or falsity of any mathematical statement. Gödel’s 1931 incompleteness theorems showed that any consistent formal system rich enough to express arithmetic contains true statements it cannot prove—a first demonstration that formal systems have absolute limits. Turing’s 1936 paper on computable numbers and the halting problem showed that no procedure can decide, for every program on every input, whether the program eventually halts. Church independently proved the same result using the lambda calculus. Kleene proved the equivalence of these formulations and developed the detailed structure of what lies beyond the computable boundary.
The convergence of all these independent formalisms on the same class of computable functions—the Church–Turing thesis—was the discovery that ‘computation’ is not a feature of any particular physical substrate or formal notation but a universal property. The same problems are computable by every sufficiently powerful computing system, and the same problems are uncomputable by all of them. This universality is the ground of the computability limit’s permanence: it is not about any particular machine but about the mathematics of what definite procedures can do.
Kleene’s arithmetical hierarchy classifies the uncomputable problems by degree. At the first level are the undecidable problems reducible to the halting problem. At higher levels are problems that would require a procedure equipped with an ‘oracle’ for solving the previous level—problems that are uncomputable even if you had a machine that could solve all halting problems. The hierarchy extends into the transfinite. This is not a curiosity; it is a map of how uncomputable things can be, showing that there is a vast structured territory beyond the computable boundary, not merely a single wall.
The halting problem as prototype. The halting problem is the simplest and most fundamental uncomputable problem: given a program and an input, does the program eventually halt? Turing proved no procedure decides this for all cases. The proof proceeds by diagonalization: assume a halting decider exists, construct a program that halts if and only if the decider says it will not, and derive a contradiction. Every AI system encounters this limit whenever it is asked to determine, in full generality, what another program will do—a task that appears in code analysis, formal verification, and any sufficiently general reasoning about computation itself.
Scale cannot cross the boundary. The computability limit is not a function of model size, training data, or computational resources. A trillion-parameter model cannot solve an uncomputable problem any more than a thousand-parameter model can, because the obstacle is not insufficient capacity but a mathematical theorem about the class of functions that procedures can compute. When claims are made that sufficiently large models will acquire any capability, the computability limit is the rigorous refutation: not any capability, and the exceptions are not edge cases but an infinite, structured territory.
Practical implications for AI assessment. The limit has immediate implications for how AI capabilities should be assessed. A system that fails at a task might be failing because the task is genuinely uncomputable in the required generality, in which case no improvement of the system will help; or because the specific function the task requires has not been learned, in which case better training might help; or because the task falls in the computationally irreducible region where the function is computable but no shortcut exists. Distinguishing these failure modes requires understanding which side of the computability boundary the task falls on—a question that Kleene’s framework is designed to answer.
Gödel’s incompleteness as companion result. Gödel’s incompleteness theorems are the logical companion to Turing’s undecidability: there are true mathematical statements that no formal system can prove. Stephen Hawking reflected on what this implied for the dream of a final theory of physics, speculating that the search for complete understanding might run up against Gödelian limits. Applied to AI: a system is itself a formal system, subject to the same limits. There are mathematical truths the system can encode but cannot prove, and no scaling produces a system that has escaped this structural feature of formal knowledge. AI extends what can be computed; it does not extend what can be formally established.