Church?Turing thesis

In computability theory the Church?Turing thesis, Church's thesis, Church's conjecture or Turing's thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers.

Success of the thesis

Since that time many other formalisms for describing effective computability have been proposed, including recursive functions, the lambda calculus, register machines, Post systems, combinatory logic, and Markov algorithms. All these systems have been shown to compute essentially the same functions as Turing machines; systems like this are called Turing-complete. Because all these different attempts of formalizing the concept of algorithm have yielded equivalent results, it is now generally assumed that the Church?Turing thesis is correct. However, the thesis is a definition and not a theorem, and hence cannot be proved true. It could, however, be disproved if a method could be exhibited which is universally accepted as being an effective algorithm but which cannot be performed on a Turing machine.

Related Topics:
Recursive function - Lambda calculus - Register machine - Post system - Combinatory logic - Markov algorithm - Turing-complete - Theorem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In the early twentieth century, mathematicians often used the informal phrase effectively computable, so it was important to find a good formalization of the concept. Modern mathematicians instead use the well-defined term Turing computable (or computable for short). Since the undefined terminology has faded from use, the question of how to define it is now less important.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The success of the Church–Turing thesis prompted supertheses that extend the thesis, including the conjecture that there is a polynomial transformation from the representation of computable functions in one formalization to their representation in another, and the conjecture that every model of computation can be step-by-step simulated by a Turing machine.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~