CONCEPT
The Computability Limit
The permanent mathematical boundary—established by Turing, Church, and
Kleene in the 1930s—beyond which no procedure can go: a vast landscape of well-defined problems that no AI, however large, will ever reliably solve, because the obstacle is logical rather than technological.
Before the first electronic computer was built, a small group of logicians proved that some problems can never be solved by any definite procedure, regardless of how much time or memory is available.
Alan Turing’s 1936 proof that the halting problem is undecidable—that no procedure can determine, for every possible program on every possible input, whether it will ever halt—established the boundary with mathematical precision.
Stephen Kleene’s subsequent development of the arithmetical and hyperarithmetic hierarchies mapped this boundary in fine detail, classifying problems by how uncomputable they are, by how far beyond any procedure they lie. The convergence of the lambda calculus, Turing’s machine, and Kleene’s general recursive functions on the same class of computable functions—the Church–Turing thesis—established that this class is not an artifact of any particular formalism but a universal feature of effective computation. Every AI system is computation in precisely this sense. It inherits, without exception, all the powers and