The Church-Turing Thesis
The Church-Turing thesis claims that any function computable by any effective procedure is computable by a Turing machine.
The claim
The thesis states that the informal notion of "a task that can be carried out by a mechanical, rule-following procedure" coincides exactly with the formal notion of "computable by a Turing machine." It is a bridge between an intuitive idea and a precise mathematical model.
Why it is a thesis, not a theorem
It cannot be proved, because one side of the equation is informal. What supports it is convergence: every independent formalization of computation ever proposed turns out to define the same class of computable functions.
- Turing machines
- Church's lambda calculus
- Godel's general recursive functions
- Register machines and modern programming languages
Evidence from convergence
Church and Turing worked separately in the 1930s with completely different formalisms, and both defined the same set of functions. Every reasonable model since has matched. That robustness is the strongest argument for accepting the thesis.
The strong (complexity) version
A stronger form claims that any physically realizable computer can be simulated by a Turing machine with only polynomial slowdown. Quantum computing challenges this efficiency form: a quantum machine may solve some problems far faster than any known classical simulation, which is why BQP matters. It does not challenge the basic thesis, since a Turing machine can still compute the same functions, just slowly.
What it does not say
The thesis does not say every function is computable. It says the computable ones are exactly the Turing-computable ones. Vast numbers of functions, including the halting function, lie outside that boundary.