Church-Turing thesis

Statement

The Church-Turing thesis states that if a computation can be effectively carried out by some machine, then it can be carried out by any of these equivalent machines or formalisms:

1. Turing machines
2. lambda-calculus
3. recursive definition

Note that (1)-(3) are known to be equivalent in terms of the power of things they can express and compute. What the Church-Turing thesis states is that any thing that can be effectively calculated is equivalent to all of these.

The Church-Turing thesis is a thesis that bridges between an intuitive notion of effective computability and a formal model of computation. It cannot be proved in this form, because the intuitive notion of effective computability has no prior formal definition. However, if a reasonable notion of effective computability is postulated that cannot be carried out by a Turing machine, then that would disprove the Church-Turing thesis.