Fonction d'Ackermann

Pour chaque appel récursif de la fonction d'Ackermann, soit $m$, soit $n$ est strictement plus petit dans la fonction appelée que dans la fonction appelante. On arrivera donc toujours à $m = 0$ qui stoppera la récursion ou $n = 0$ qui fera baisser la valeur de $m$. Il n'y aura donc toujours qu'un nombre finie de récursion pour tout couple $(m, n)$.

Par récurrence sur $m$.

1. $A_0(n) = \text{Ack}(0, n) = n+1$
2. si $A_m(n)$ est primitive récursive, $A_{m+1}(n)$ l'est également puisqu'elle est définie par l'opération de récurrence :
   • $A_{m+1}(0) = A_{m}(1)$
   • $A_{m+1}(n+1) = A_{m}(A_{m+1}(n))$

TBD 1. et 2. en appliquant la formule TBD 3. par récurrence sur m et par croissance de la fonction. TBD 4. Par récurrence sur $n$. Pour $n=3$ on a : $2 \uparrow^{(k)} (3+1) = 2 \uparrow^{(k)} (2 \uparrow^{(k+1) 2}) = 2 \uparrow^{(k+1)} (3)$

Commençons par traiter les 2 premiers cas :

• $\text{Ack}(0, n) = n+1$ est vrai par définition
• Comme $\text{Ack}(1, n) = \text{Ack}(0, \text{Ack}(1, n-1)) = \text{Ack}(1, n-1) + 1$ et que $\text{Ack}(1, 0) = \text{Ack}(0, 1) = 2$, une récurrence triviale sur $n$ nous donne $\text{Ack}(1, n) = n+2 = 2 + (n+3) - 3$

Pour le dernier cas, commençons par montrer par récurrence sur $n$ que $\text{Ack}(2, n) = 2 \uparrow^{(0)} (n+3) - 3$ :

• $\text{Ack}(2, 0) = \text{Ack}(1, 1) = 3 = 2 \uparrow^{(0)} (0+3) - 3$
• on suppose la propriété vraie pour $n$. Pour $n+1$ on a $\text{Ack}(2, n+1) = \text{Ack}(1, \text{Ack}(2, n)) = \text{Ack}(2, n) + 2 = 2 \uparrow^{(0)} (n+3) - 1 = 2n + 5$ par hypothèse de récurrence. Comme $2 \uparrow^{(0)} (n+1+3) - 3 = 2n + 5$, ceci conclut la preuve par récurrence.

On peut terminer la preuve en prouvant par récurrence sur $m > 1$ que $\text{Ack}(m, n) = 2 \uparrow^{(m-2)} (n+3) - 3$. On vient de le montrer pour $m=2$, supposons la vraie pour $m$ et prouvons le $m+1$.

Ce que l'on va faire par sur $n$ :

• $\text{Ack}(m+1, 0) = \text{Ack}(m, 1) = 2 \uparrow^{(m-2)} (1+3) - 3$. Comme l'exercice nous a montré que $4 = 2 \uparrow^{(m-1)} (2)$ et comme $2 \uparrow^{(m-2)} (2 \uparrow^{(m-1)} (2)) = 2 \uparrow^{(m-1)} (0+3)$ on a bien $\text{Ack}(m+1, 0) = 2 \uparrow^{(m-1)} (0+3) - 3$
• on suppose la propriété vraie pour $n$. Pour $n+1$ on a $\text{Ack}(m+1, n+1) = \text{Ack}(m, \text{Ack}(m+1, n)) = 2 \uparrow^{(m-2)} (2 \uparrow^{(m-1)} (n+3) - 3+3) - 3$. On conclut en appliquant la formule pour obtenir $\text{Ack}(m+1, n+1) = 2 \uparrow^{(m+1-2)} (n+1 + 3) - 3$

Pour la première partie, si $n=0$ on a $\text{Ack}(m_1, \text{Ack}(m_2, 0)) = \text{Ack}(m_1, \text{Ack}(m_2-1, 1))$. On peut donc toujours se ramener au cas où $n>0$. De là, par croissance de la fonction d'Ackermann dans ses deux variables, on a : $\text{Ack}(m_1, \text{Ack}(m_2, n)) \leq \text{Ack}(\max(m_1, m_2), \text{Ack}(\max(m_1, m_2), n))$. En posant $m_0 = \max(m_1, m_2)$, on a pour $n\geq 0$:

Pour la seconde partie, on a :

Comme $\sum_i\text{Ack}(m_i, n) = \text{Ack}(m_1, n) + \text{Ack}(m_2, n) + \sum_{i>2}\text{Ack}(m_i, n) \leq \text{Ack}(m, n) + \sum_{i>2}\text{Ack}(m_i, n) \leq \text{Ack}(m, n)$ une récurrence triviale permet de conclure.

Comme l'ensemble des fonctions récursives primitives est l'ensemble minimum des fonctions contenant les fonctions primitives de base et stable par composition et récursion, il suffit de montrer que :

1. la propriété est vérifiée pour les fonctions primitives de base
2. la propriété est conservée par composition et récursion

Ce type de récurrence est nommée récurrence structurelle

La première partie de la preuve est claire puisque les fonctions zéros, projections et successeurs sont toutes plus petites que $\text{Ack}(0, \sum_{1\leq i \leq n}x_i) = \sum_{1\leq i \leq n}x_i + 1$

Pour la seconde partie, commençons par montrer que la propriété est stable par composition.

Soient $f: \mathbb{N}^n \to \mathbb{N}$ et $(g_i)_{1 \leq i \leq n}: \mathbb{N}^m \to \mathbb{N}$ des fonctions primitives récursives satisfaisant la propriété. On a alors :

Et finissons par la récursion.

Soient $f: \mathbb{N}^n \to \mathbb{N}$ et $g: \mathbb{N}^{n+2} \to \mathbb{N}$ des fonctions primitives récursives satisfaisant la propriété. Il existe alors $m$ tel que $\text{Ack}(M_g,\text{Ack}(2,n)) \leq \text{Ack}(m,n)$ et on note $M_{\rho^n(f, g)} = \max(m, M_f, M_g) + 1$.

On a alors : $\rho^n(f, g)(0, x_1, \dots, x_n) \leq \text{Ack}(M_f, 0+\sum_{1\leq i \leq n}x_i) \leq \text{Ack}(M_{\rho^n(f, g)}, 0+\sum_{1\leq i \leq n}x_i)$

De là, en supposant que $\rho^n(f, g)(x, x_1, \dots, x_n) \leq \text{Ack}(M_{\rho^n(f, g)}, x+\sum_{1\leq i \leq n}x_i)$ on a :

Comme $ n\leq m+n < \text{Ack}(m, n)$ (on n'avait pas encore utilisé cette inégalité, il fallait bien un jour qu'elle serve) on a :

Si la fonction d'Ackermann était primitive récursive, la fonction : $A(n) = \text{Ack}(n, n) = \text{Ack} \circ [\pi^1_1, \pi^1_1]$ l'est aussi.

Il existe alors $M_A$ tel que $A(n) \leq \text{Ack}(M_A, n)$ pour tout $n$. Ceci est impossible car pour $n = M_A + 1$ on aurait : $A(M_A + 1) \leq \text{Ack}(M_A, M_A + 1) \leq \text{Ack}(M_A + 1, M_A)$ mais comme $A(M_A + 1) = \text{Ack}(M_A + 1, M_A + 1)$ ceci impliquerait $A(M_A + 1) = \text{Ack}(M_A + 1, M_A + 1) \leq \text{Ack}(M_A + 1, M_A)$ ce qui contredit la stricte croissance de la fonction d'Ackermann.