La fonction d'Ackermann est récursive

(i) Par récurrence sur $m$, et, pour chaque $m$, par récurrence sur $n$, l'énoncé portant sur toutes les suites $u$.

Pour $m = 0$, une étape mène à $u\, (n + 1) = u\, A(0, n)$.

Pour $m + 1$ et $n = 0$, une étape mène à $u\, m\, 1$ ; l'hypothèse de récurrence sur $m$ la conduit à $u\, A(m, 1) = u\, A(m + 1, 0)$, en passant par des piles $u\, v$ avec $v$ de longueur au moins $2$.

Pour $m + 1$ et $n + 1$, une étape mène à $u\, m\, (m + 1)\, n$. L'hypothèse de récurrence sur $n$, appliquée à la suite $u\, m$, conduit à $u\, m\, A(m + 1, n)$ ; l'hypothèse sur $m$, appliquée à la suite $u$, conduit enfin à $$\begin{aligned} &u\, A\big(m, A(m + 1, n)\big) \\ &\quad = u\, A(m + 1, n + 1). \end{aligned}$$ Les piles intermédiaires s'écrivent $u\, m\, v$ puis $u\, v'$, avec $v$ et $v'$ de longueur au moins $2$.

(ii) Codons les piles par les codes de suites de Codages. La fonction $E$ qui envoie le code d'une pile sur celui de la pile obtenue après une étape est primitive récursive : avec les notations de ce nœud, si $N$ code $u\, m\, n$, alors $n = \mathrm{dr}(N)$, $m = \mathrm{dr}(\mathrm{dbt}(N))$, et $u$ a pour code $\mathrm{dbt}(\mathrm{dbt}(N))$. Les trois cas, et le cas $\mathrm{lg}(N) \leqslant 1$, sont des relations primitives récursives, et dans chacun le résultat s'obtient par la fonction d'ajout ; on conclut par la définition par cas (Clôture, (ii)).

Les itérés $E^t(N)$, définis par récurrence primitive sur $t$, sont primitifs récursifs en $(N, t)$. D'après (i), appliqué à la suite vide, la pile $\langle m, n \rangle$ atteint $\langle A(m, n) \rangle$, et c'est la première pile de longueur $1$ qu'elle rencontre. Ainsi $$A(m, n) = \mathrm{dr}\Big(E^{\tau}\big(\langle m, n \rangle\big)\Big),$$ avec $\tau = \mu t\, \big[\mathrm{lg}\big(E^t(\langle m, n \rangle)\big) = 1\big]$, qui existe toujours. C'est une fonction récursive totale par le point (iii) de Fonctions récursives. Elle n'est pas primitive récursive (Ackermann).