<<

. 5
( 10 .)



>>

Composition. The ¬rst of our methods for assembling computable
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.

<<

. 5
( 10 .)



>>