Vipul: Created page with "{{intuition-to-formalism bridge thesis}} ==Statement== The '''Church-Turing thesis''' states that if a computation can be effectively carried out by some machine, then it can b..."

2011-12-28T02:44:33Z

Created page with "{{intuition-to-formalism bridge thesis}} ==Statement== The '''Church-Turing thesis''' states that if a computation can be effectively carried out by some machine, then it can b..."

New page

{{intuition-to-formalism bridge 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:

# [[Turing machine]]s
# [[lambda-calculus]]
# 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.

Church-Turing thesis - Revision history

Vipul: Created page with "{{intuition-to-formalism bridge thesis}} ==Statement== The '''Church-Turing thesis''' states that if a computation can be effectively carried out by some machine, then it can b..."