In much the same way, we can define integer division, but we will leave the
demonstration of it as an exercise. If we accept this as given, we see that the
basic arithmetic operations are all constructible by the elementary processes
described. With the algebraic operations precisely defined, other more
complicated ones can now be constructed, and very complex computations built
from the simple ones. We call functions that can be constructed in such a manner
primitive recursive.
Definition 13.1
A function is called primitive recursive if and only if it can be constructed from
the basic functions z, s, p k , by successive composition and primitive recursion.
Note that if g 1 , g 2 , and h are total functions, then f defined by composition
and primitive recursion is also a total function. It follows from this that every
primitive recursive function is a total function on I or I ×I.
The expressive power of primitive recursive functions is considerable, and
most common functions are primitive recursive. However, not all functions are
in this class, as the following argument shows.
Theorem 13.1
Let F denote the set of all functions from I to I. Then there is some function in F
that is not primitive recursive.
Proof: Every primitive recursive function can be described by a finite string that
indicates how it is defined. Such strings can be encoded and arranged in standard