The Ackermann function $A(n,m)$ is defined on the natural numbers by a very simple recursion, but the values grow enormously, almost beyond conception. This function completely transcends any simple-minded system of rates-of-growth based on polynomial, exponential, double-exponential and so on.
The first few values of the diagonal function $A(n) = A(n,n)$ are:
- $A(0) = 1$
- $A(1) = 3$
- $A(2) = 7$
- $A(3) = 61$
- $A(4) = 2^{2^{2^{65536}}}-3$
- $A(5)$ is vast, and can be described in terms of exponential stacks of $2$s, whose height is a stack of $2$s, etc. 5 times.
- $A(6)$ is so vast, it is best described using the Ackermann function itself.
The levels of the Ackerman function $A_n(m)=A(n,m)$ stratify the primitive recursive functions, in the sense that they are each primitive recursive, but every primitive recursive function is bounded by such a level of the Ackermann function. Thus, the Ackermann function itself is not primitive recursive, although it is computable in the sense of computability theory.
