In computability theory the Church–Turing thesis (also known as Church's thesis, Church's conjecture and Turing's thesis) is a combined hypothesis about the nature of effectively calculable (computable) functions by recursion (Church's Thesis), by mechanical device equivalent to a Turing machine (Turing's Thesis) or by use of Church's λ-calculus:
Church's Thesis: "Every effectively calculable function (effectively decidable predicate) is general recursive" (Kleene 1952:300)
Turing's Thesis: "Turing's thesis that every function which would naturally be regarded as computable is computable under his definition, i.e. by one of his machines, is equivalent to Church's thesis by Theorem XXX." (Kleene 1952:376)
The three computational processes (recursion, λ-calculus, and Turing machine) were shown to be equivalent by Alonzo Church, Stephen Kleene and J.B. Rosser (1934-6) and by Alan Turing (1936-7). Although Stephen Kleene proved the two theses equivalent, the fundamental premise behind the theses — the notion of "effectively computable" or "effectively calculable" — is "a vague intuitive one" based as it is on (i) “heuristic [observational, experiential] evidence”, (ii) the “equivalence of 'diverse formulations'” (e.g. the three computational processes) and (iii) on an observational analysis of a human with a pencil and paper following a set of rules (Turing's analysis) and of a "worker" in boxes (Emil Post's analysis 1936). Thus, as they stand, neither thesis can be proven. The various notions for "effective calculability/computability" — the fly in the ointment — have been proposed as a "formal definition" by Church, Turing and Rosser, as a "working hypothesis" leading by inductive reasoning to a "natural law" by Post (an idea "sharply" criticized by Church), or as an axiom or set of axioms (suggested by Kurt Gödel to Church in 1934-5 but discounted in Post 1936).
Today the thesis has near-universal acceptance.
Informally the Church–Turing thesis states that if an algorithm (a procedure that terminates) exists then there is an equivalent Turing Machine or applicable λ-function for that algorithm.
Reference:
http://en.wikipedia.org/wiki/Church-turing_thesis
