Church's Thesis

Church's thesis is that the recursive functions, recursively decidable, enumerable sets are the (intuitively) computable functions, decidable sets, enumerable sets.

The thesis concerns a notion that is not mathematically defined, and so it is not subject to proof. There are several arguments for it, I'll highlight two.

The thesis is analogous to the thesis that a circle (in the intuitive sense) is the set of all points the same distance from a single point in a plane.

One might, by analogy, try to show that the thesis is true by a detailed analysis of the intuitive notion. That is what Turing's paper in which he introduced Turing machines attempts.

Church gave an empirical argument: look at all these attempts to capture the notion of procedure. They start from different conceptions, and they all yield the same result. The notion is so stable, it has to be the right one.

Some examples of ways people defined recursive. First two remarks:

1. We can use symbols or numbers indifferently: Numbers base n and a set of n symbols amount to the same thing, and so we can move back and forth freely.
2. We can define recursive functions, decidable sets, enumerable sets in terms of each other, and so you can take any one as basic.

Examples of definitions:

1. Various sorts of machines: Turing machines, register machines, deterministic machines, so-called nondeterministic machines (that is, branching machines), machines that answer to the formal specifications of modern computer languages.
2. Grammars: Thue grammars, semi-Thue grammars.
3. Arithmetic definitions. A bounded quantifier is a quantifier like this: %$\forall m<n$% or %$\exists m<n$%. A %$\Sigma$% formula is a formula in the language of arithmetic that has existential quantifiers at the front and all the rest of the quantifiers bounded.
   1. The sets of natural numbers definable by %$\Sigma$% formulas are exactly the r.e. sets.
   2. Existential followed by recursive also yields r.e.
   3. Existential followed by primitive recursive also yields r.e., where a primitive recursive function is one definable from 0,%$S$% using the following scheme, in which %$F$% is primitive recursive:
      1. %$f(0,a_{1},\dots , a_{m})=k,$%
      2. %$f(Sn,a_{1}\dots , a_{m})=F(a_{1},\dots ,a_{m},n,<f(0),f(1),\dots , f(n)>)$%
   4. Instead of existential primitive recursive to define r.e. sets, one can use "%$\mu x$%"--least %$x$% such t hat--followed by recursive or primitive recursive to yield the recursive functions.
   5. Systems of arithmetic equations to be solved yield the r.e. sets. More precisely, write down a system of equations using + and %$\cdot$% and look at the values for a fixed variable %$x_0$% for which the equations can be solved. One can allow inequalities too.
      1. It is even true that this works for a single polynomial and even a single polynomial in 13+1 variables. This was never taken to be a definition of r.e.; it is highly nontrivial to prove that it is strong enough. If you allow exponentiation into the equations, it is easy, and was proposed as a definition.
      2. You can also use a list of equations in 4+1 variables.
      3. There is even a single equation %$p(x,y,a_{0},\dots ,a_{13})=0$% that you can actually write down such that for every r.e. set there is a %$y$% such that the set is the set of %$x$%s that work for that %$y$%.
4. Proof-theoretic. In a language that includes 0 and %$S$% A set is r.e.if and only if there is a set of axioms and a formula %$\phi$% such that %$n$% is in the set if and only if you can prove %$\phi (S^{n}0)$% on the basis of the axioms.
   1. One can also pick single suitable sets of axioms. Examples: Arithmetic, set theory, theory of hereditarily finite sets, theories of some ugly semigroups.

-- ProfessorShaughanLavine - 31 Jan 2005