The Ackermann function

The Ackermann function is a total function which is computable but not primitive recursive. A number of functions go by this name; a simple one is as follows:
$A(m, n) = \begin{cases}
n + 1 & m = 0
\\ A(m-1, 1) & m > 0 \land n = 0
\\ A(m-1,A(m,n-1)) & m > 0 \land n > 0
\end{cases}$
The rough outline for why $A$ is not primitive recursive is as follows:

Note that $A(4, n) = 2^{2^{\cdots^2}} - 3$ with $n+2$ exponentiations

To be primitive recursive, the function must be defined with a finite number of applications of primitive recursion

However, roughly, each exponentiation requires an application of primitive recursion

Thus, we cannot satisfy all $n$s

Skipping details, the reason that $A$ is not primitive recursive is that it can be shown to grow faster than any primitive recursive function

The Ackermann function is significant because:

It shows that the set of [[primitive recursive]] functions is smaller than the set of [[computable]] functions; i.e., primitive recursion is weaker than computability

Referenced by: