Classical Computability Theory Part 1 (of 3)

(Part 1)

After some introductory historical remarks, the theory of primitive recursive (p.r.) functions is presented rather in detail (1.1). An inductive definition, similar to the one of Gödel [1931], is given first (1.1.1). Some simplifications of the schemata PR and CN are derived in Sections 1.1.2 – 1.1.3. Primitive recursiveness of functions is extended to sets and relations in Section 1.1.4. In 1.1.5 it is shown that the common techniques of bounded mini- and maximization for defining number theoretical notions does not lead out of the class of p.r. functions. In 1.1.6 it is shown that various more powerful-seemingly operations do not lead out of this class, too - simultaneous primitive recursion, course-of-values recursion and iteration. Additional results of this sort are mentioned – recursion in which substitutions are made for parameters, multivariable recursion (e.g. ordinary double recursion), nested simple recursion, and bounded nested recursion. In each of the sections already mentioned a lot of examples are provided. In Section 1.1.7.1 sort of scale functions are introduced. 9 of 10 facts about them are proved.
In 1.1.7.2 it is proved that these functions grow (in a certain defined sense) faster than any p.r. function. This must give us a hint that these computable functions are essentially different to the p.r. ones. Additionally it is sketched how to use them to obtain the so-called Grzegorczyk-hierarchy of the p.r. functions, thereby introducing the concepts of bounded primitive recursion and of elementary function. Sections 1.1.1 - 1.1.7 here in pdf-Format.

Section 1.2 deals with computable functions "beyond the p.r. limit". In 1.2.1 a simple variant A of Ackermann's original function is defined by means of the scale functions and it is shown by a diagonal argument that A cannot be p.r. (A is called 'Ackermann-Péter-Robinson function' due to Péter's and Robinson's simplifications of Ackermann's original function.) In Section 1.2.2 two of the most important concepts of recursion and computability theory are introduced: arithmetization and diagonalization of function classes. Arithmetization of a (countable) set is accomplished by carrying out a Gödel-numbering (or effective encoding). Then it is shown how to encode effectively the class of p.r. functions in order to define a computable diagonal function leading out of this class. This is done in Section 1.2.2.1. In 1.2.2.2 the multiply recursive functions are introduced, i.e. the functions obtained by n-fold nested recursion. It is sketched how to proceed the Grzegorczyk-hierarchy by successively adding n-fold nested recursion schemata. So what we finally obtain along these lines is an infinite union of effectively computable total functions. And the question remains – do we already have all the computable functions?

In Section 1.2.3, finally, the possibilities of introducing the operation of unbounded minimization (or the µ-operator) are discussed. The distinction between unbounded minimization and regular unbounded minimization defines the difference between the sets of partial µ-recursive and µ-recursive functions. That is, by the introduction of the unrestricted µ-operator one drops the requirement for computable functions to be totally defined. This is certainly a paradigmatic change and its importance for the further development of computability is remarkable. Finally it is proved that the function A can be obtained by regular minimization (such that it is µ-recursive). Section 1.2 here in pdf-Format.

Section 1.3 deals with an alternative characterization of the p.r. functions, namely the so-called Loop programs. Syntax and semantics of these programs are provided in detail (Section 1.3.1). First examples are given in 1.3.2 and the technical basis for the use of macros is given in 1.3.3. In Section 1.3.4 it is proved that every p.r. function can be computed by some Loop program (with many additional examples), while in Section 1.4 the converse is shown by an elegant proof using simultaneous primitive recursion. Sections 1.3 - 1.4 here in pdf-Format.

Ad Section 1.5 (here in pdf-Format): After some introductory historical remarks on Gödel's general recursive functions, the sets of recursive and partial recursive functions are introduced by inductive definitions in 1.5.1, and some basic result are proved.
Section 1.5.2 is devoted to an alternative characterization of (partial) recursive functions, namely register programs (or Shepherdson-Sturgis machines). Syntax, semantics and the use of macros is treated in 1.5.2.1 – 1.5.2.2. In 1.5.2.3 – 1.5.2.4 many examples are exhibited and it is proved that the (partial) recursive functions are all computable by register programs.

1            Computations on positive integers

1.1          Primitive recursive functions

1.1.1       An inductive definition of the primitive recursive functions

1.1.2       The problem of avoiding 0-ary functions

1.1.3       Some derived substitution and primitive recursion schemata

1.1.4       Primitive recursive sets, relations, and predicates

1.1.5       Bounded mini- and maximization

1.1.6       Some extended primitive recursion schemata

1.1.7       The scale functions

1.1.7.1    Ten facts about the scale functions

1.1.7.2    The scale functions dominate the primitive recursive functions

1.2          Effectively computable functions, not primitive recursive

1.2.1       The Ackermann-Péter-Robinson function A

1.2.2       Arithmetization and diagonalization of function classes

1.2.2.1    A non primitive recursive diagonal function

1.2.2.2    Multiply recursive functions

1.2.3       Unbounded minimization – a step to partial recursive functions

1.3          Loop programs

1.3.1       The programming language

1.3.1.1    The syntax of L

1.3.1.2    The semantics of L

1.3.2       First examples of loop programs

1.3.3       The use of macros in L

1.3.4       Further examples and theorems

1.4          The class of L-computable functions is exactly the class of primitive

               recursive Functions

1.5          Recursive and partial recursive functions

1.5.1       An inductive definition of the partial recursive functions

1.5.2       Register programs

1.5.2.1    The programming language R

1.5.2.1.1 The syntax of R

1.5.2.1.2 The semantics of R

1.5.2.2    The use of macros in R

1.5.2.3    Each primitive recursive function is R-computable

1.5.2.4    Further examples and theorems