Defining Computation to Limit It

In 1936 Alan Turing was trying to answer a question David Hilbert had posed about mathematics: is there a mechanical procedure that, given any mathematical statement, determines whether it is provable?

To show there is not, Turing first had to say what a mechanical procedure is. Nobody had needed a precise definition before.

His answer was a machine so simple it sounds useless. An infinite tape divided into cells. A head that can read and write one symbol at a time and move left or right. A finite table of rules saying what to do given the current state and the symbol under the head.

That is the whole apparatus, and it turns out to be able to compute anything computable. Every programming language ever written, every computer ever built, computes exactly the same set of functions: faster, more conveniently, and not more.

The claim that this is true of any reasonable model of computation is the Church-Turing thesis, and it is a thesis rather than a theorem because "effectively calculable" is an informal notion and cannot be proved equivalent to a formal one. Its support is empirical and considerable: lambda calculus, recursive functions, register machines, cellular automata, quantum computers and every real language have all turned out to reach exactly the same set.

Having defined computation, Turing used it to establish a limit.

The halting problem asks whether there is a program that, given any program and input, determines whether it will eventually finish or run forever. Suppose such a checker exists. Build a program that runs the checker on itself and then does the opposite of what the checker predicts: if the checker says it halts, it loops forever; if the checker says it loops, it halts immediately.

The contradiction means no such checker can exist.

This is not a statement about current technology or about how fast computers are. It is a proof about what computation can do, and a faster machine does not help, because running an impossible procedure faster produces an answer no sooner. The distinction between uncomputable and merely intractable is exactly this: an intractable problem has an algorithm that takes too long, and better hardware genuinely helps with the second and not at all with the first.

Rice's theorem generalises the result uncomfortably far: any non-trivial property of a program's behaviour is undecidable in general. Does this program ever access memory it should not? Does it always terminate? Does it compute the right answer? None of these can be answered by a general procedure.

This matters directly for anybody who has ever wished for a tool that finds all bugs. Such a tool cannot exist, and the impossibility is a theorem rather than an engineering gap. Real static analysers work by being either incomplete (missing some real bugs) or unsound, reporting some things that are not bugs. Every practical tool makes that choice, and knowing it is forced changes what is reasonable to demand from one.

There is a second limit that is practical rather than logical, and it explains why algorithms matter more than hardware.

Sorting a list naively, by comparing every pair, takes a number of operations proportional to the square of the list's length. A good algorithm takes a number proportional to n log n. For a million items that is the difference between roughly a trillion operations and roughly twenty million: a factor of fifty thousand.

No plausible hardware improvement closes a gap of that kind, and the gap widens with every additional item. This is why the analysis of algorithms is about growth rates rather than about constants: an asymptotically better algorithm eventually wins however slow its individual steps are, and the crossover point is usually reached long before the problems get interesting.

Which is also the reason the field's central open question is about growth rates, and why it is worth a million dollars.