La fonction d'Ackermann n'est pas primitive récursive

(i) Par le principe d'induction de Primitives récursives, il suffit de vérifier la propriété sur les fonctions de base et de montrer qu'elle se conserve. On emploie sans le dire la croissance de $A$ en chaque variable (Croissance d'Ackermann, (ii) et (iii)).

Fonctions de base. $Z(x) = 0 < A(0, x)$, $P^n_i(x) \leqslant |x| < A(0, |x|)$, et $S(x) = x + 1 < x + 2 = A(1, x)$.

Composition. Soit $h = f(g_1, \dots, g_m)$, avec $f(u) < A(k_0, |u|)$ et $g_j(x) < A(k_j, |x|)$, et $k$ le plus grand des $k_j$, pour $0 \leqslant j \leqslant m$. Le $m$-uplet $u = (g_1(x), \dots, g_m(x))$ vérifie $|u| < A(k, |x|)$, d'où, par le point (v) du lemme, $$\begin{aligned} h(x) &< A(k, |u|) < A\big(k, A(k, |x|)\big) \\ &< A(k + 2, |x|). \end{aligned}$$

Récurrence primitive. Soit $h(x, 0) = f(x)$ et $h(x, y + 1) = g(x, y, h(x, y))$, avec $f(x) < A(k_f, |x|)$ et $g(u) < A(k_g, |u|)$. Posons $k = \max(k_f, k_g) + 1$, et montrons par récurrence sur $y$ que $$h(x, y) < A(k, |x| + y).$$

Pour $y = 0$, c'est l'hypothèse sur $f$. Supposons-le pour $y$. Les trois entiers $|x|$, $y$ et $h(x, y)$ sont strictement inférieurs à $A(k, |x| + y)$, par (i) du lemme et par l'hypothèse. Comme $k_g \leqslant k - 1$, $$\begin{aligned} h(x, y + 1) &< A\big(k - 1, A(k, |x| + y)\big) \\ &= A(k, |x| + y + 1). \end{aligned}$$

Enfin $|x| + y \leqslant 2|(x, y)| < 2|(x, y)| + 3 = A(2, |(x, y)|)$, d'où, par (v) du lemme, $$\begin{aligned} h(x, y) &< A\big(k, A(2, |(x, y)|)\big) \\ &< A\big(\max(k, 2) + 2, |(x, y)|\big). \end{aligned}$$

Sans paramètre, $h(0) = a$ et l'on prend $k_f = a$, puisque $A(a, 0) \geqslant a + 1$ par la croissance en $x$ ; le même calcul s'applique avec $|x| = 0$.

(ii) Si $A$ était primitive récursive, la fonction $d(x) = A(P^1_1(x), P^1_1(x)) = A(x, x)$ le serait aussi, par composition. Par (i), il existerait $k$ tel que $A(x, x) < A(k, x)$ pour tout $x$ ; pour $x = k$, on obtiendrait $A(k, k) < A(k, k)$.