If we accept this result, it follows easily that Ackermann's function is not
primitive recursive.
Theorem 13.4
Ackermann's function is not primitive recursive.
Proof: Consider the function
g(i) = A (i, i).
If A were primitive recursive, then so would g. But then, according to
Theorem13.3, there exists an n such that
g(i) < A (n, i),
for all i. If we now pick i = n, we get the contradiction
g (n) = A(n, n)
< A(n, n),
proving that A cannot be primitive recursive.
µ Recursive Functions
To extend the idea of recursive functions to cover Ackermann's function and
other computable functions, we must add something to the rules by which such
functions can be constructed. One way is to introduce the µ or minimalization
operator, defined by
µy (g (x, y)) = smallest y such that g (x, y) = 0.
In this definition, we assume that g is a total function.
Example 13.4