La fonction d’Ackermann

Ici on s’attaque à un des exercices les plus classiques en matière de terminaison d’algorithme. On présente une fonction récursive et le but est de montrer qu’un algorithme calculant cette fonction termine.

Exercice

La fonction d’Ackermann est une fonction de $\mathbb{N}^{2}$ dans $\mathbb{N}$ et est définie par : \[A(m,\:n) = \begin{cases} n+1& \text{ si }m=0\\ A(m-1,\:1) & \text{ si }m\gt 0 \text{ et }n=0\\ A(m-1, A(m,\:n-1)) & \text{ si }m\gt 0 \text{ et }n\gt 0 \end{cases}\]

$1)$ Munir $\mathbb{N}^{2}$ d’un ordre bien fondée.

$2)$ En déduire que la fonction d’Ackermann est bien définie.

---

Correction

$1.$ Considérons l’ordre lexicographique $\lt_{lex}$ définie par :
\[(x,y) \lt_{lex} (x’,y’) \Leftrightarrow x\lt x’ \text{ ou } ( x=x’ \text{ et } y\lt y’ )\]

Prouvons que cet ordre est bien fondée. Nous proposons deux méthodes utilisant les deux définitions équivalentes de l’ordre bien fondée.

Première méthode : montrons qu’il n’existe pas de suite infinie strictement décroissante Par l’absurde, supposons qu’une telle suite existe. Appelons-là $\displaystyle (u_n)_{n\in\mathbb{N}}$. Soit $u_0 = (x,y)$. On note que les éléments de $(u_n)$ sont de la forme $(k,k’)$ avec $0 \leq k \leq x$. Notre suite étant infinie et le nombre de possibilité pour le premier élément étant finie, on a $K \in \mathbb{N}$ tel qu’on ait une infinité d’élément de $(u_n)_{n\in\mathbb{N}}$ de la forme $(K,k’)$. Ainsi, on a $\varphi$ une extractrice de $\mathbb{N}$ telle que la suite $(u_{\varphi(n)})$ soit strictement décroissante et n’ait que des valeurs de la forme $(K,k’)$. On pose $u_{\varphi(0)} = (K,K’)$. Or, nous n’avons que $K’+1$ éléments distincts compris entre $(K,K’)$ et $(K,0)$, ce qui contredit l’hypothèse de stricte décroissance. Ainsi, $\lt_{lex}$ définit bien un ordre bien fondé sur $\mathbb{N}^{2}$.

Deuxième méthode : montrons que pour tout sous ensemble de $\mathbb{N}^{2}$, il existe un élément strictement minimal au sens de l’ordre $\leq_{lex}$. Pour cela, il suffit de considérer un ensemble de $\mathbb{N}^{2}$ et de considérer le sous-ensemble constitué des éléments dont le premier élément du $2$-uplet est minimale. Puis, on prend le plus petit élément dans cet ensemble par rapport à la seconde composante, ce qui est possible dans les deux cas car $(\mathbb{N},\lt )$ est bien fondée. On a bien exhibé un plus petit élément, donc $(\mathbb{N}^{2},\lt_{lex})$ est bien fondé.

---

$2)$ Prouvons à présent que la fonction d’Ackermann est bien définie. On peut considérer notre définition comme un algorithme récursif et la question est alors de savoir si notre programme termine. Pour le prouver, on procède par induction sur l’entrée.

Tout d’abord, si $m=0$, $A(m,n)$ termine en une étape.

Soit $(m,n) \in \mathbb{N}^{*}\times\mathbb{N}$. On suppose que la fonction d’Ackermann termine sur tout $(k,l)\lt_{lex}(m,n)$. Montrons qu’elle termine sur l’entrée $(m,n)$. Si $n=0$, Ackermann termine sur $(m-1,1)$ donc termine sur $(m,n)$. Sinon, par hypothèse d’induction, $A(m,n-1)$ existe et le calcul termine. De plus $(m-1,A(m,n-1))\lt_{lex}(m,n)$. Ainsi, toujours par hypothèse d’induction, notre fonction termine sur l’entrée $(m-1,A(m,n-1))$ et donc termine sur $(m,n)$. Cela prouve donc le cas $(m,n)$ et achève la récurrence.

Nous avons donc prouvé que la fonction d’Ackermann est bien définie.