The Debate about Church's Thesis and its Converse: Church's Definition/Thesis and its Epistemological Status (Part 4.2 of Effective Versus Algorithmic Computability)

Part 4.2 available in pdf-format.

Section 4.2 is devoted to the much discussed epistemological status of Church's thesis. First, (4.2.1) the thesis is introduced in the original form, namely as definition, and it is explained where the term 'Church's thesis' comes from. In 4.2.2 the arguments in favor of the thesis/definition, put forward by various authors, are exhibited and discussed. The present author doesn't want to hold back his opinion that Church's step-by-step argument remains to be the best on the market – in opposition to some recent criticism by Sieg, followed by Soare and Schulz.

The epistemological status of the thesis is further examined at full length in Section 4.2.3. After some preliminary remarks on definitions (real and nominal ones, as propositions and as rules) using Weingartner's theory of definition, the early debate among the initiators of computability theory is recollected and analyzed (4.2.3.1). Church, Turing, and Gödel pleaded for 'definition', while Post, Kleene, and Kalmár rejected this view. Already this controversy contained essentially all ingredients of later discussions, up to now. Nothing really new has been contributed since then, as Section 4.2.3.2 shows. In 4.2.3.3 the thesis is compared to other well-known mathematical theses/definitions such as that every circle is the set of all points equidistant to some given point. Also, Quines discussion of the paradigmatic case of the definition of 'ordered pair' (in Word and Object) is examined in order to find some clue what to do with Church's thesis. Further comparisons and analogies are listed in 4.2.3.4, quite a few involving fundamental physical laws. Finally, (un-)provability and refutability of Church's thesis are discussed in Section 4.2.3.5. In 4.2.3.6 a brief resumé is presented.

Classical Computability Theory - Part 2 (of 3)

(Part 2)

This part is concerned with functions definable on arguments which are themselves the indices of an effective enumeration of programs. To this end we provide in detail an effective bijection from the set of register programs to N in Section 2.1.

In 2.2 it is proved that a noneffective bijection from the set of partially register program computable functions to N exists, and that there must exist total number-theoretic functions which are not register program computable. Sections 2.1 - 2-2 here in pdf-Format.

Two kinds of arguments known under the name 'proof by Church's thesis' are introduced in Section 2.3 (here in pdf-Format). First, the use of the thesis for maintaining absolute unsolvability results is treated, including the famous halting predicates. Second, the use of the thesis for the purpose of avoiding tedious proofs is critically commented.

In Section 2.4 three of the most important results in recursion theory are proved, namely (i) the existence of a universal register program which partially computed each n-ary register program computable function (Universality Theorem); (ii) the fact that there is a register program for effectively deciding whether an arbitrary register program eventually halts after some given number of steps (Step-counter Theorem), and (iii) Kleene's famous Normal Form Theorem, saying that each (partial) recursive function can be written in a certain form by means of only p.r. functions and only one application of the µ-operator. It follows that the (partial) recursive are exactly the (partially) register program computable functions. It is also shown that the partial recursive functions may be defined inductively with unbounded minimization restricted to total functions only!

In Section 2.5 the concepts of 'register program (recursive) enumerability' and 'partial decidability' of relations are introduced. Quite a few basic results involving these concepts are proved, e.g. the existence of nonrecursive but recursively enumerable relations, and the Enumeration Theorem for recursively enumerable sets.

Section 2.6 provides a survey of some important recursively decidable problems of recursion theory. These results are easily derived with the help of some prominent theorems: Parameter Theorem, Kleene's Second Recursion Theorem, Fixed Point Theorem, and Rice's Theorem. Sections 2.4 - 2.6 here in pdf-Format.


Finally, it should be well noted that most of the technical details of parts 2 (and 3) are based on the textbooks of Davis and Weyuker [1983] and Cutland [1980], both dealing with register programs and very recommendable.


2             Computations on program numbers (indices)


2.1          Effective denumerability of the set of register programs
2.2          Effective denumerability of the class of partially R-computable functions


2.3          What is a "proof by Church's thesis"?
2.3.1       Typical arguments for the existence of (absolutely) unsolvable problems
                in mathematics - the halting problems for register programs
2.3.2       Avoidable use of Church's thesis


2.4          Universal functions, register programs, and Kleene's Normal Form Theorem
2.5          Recursively enumerable relations and partial decidability
2.6          Parameter Theorem, Second Recursion Theorem, Fixed Point Theorem,
               and Rice's Theorem