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