Church-Turing Thesis

"An envisioned computation is said to be feasible if it would consume only a quantity of resources that does not exceed what is likely to be available to the computational process." - R. Gregory Taylor.

Introduction

Alonzo Church's λ-calculus paper and Alan Turing's "Machines" paper in 1936 connected the informal notion of an algorithm or computable function to a more precise definition. Turing defined a machine showing that this machine, which is now called a Turing machine, can compute anything that can be intuitively computed. In 1931, Kurt Gödel first introduced a set of functions that he called recursive. In 1934, Stephen Kleene was able to generalize Gödel’s recursive functions. Then in 1936, Church made a similar connection to Turing, in that anything that can be intuitively computed can be expressed in terms of general recursive functions. Thus, Church and Turing both related the philosophical notion of effectively computable to the formal notion of Turing and Recursively computable.

There are actually three computability paradigms that are connected together, but are not provably connected, hence the term thesis.  We have the (1) machines paradigm from Turing, the (2) recursive functions from Church and (3) languages that emerged after Church and Turing.

Church's Thesis

A function ¦ is recursive iff ¦ is total and effectively computable. A function ¦ is partially recursive iff ¦ is effectively computable.

Turing's Thesis

Turing claimed the following notion in 1936:

A (number-theoretic) function f is effectively computable iff function ¦ is Turing-computable.

which can be shown in two parts:

1. If function ¦ is effectively computable, then function ¦ is Turing-computable.
2. If function ¦ is Turing-computable, then function ¦ is effectively computable.

The first part is not intuitively obvious but the second part is. Any (number-theoretic) function can be either Turing-computable or not Turing-computable. The Church-Turing thesis, although is not a proof of algorithm, it remains true in the philosophical sense, since it hasn't been disapproved. The class of Turing-computable functions is identical to the class of effectively computable functions.

Church-Turing Thesis

So, finally the Church-Turing thesis states the following:

Function ¦ is effectively computable iff ¦ is partial recursive or ¦ is Turing-computable.

Links

http://plato.stanford.edu/entries/church-turing/
http://cognet.mit.edu/MITECS/Entry/sieg2
http://mathworld.wolfram.com/Church-TuringThesis.html
http://www.alanturing.net/turing_archive/pages/Reference%20Articles/The%20Turing-Church%20Thesis.html