When we say that a problem "cannot be solved by any algorithm", we make a very strong claim. To make it precise we need a mathematical definition of algorithm. The Church-Turing thesis states that the functions computable by an effective mechanical procedure are exactly those computable by a Turing machine. It is the bridge between an intuitive idea, "a procedure that can be carried out step by step", and a formal object. Here I examine it as a concept, together with the alternative models that support it.
Why it is a thesis and not a theorem
A theorem connects two mathematical objects. The Church-Turing thesis connects a mathematical object, the Turing machine, to an informal notion, that of an effective procedure. It cannot be proved in the strict sense, because one of the two terms has no rigorous definition. One can only gather evidence for it.
The main evidence is striking: models of computation developed independently, from very different starting ideas, all turned out to be equivalent to the Turing machine. Nobody has ever proposed a reasonable model, that is one physically realizable with finite, deterministic steps, that computes anything more.
First model: the lambda calculus
The lambda calculus has no tapes and no states. It has only functions. Terms are built with three rules:
- a variable x is a term;
- an abstraction λx.M is a term: the function mapping x to M;
- an application (M N) is a term: the function M applied to the argument N.
Computation proceeds by a single rule, β-reduction: (λx.M) N is rewritten as M with N in place of x. For example (λx.x x) y reduces to y y.
There are no numbers, but they can be encoded. In Church's encoding the number n is the function that applies its first argument n times to its second:
0 = λf.λx. x
1 = λf.λx. f x
2 = λf.λx. f (f x)
successor = λn.λf.λx. f (n f x)
Similar encodings represent booleans, pairs, lists and recursion (through fixed-point combinators). The upshot is that the functions on natural numbers definable in the lambda calculus are exactly those computable by a Turing machine.
Second model: recursive functions
This approach starts from basic functions on the natural numbers and closes the set under a few operations.
Basic functions: the constant zero, the successor n ↦ n + 1, and projections returning one of their arguments.
Operations:
- composition: from f and g obtain f(g(x));
- primitive recursion: define h(x, 0), and h(x, n + 1) in terms of h(x, n), like a for loop with a known number of iterations;
- minimization (the μ operator): μy[f(x, y) = 0] is the smallest y for which f is zero, found by trying y = 0, 1, 2, …
Without minimization we get the primitive recursive functions, which always terminate: addition, multiplication, exponentiation, factorial and almost everything used in practice. But not every computable total function is primitive recursive: the Ackermann function grows too fast to be one.
With minimization, which corresponds to a while loop with no known bound, we get the μ-recursive functions, which may fail to terminate. They coincide with the Turing-computable functions. The difference between a for loop and a while loop is, in this sense, the difference between guaranteed termination and full computational power.
Third model: register machines
A register machine has finitely many registers, each holding an arbitrary natural number, and a program of numbered instructions:
- INC r: increment register r;
- DEC r, k: if r is positive decrement it, otherwise jump to instruction k;
- HALT.
These three instructions suffice to compute everything a Turing machine computes. In fact two registers are enough with a suitable encoding of the data. The model is close to the architecture of real processors.
Turing completeness
A system is Turing complete if it can simulate any Turing machine, given enough memory. All general-purpose programming languages are Turing complete, but so are unexpected systems: some cellular automata, such as Conway's Game of Life, and various mechanisms built for other purposes, such as certain macro and template systems.
The practical consequence is twofold:
- a Turing-complete system can express any computation;
- a Turing-complete system inherits every undecidability: for its programs termination cannot be decided in general, nor, by Rice's theorem, any non-trivial semantic property.
This is why designers of configuration formats, query languages or filter rules sometimes deliberately choose a language that is not Turing complete: they give up some expressiveness to gain guarantees, such as termination of every evaluation.
What the thesis does not say
The thesis concerns what can be computed, not at what cost. Models equivalent for computability may differ greatly in efficiency. There is an "extended" version of the thesis, according to which every reasonable model can be simulated by a Turing machine with at most polynomial slowdown; this version is far more debated, and quantum computing is the main reason for doubt.
In short
- The Church-Turing thesis identifies effective computation with computation by Turing machines.
- It cannot be proved, since it links an intuitive notion to a formal one, but the equivalence of many models supports it.
- Lambda calculus, μ-recursive functions and register machines compute exactly the same functions.
- Primitive recursive functions always terminate but do not cover everything: Ackermann lies outside.
- A Turing-complete system gains full expressiveness at the price of every undecidability.
