Church's thesis is the mathematical assertion that all total functions are recursive.
One way Church's Thesis can be formally stated is by the schema:A number-theoretic function is computable if there is an algorithm, or mechanical procedure, that computes it. The procedure should specify what is to be done at each step, as a function of the input only, without involving any creativity on the part of the agent. Computability is an informal, or pre-formal, notion in that it has meaning independently of, and prior to, its formal development.
A function is recursive, for example, if its values can be derived from a fixed set of equations in a certain form. It is reasonably clear that every recursive function is computable, since an algorithm can be ‘read off’ a recursive derivation or a Turing machine. Church's thesis is the assertion that a function is computable if and only if it is recursive, Turing-computable, etc.
Formally we may write
Where the variables
range over the natural numbers, and
is any predicate. This schema asserts that, if for every
there is a
satisfying some predicate, then there is in fact an
which is the Gödel number of a general recursive function which will, for every
produce such a y satisfying that predicate. (T is some universal predicate which decodes the Gödel-numbering used.)
The thesis is incompatible with classical logic. For instance, it is a classical tautology that every Turing machine either halts or does not halt on a given input; but if that were true, then from Church's Thesis one would conclude that there is a general recursive function which solves the halting problem. This is impossible.