Church's Thesis

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 variablesrange over the natural numbers, andis any predicate. This schema asserts that, if for everythere is asatisfying some predicate, then there is in fact anwhich is the Gödel number of a general recursive function which will, for everyproduce 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.

You have no rights to post comments