Church-Turing Thesis

Algorithm equals Turing-computable: what the thesis claims and why.

The idea

Church-Turing thesis. A function is computable by an algorithm — an effective, mechanical, step-by-step procedure that a person could in principle carry out with paper and pencil — if and only if some Turing machine computes it.

One side of the claim, some Turing machine computes it, is a precise mathematical condition. The other, there is an algorithm, is an informal notion with no definition at all. A statement with an undefined notion on one side cannot be proved, which is what the word thesis records: it is a proposal for how to formalize an informal idea, not a theorem awaiting proof.

The evidence for it is convergence. Turing machines, Church's lambda-calculus, the general recursive functions, register machines, and every later mechanical formalization compute exactly the same class of functions, with routine translations between them. A class so indifferent to the choice of formalism is a strong candidate for the true notion of computability.

The thesis does not say that every function is computable — there are uncountably many functions and only countably many machines — only that wherever there is an algorithm there is a Turing machine, and conversely. In practice it licenses prose: once the identification is accepted, describing a procedure in ordinary words counts as specifying a machine, which is why proofs in this subject are written in words rather than transition tables.

Ways to work on it

• Walkthrough. What the thesis asserts, why it is a thesis, and the evidence for it.
• Practice. Judge a statement against what the thesis does and does not claim.
• Hardest. Separate the thesis from diagonal non-computability and the extended (efficiency) thesis.

Not sure where to start? Take the ten-question placement test.