Ackermann function is not primitive recursive

Remarks

The key lemma is a domination result. For every primitive recursive $f \colon \N^k \to \N$ there is $m \in \N$ such that $f(\bar x) < A(m, \max \bar x)$ for all $\bar x \in \N^k$. It is proved by induction on the construction of $f$, using that $A$ is increasing in each argument. If $A$ were primitive recursive, so would be $g(n) = A(n, n)$. Then some $m$ would give $A(n, n) < A(m, n)$ for all $n$, which fails at $n = m$.

The theorem shows that the class of primitive recursive functions is strictly smaller than the class of total computable functions. Computability of $A$ follows from the fact that the recursion decreases the pair $(m, n)$ in the lexicographic order.

Going deeper

For a student

Each primitive recursive function is dominated by one level $n \mapsto A(m, n)$ of the Ackermann function. The diagonal $n \mapsto A(n, n)$ escapes every level, so it is outside the class. This is a diagonal argument, like the one that shows that no effective list of total computable functions contains all of them. To reach all computable functions one adds unbounded search, which gives the general recursive functions.