From Logic to Physics: How the Meaning of Computation Changed over Time.

The common formulation of the Church-Turing thesis runs as follows: Every computable partial function is computable by a Turing machine Where by partial function I mean a function from a subset of natural numbers to natural numbers. As most textbooks relate, the thesis makes a connection between an intuitive notion (computable function) and a formal one (Turing machine). The claim is that the definition of a Turing machine captures the pre-analytic intuition that underlies the concept computation. Formulated in this way the Church-Turing thesis cannot be proved in the same sense that a mathematical proposition is provable. However, it can be refuted by an example of a function which is not Turing computable, but is nevertheless calculable by some procedure that is intuitively acceptable. [ABSTRACT FROM AUTHOR]