functions from simpler ones should be thoroughly familiar from many

parts of mathematics.

Definition 14.2. Suppose that m, k ≥ 1, g is an m-place function,

and h1, . . . , hm are k-place functions. Then the k-place function f is

said to be obtained from g, h1 , . . . , hm by composition, written as

f = g —¦ (h1 , . . . , hm ) ,

if for all (n1 , . . . , nk ) ∈ Nk ,

f(n1 , . . . , nk ) = g(h1 (n1 , . . . , nk ), . . . , hm (n1 , . . . , nk )).

29

30 14. PRIMITIVE RECURSIVE FUNCTIONS

Example 14.1. The constant function c1 , where c1 (n) = 1 for all

1 1

n, can be obtained by composition from the initial functions S and O.

For any n ∈ N,

c1 (n) = (S —¦ O)(n) = S(O(n)) = S(0) = 0 + 1 = 1 .

1

Problem 14.2. Suppose k ≥ 1 and a ∈ N. Use composition

to de¬ne the constant function ck , where ck (n1 , . . . , nk ) = a for all

a a

(n1 , . . . , nk ) ∈ N , from the initial functions.

k

Proposition 14.3. Suppose that 1 ¤ k, 1 ¤ m, g is a Turing

computable m-place function, and h1, . . . , hm are Turing computable

k-place functions. Then g —¦ (h1 , . . . , hm ) is also Turing computable.

Unfortunately, one can™t do much else of interest using just the

initial functions and composition . . .

Proposition 14.4. Suppose f is a 1-place function obtained from

the initial functions by ¬nitely many applications of composition. Then

there is a constant c ∈ N such that f(n) ¤ n + c for all n ∈ N.

Primitive recursion. Primitive recursion boils down to de¬ning

a function inductively, using di¬erent functions to tell us what to do

at the base and inductive steps. Together with composition, it su¬ces

to build up just about all familiar arithmetic functions from the initial

functions.

Definition 14.3. Suppose that k ≥ 1, g is a k-place function, and

h is a k + 2-place function. Let f be the (k + 1)-place function such

that

1. f(n1 , . . . , nk , 0) = g(n1 , . . . , nk ) and

2. f(n1 , . . . , nk , m + 1) = h(n1 , . . . , nk , m, f(n1, . . . , nk , m)

for every (n1 , . . . , nk ) ∈ Nk and m ∈ N. Then f is said to be obtained

from g and h by primitive recursion.

That is, the initial values of f are given by g, and the rest are given

by h operating on the given input and the preceding value of f.

For a start, primitive recursion and composition let us de¬ne addi-

tion and multiplication from the initial functions.

Example 14.2. Sum(n, m) = n + m is obtained by primitive re-

cursion from the initial function π1 and the composition S —¦ π3 of initial

1 3

functions as follows:

• Sum(n, 0) = π1 (n);

1

• Sum(n, m + 1) = (S —¦ π3 )(n, m, Sum(n, m)).

3

14. PRIMITIVE RECURSIVE FUNCTIONS 31

To see that this works, one can proceed by induction on m:

At the base step, m = 0, we have

1

Sum(n, 0) = π1 (n) = n = n + 0 .

Assume that m ≥ 0 and Sum(n, m) = n + m. Then

Sum(n, m + 1) = (S —¦ π3 )(n, m, Sum(n, m))

3

3

= S(π3 (n, m, Sum(n, m)))

= S(Sum(n, m))

= Sum(n, m) + 1

= n + m + 1,

as desired.

As addition is to the successor function, so multiplication is to

addition.

Example 14.3. Mult(n, m) = nm is obtained by primitive recur-

sion from O and Sum —¦ (π3 , π1 ):

3 3

• Mult(n, 0) = O(n);

• Mult(n, m + 1) = (Sum —¦ (π3 , π1 ))(n, m, Mult(n, m)).

3 3

We leave it to the reader to check that this works.

Problem 14.5. Use composition and primitive recursion to obtain

each of the following functions from the initial functions or other func-

tions already obtained from the initial functions.

1. Exp(n, m) = nm

2. Pred(n) (de¬ned in Problem 13.1)

3. Diff(n, m) (de¬ned in Problem 13.1)

4. Fact(n) = n!

Proposition 14.6. Suppose k ≥ 1, g is a Turing computable k-

place function, and h is a Turing computable (k + 2)-place function. If

f is obtained from g and h by primitive recursion, then f is also Turing

computable.

Primitive recursive functions and relations. The collection of

functions which can be obtained from the initial functions by (possibly

repeatedly) using composition and primitive recursion is useful enough

to have a name.

Definition 14.4. A function f is primitive recursive if it can be

de¬ned from the initial functions by ¬nitely many applications of the

operations of composition and primitive recursion.

32 14. PRIMITIVE RECURSIVE FUNCTIONS

So we already know that all the initial functions, addition, and

multiplication, among others, are primitive recursive.

Problem 14.7. Show that each of the following functions is prim-

itive recursive.

1. For any k ≥ 0 and primitive resursive (k + 1)-place function g,

and Πm g(n1 , . . . , nk , i), the (k + 1)-place function f given by

i=0

f(n1 , . . . , nk , m) = Πm g(n1 , . . . , nk , i)

i=0

= g(n1 , . . . , nk , 0) · . . . · g(n1 , . . . , nk , m)

for any (k + 1)-tuple (n1 , . . . , nk , m).

0 n=a

2. For any constant a ∈ N, χ{a}(n) =

1 n = a.

f(n1 , . . . , nk ) (n1 , . . . , nk ) = (c1 , . . . , ck )

3. h(n1 , . . . , nk ) = , if

a (n1 , . . . , nk ) = (c1 , . . . , ck )

f is a primitive recursive k-place function and a, c1, . . . , ck ∈ N

are constants.

Theorem 14.8. Every primitive recursive function is Turing com-

putable.

Be warned, however, that there are computable functions which are

not primitive recursive.

We can extend the idea of “primitive recursive” to relations by using

their characteristic functions.

Definition 14.5. Suppose k ≥ 1. A k-place relation P ⊆ Nk is

primitive recursive if its characteristic function

1 (n1 , . . . , nk ) ∈ P

χP (n1 , . . . , nk ) =

0 (n1 , . . . , nk ) ∈ P

/

is primitive recursive.

Example 14.4. P = {2} ‚ N is primitive recursive since χ{2} is

recursive by Problem 14.7.

Problem 14.9. Show that the following relations and functions are

primitive recursive.

1. ¬P , i.e. Nk \ P , if P is a primitive recursive k-place relation.

2. P ∨ Q, i.e. P ∪ Q, if P and Q are primitive recursive k-place

relations.

3. P § Q, i.e. P © Q, if P and Q are primitive recursive k-place

relations.

14. PRIMITIVE RECURSIVE FUNCTIONS 33

4. Equal, where Equal(n, m) ⇐’ n = m.

m

5. h(n1 , . . . , nk , m) = i=0 g(n1 , . . . , nk , i), for any k ≥ 0 and prim-

itive recursive (k + 1)-place function g.

6. Div, where Div(n, m) ⇐’ n | m.

7. IsPrime, where IsPrime(n) ⇐’ n is prime.

8. Prime(k) = pk , where p0 = 1 and pk is the kth prime if k ≥ 1.

9. Power(n, m) = k, where k ≥ 0 is maximal such that nk | m.

10. Length(n) = , where is maximal such that p | n.

11. Element(n, i) = ni , if n = pn1 . . . pnk (and ni = 0 if i > k).

1 k

nj

ni ni+1

if 1 ¤ i ¤ j ¤ k

pi pi+1 . . . pj

12. Subseq(n, i, j) = , whenever

0 otherwise

n = pn1 . . . pnk .

1 k

13. Concat(n, m) = pn1 . . . pnk pm1 . . . pml , if n = pn1 . . . pnk and

1 1

k k+1 k+ k

m

m1

m = p1 . . . p .

Parts of Problem 14.9 give us tools for representing ¬nite sequences

of integers by single integers, as well as some tools for manipulating

these representations. This lets us reduce, in principle, all problems

involving primitive recursive functions and relations to problems in-

volving only 1-place primitive recursive functions and relations.

Theorem 14.10. A k-place g is primitive recursive if and only if

the 1-place function h given by h(n) = g(n1 , . . . , nk ) if n = pn1 . . . pnk

1 k

is primitive recursive.

Note. It doesn™t matter what the function h may do on an n which

does not represent a sequence of length k.

Corollary 14.11. A k-place relation P is primitive recursive if

and only if the 1-place relation P is primitive recursive, where

(n1, . . . , nk ) ∈ P ⇐’ pn1 . . . pnk ∈ P .

1 k

Computable non-primitive recursive functions. While primi-

tive recursion and composition do not su¬ce to build up all Turing com-

putable functions from the initial functions, they are powerful enough

that speci¬c counterexamples are not all that easy to ¬nd.

Example 14.5 (Ackerman™s Function). De¬ne the 2-place function

A from as follows:

• A(0, ) = S( )

• A(S(k), 0) = A(k, 1)

• A(S(k), S( )) = A(k, A(S(k), ))

Given A, de¬ne the 1-place function ± by ±(n) = A(n, n).

34 14. PRIMITIVE RECURSIVE FUNCTIONS

It isn™t too hard to show that A, and hence also ±, are Turing

computable. However, though it takes considerable e¬ort to prove it,

± grows faster with n than any primitive recursive function. (Try

working out the ¬rst few values of ± . . . )

Problem 14.12. Show that the functions A and ± de¬ned in Ex-

ample 14.5 are Turing computable.

If you are very ambitious, you can try to prove the following theo-

rem.

Theorem 14.13. Suppose ± is the function de¬ned in Example

14.5 and f is any primitive recursive function. Then there is an n ∈ N

such that for all k > n, ±(k) > f(k).

Corollary 14.14. The function ± de¬ned in Example 14.5 is not

primitive recursive.

. . . but if you aren™t, you can still try the following exercise.

Problem 14.15. Informally, de¬ne a computable function which

must be di¬erent from every primitive recursive function.

CHAPTER 15

Recursive Functions

We add one more computable method of building functions, un-

bounded minimalization, to our repertoire. The functions which can

be de¬ned from the initial functions using unbounded minimalization,

as well as composition and primitive recursion, turn out to be precisely

the Turing computable functions.

Unbounded minimalization. Unbounded minimalization is the

counterpart for functions of “brute force” algorithms that try every

possibility until they succeed. (Which, of course, they might not . . . )

Definition 15.1. Suppose k ≥ 1 and g is a (k + 1)-place func-

tion. Then the unbounded minimalization of g is the k-place function

f de¬ned by

f(n1 , . . . , nk ) = m where m is least so that g(n1 , . . . , nk , m) = 0.

This is often written as f(n1 , . . . , nk ) = µm[g(n1, . . . , nk , m) = 0].

Note. If there is no m such that g(n1 , . . . , nk , m) = 0, then the

unbounded minimalization of g is not de¬ned on (n1 , . . . , nk ). This is

one reason we will occasionally need to deal with partial functions.

If the unbounded minimalization of a computable function is to be

computable, we have a problem even if we ask for some default out-

put (0, say) to ensure that it is de¬ned for all k-tuples. The obvious

procedure which tests successive values of g to ¬nd the needed m will

run forever if there is no such m, and the incomputability of the Halt-

ing Problem suggests that other procedure™s won™t necessarily succeed

either. It follows that it is desirable to be careful, so far as possible,

which functions unbounded minimalization is applied to.

Definition 15.2. A (k + 1)-place function g is said to be regular

if for every (n1, . . . , nk ) ∈ Nk , there is at least one m ∈ N so that

g(n1 , . . . , nk , m) = 0.

That is, g is regular precisely if the obvious strategy of computing

g(n1 , . . . , nk , m) for m = 0, 1, . . . in succession until an m is found

with g(n1 , . . . , nk , m) = 0 always succeeds.

35

36 15. RECURSIVE FUNCTIONS

Proposition 15.1. If g is a Turing computable regular (k + 1)-

place function, then the unbounded minimalization of g is also Turing

computable.

While unbounded minimalization adds something essentially new to

our repertoire, it is worth noticing that bounded minimalization does

not.

Problem 15.2. Suppose g is a (k + 1)-place primitive recursive

regular function such that for some primitive recursive k-place function

h,

µm[g(n1, . . . , nk , m) = 0] ¤ h(n1, . . . , nk )

for all (n1 , . . . , nk ) ∈ N. Show that µm[g(n1, . . . , nk , m) = 0] is also

primitive recursive.