[35] Consider the generalized exponential function f informally having the following property: f(0, x, y) = y + x, f(1, x, y) = y × x, f(2, x, y) = yx, ... . A more formal definition of f is given by f(0, 0, y) =

y, f(0, x + 1, y) = f(0, x, y) + 1, f(1, 0, y) = 0, f(z + 2, 0, y) = 1, f(z +

1, x + 1, y) = f(z,f(z + 1, x, y), y).

(a) Show that this function is computable but not primitive computable.

(b) Show that the function A(x) = f(x, x, x), called the Ackermann generalized exponential function, is computable but not primitive computable. (It rises faster than any primitive computable function.)

Comments. The function f was given by Wilhelm Ackermann (1926) as a first example of a computable function that is not primitive computable [Math. Ann. 99(1928), 118–133]. See also D. Hilbert [Math.

Ann., 95(1926), 161–190], who credits the proof to Ackermann. There are many variants of definitions of the Ackermann function. A common computable definition is A

(0, n) = n + 1; A

(i, 0) = A

(i − 1, 1)

for i ≥ 0; and A

(i, n) = A

(i − 1, A

(i, n − 1)) for i, n > 0 Then A(x) = A

(x, x). This definition is apparently due to R.M. Robinson

[Bull. Amer. Math. Soc. 54(1948), 987–993], and an earlier variant is due to R´ozsa P´eter [Math. Ann. 111(1935), 42–60]. An inherently iterative algorithm to compute A is given by J.W. Grossman and R.Z.

Zeitman [Theoret. Comput. Sci., 37(1988), 327–330]. Another definition for the Ackermann function (Source: [P. Odifreddi, Ibid.]) is hω

defined as follows: h0(x) = x + 1; hn+1(x) = h(x) n (x); hω(x) = hx(x)

where h(0)

n (x) = x; h(z+1) n (x) = hn(h(z) n (x)). One of the advantages of this version is that it can be translated into the transfinite. Note:

h1(x)=2x; h2(x) = x2x.