(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.1 The programming language
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.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