The Church–Turing Thesis and the Limits of Computation

Three mathematicians, working separately, asked what it means to “compute” something. Their answers agreed exactly — and revealed an entire landscape of problems no machine will ever solve.

In the spring of 1936, three papers landed in three different journals. Alonzo Church at Princeton had invented the λ-calculus, a notation for defining functions by pure substitution. Stephen Kleene was formalising the μ-recursive functions, building up computable functions from a handful of arithmetic primitives. And a young British student named Alan Turing was describing an imaginary machine with a tape and a head.

None of them had seen the others' work in time. Each had set out to capture, in mathematical terms, the everyday idea of an effective procedure: something a clerk with paper and rules could carry out, given long enough, with no creativity required. And each had produced what looked like an entirely different definition.

Then someone noticed something strange. The three definitions defined exactly the same set of functions. Anything you could compute in one, you could compute in the others. Three roads, three landscapes, same destination.

One idea behind three faces

That convergence is what the Church–Turing thesis is really about. It is not a theorem — you cannot prove it in the strict sense, because one of its terms (“effectively computable”) is informal. It is a conjecture about the match between an intuitive notion and a precise one. It says:

Any function that can be calculated by a finite, mechanical procedure can be calculated by a Turing machine.

The reason it is taken so seriously, despite being unprovable, is the embarrassment of agreement. Since 1936, dozens of other formalisms have been proposed: register machines, cellular automata, tag systems, combinatory logic, Markov algorithms, modern programming languages. Every single one, when its computational power is carefully measured, lands on the same set of functions. A different definition has never produced more.

It is as if three groups of cartographers, mapping wilderness from opposite directions, had each drawn the same coastline without ever comparing notes. At some point you stop suspecting accident and start believing the coastline is real.

The first impossible problem

The thesis tells you what computation is. The next question is what it cannot do. And the answer, also from 1936, is surprisingly precise: some perfectly well-posed questions cannot be answered by any machine that will ever be built.

The cleanest example is the halting problem. Given a program P and an input x, will P eventually stop, or will it run forever? It sounds like the kind of thing a clever enough analyser should crack. Sometimes it can — for many programs we can tell. But Turing proved that no general algorithm exists. No future compiler, no future AI, no future mathematician with infinite patience can ever produce a method that always works for every program.

The proof is a short, perfect piece of self-reference. Suppose, for contradiction, that a halt-detector H exists: feed it the source code of any program P and an input x, and it answers “halts” or “loops.” Then build a small mischief-maker D. D takes a single argument, a program P, and does the following: it asks H what P would do if given its own source code; then D does the opposite.

Now feed D its own source code. If H claims D halts on itself, D loops; if H claims D loops on itself, D halts. Either way, H is wrong. So H cannot exist. The halting problem is undecidable.

This is not a statement about today's computers being too slow. It is a statement about the structure of computation itself. Build a faster machine, run it for longer, throw more researchers at it — nothing helps. The wall is logical, not technological.

A wider landscape of the uncomputable

Once the halting problem fell, others tumbled out behind it. Rice's theorem, proved in 1953, generalises the result startlingly: every non-trivial property of a program's behaviour is undecidable. You cannot in general decide if two programs compute the same function, whether a program ever prints “hello”, whether it is virus-free, whether it terminates on at least one input. These are not edge cases. They are the rule.

Elsewhere, Hilbert's tenth problem — is there an algorithm to decide whether a polynomial equation with integer coefficients has integer solutions? — was answered by Yuri Matiyasevich in 1970. The answer is no, and the route runs through Turing's argument. Tarski's high-school algebra problem, the word problem for groups, the determination of whether a given tile set can cover the plane: all uncomputable.

The busy beaver function offers perhaps the most vivid demonstration. Define BB(n) as the largest number of steps a halting Turing machine with n states can run before stopping. BB grows faster than any computable function. BB(5) is at least 47,176,870 and is now known exactly; BB(6) was recently shown to exceed a tower of exponentials thousands of layers high; BB(7) and beyond are forever sealed off. We can prove they exist. We cannot, ever, write them down.

What the thesis does not say

It is easy to over-read all this. Three clarifications.

First, the Church–Turing thesis is about what can be computed in principle, with unlimited time and memory. It says nothing about efficiency. Whether a problem is solvable in polynomial time, whether P equals NP — these are questions of complexity, not computability. A problem can be perfectly decidable and yet require more steps than there are atoms in the universe.

Second, the thesis is about a single Turing machine viewed mathematically. There is a related but distinct claim — the physical Church–Turing thesis — that asks whether any physical process whatsoever could compute something a Turing machine cannot. Some exotic proposals (relativistic “hypercomputers” that exploit black-hole geometries, machines that pack infinitely many steps into finite time) attempt to break the barrier. None has ever been built, and most physicists doubt the universe permits them.

Third, undecidability does not mean unknowability. We can prove, of any specific program, what it does, often quite easily. What is impossible is the universal procedure that handles every program at once. There is room for cleverness in every individual case. Just no general method to settle them all.

That is the picture the thesis leaves us with. Computation is one definite thing, the same in every formalism. Inside its boundary lies a vast country of solvable problems — arithmetic, search, simulation, much of mathematics. And outside it, mapped only by the proofs that show we cannot enter, lies a larger country still: the questions whose answers exist, whose meaning is clear, and which no machine will ever decide for us.