Church-Turing thesis

Statement

The Church–Turing thesis says: every function that can be computed by an effective procedure (an algorithm) can be computed by a Turing machine. Equivalently, the intuitive notion of "algorithmically computable" coincides with "Turing-computable".

It was proposed independently by Alonzo Church (lambda calculus, 1936) and Alan Turing (Turing machines, 1936). Other formalisations were later shown to be equivalent in power: general recursive functions (Gödel, Kleene), Post systems, unrestricted grammars, register machines, and modern programming languages.

What is an algorithm?

By the thesis, an algorithm is a finite sequence of well-defined mechanical steps that can be carried out by a Turing machine and that halts on every input. A problem is decidable if some TM decides it (a machine that always halts and answers yes or no); a function is computable if some TM computes it.

Why a "thesis" and not a theorem?

• A theorem needs a mathematical proof. Here one side of the statement, "effectively computable", is an informal, intuitive notion with no formal definition, so the claim cannot be proved.
• It can be supported but not proved: every model of computation proposed so far (more than a dozen, such as lambda calculus and RAM machines) has turned out to be equivalent to Turing machines, and no counter-example has ever been found.
• It could in principle be disproved if some more powerful, physically realisable form of computation were discovered, but none is known.

Consequence

Showing that a problem is not solvable by any Turing machine (for example the halting problem) shows that it cannot be solved by any algorithm or program on any computer.