Ackermann's Function
Ackermann's function is a function from I × I to I, defined by
A (0,y) = y +1,
A (x, 0) = A (x – 1,1),
A (x, y +1) = A (x – 1, A (x, y)).
It is not hard to see that A is a total, computable function. In fact, it is quite
elementary to write a recursive computer program for its computation. But in
spite of its apparent simplicity, Ackermann's function is not primitive recursive.
Of course, we cannot argue directly from the definition of A. Even though
this definition is not in the form required for a primitive recursive function, it is
possible that an appropriate alternative definition could exist. The situation here
is similar to the one we encountered when we tried to prove that a language was
not regular or not context-free. We need to appeal to some general property of
the class of all primitive recursive functions and show that Ackermann's function
violates this property. For primitive recursive functions, one such property is the
growth rate. There is a limit to how fast a primitive recursive function f(n) can
grow as n → ∞, and Ackermann's function violates this limit. That Ackermann's
function grows very rapidly is easily demonstrated; see, for example, Exercises 9
to 11 at the end of this section. How this is related to the limit of growth for
primitive recursive functions is made precise in the following theorem. Its proof,
which is tedious and technical, will be omitted.
Theorem 13.3
Let f be any primitive recursive function. Then there exists some integer n such
that
f(i) < A (n,i),
for all i = n, n +1,….
Proof: For the details of the argument, see Denning, Dennis, and Qualitz (1978,
p. 534).
Ackermann's function is a function from I × I to I, defined by
A (0,y) = y +1,
A (x, 0) = A (x – 1,1),
A (x, y +1) = A (x – 1, A (x, y)).
It is not hard to see that A is a total, computable function. In fact, it is quite
elementary to write a recursive computer program for its computation. But in
spite of its apparent simplicity, Ackermann's function is not primitive recursive.
Of course, we cannot argue directly from the definition of A. Even though
this definition is not in the form required for a primitive recursive function, it is
possible that an appropriate alternative definition could exist. The situation here
is similar to the one we encountered when we tried to prove that a language was
not regular or not context-free. We need to appeal to some general property of
the class of all primitive recursive functions and show that Ackermann's function
violates this property. For primitive recursive functions, one such property is the
growth rate. There is a limit to how fast a primitive recursive function f(n) can
grow as n → ∞, and Ackermann's function violates this limit. That Ackermann's
function grows very rapidly is easily demonstrated; see, for example, Exercises 9
to 11 at the end of this section. How this is related to the limit of growth for
primitive recursive functions is made precise in the following theorem. Its proof,
which is tedious and technical, will be omitted.
Theorem 13.3
Let f be any primitive recursive function. Then there exists some integer n such
that
f(i) < A (n,i),
for all i = n, n +1,….
Proof: For the details of the argument, see Denning, Dennis, and Qualitz (1978,
p. 534).