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.
Builds on
Leads to
Not sure where to start? Take the ten-question placement test.