6. Show that
f(n) = 2 n
is primitive recursive.
7. Show that the function
g (x,y) = x y
is primitive recursive.
8. Write a computer program for computing Ackermann's function. Use it to
evaluate A (2, 5) and A (3, 3).
9. Prove the following for the Ackermann function.
(a) A (1, y) = y + 2.
(b) A (2, y) = 2y + 3.
(c) A (3, y) = 2 y+3 – 3.
10. Use Exercise 9 to compute A (4,1) and A (4, 2).
11. Give a general expression for A (4,y).
12. Show the sequence of recursive calls in the computation of A (5, 2).
13. Show that Ackermann's function is a total function in I × I.
14. Try to use the program constructed for Exercise 8 to evaluate A (5, 5). Can
you explain what you observe?
15. For each g below, compute µy(g (x,y)), and determine its domain.
(a) g (x ,y) = xy.
(b) g (x ,y) = 2 x + y – 3.
(c) g (x , y) = integer part of (x – 1) / (y +1).
(d) g (x , y) = x mod(y + 1).
16. The definition of pred in Example 13.3, although intuitively clear, does not
strictly adhere to the definition of a primitive recursive function. Show how
the definition can be rewritten so that it has the correct form.