Penser l'algorithmie
TBD chapeau
TBD chapeau commençons par un cas particulier, correspondant à l'arithmétique de Peano et utilisé par Godel pour démontrer ses théorèmes d'incomplétude.
Nous avons vu que les fonctions primitives récursives étaient des fonctions calculable. Nous allons montrer ici qu'un modèle plus générale, les fonctions récursives, sont équivalentes au pseudo-code ! Ceci montre que l'algorithmie peut posséder de nombreuses formes, toutes équivalentes.
Ackermann le retour
TBD à refaire propre TBD Rappeler l'endroit ou est Ackermann dans le cours TBD en faire une partie à part.
La fonction d'Ackermann n'est pas primitive récursive, on va le voir, mais si on fixe son premier paramètre fixé, elle l'est :
Proposition
La fonction $A_m(n) = \text{Ack}(m, n)$ est primitive récursive pour tout $n$.
preuve
preuve
Par récurrence sur $m$.
- $A_0(n) = \text{Ack}(0, n) = n+1$
- 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))$
Retenez bien ce résultat qui peut paraître surprenant, ce n'est pas parce que $A_m(x)$ est primitive récursive pour tout $n$ que $\text{Ack}(m, n)$ l'est. Chaque $A_m(x)$ est construit différemment, on ne peut pas en déduire un schéma général pour construire $\text{Ack}(m, n)$. On retrouvera ce comportement étrange lorsque l'on cherchera à calculer des réels.
La fonction d'Ackermann n'est pas primitive récursive
TBD à refaire.
Ces trois inégalités permettent d'en déduire les 2 inégalités fondamentales suivantes qui montre que la fonction s'emballe très vite calculer les valeurs précédentes d'Ackermann est négligeable par rapport aux valeurs plus grandes :
Montrez que pour tous entiers $(m_i)_{1\leq i \leq k}$ ($k\geq 2$), il existe un entier $m$ tel que :
- $\text{Ack}(m_1, \text{Ack}(m_2, n)) \leq \text{Ack}(m, n)$ pour tout $n \geq 0 $
- $\sum_i\text{Ack}(m_i, n) \leq \text{Ack}(m, n)$ pour tout $n\geq 0$
corrigé
corrigé
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.
La preuve que la fonction d'Ackermann n'est pas récursive primitive est éclairante : on montre qu'elle croit trop vite pour être primitive récursive.
Proposition
Pour toute fonction récursive primitive $f(x_1, \dots, x_n)$ il existe $K_f$ tel que pour tous $(x_1, \dots, x_n) \in \mathbb{R}^n$ :
preuve
preuve
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 :
- la propriété est vérifiée pour les fonctions primitives de base
- 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 :
La proposition précédente montre que toute fonction récursive primitive est majorée par une fonction d'Ackermann, ce qui va nous permettre de conclure la preuve :
Proposition
La fonction d'Ackermann n'est pas récursive primitive.
preuve
preuve
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.