Ackermann : ce qui décroît quand rien ne décroît

1. Le troisième cas est celui qui résiste.

else ackermann (m - 1) (ackermann m (n - 1))

L'appel interne est ackermann m (n - 1) : $m$ n'a pas bougé. L'appel externe est ackermann (m - 1) v où $v$ est la valeur rendue par l'appel interne — et cette valeur est en général beaucoup plus grande que $n$. Ni $m$ ni $n$ ne décroît donc à chaque appel, et aucun variant entier construit sur l'un ou l'autre ne peut fonctionner.

2. Le couple $(m,n)$ décroît pour l'ordre lexicographique sur ${\mathbb{N}}^2$, qui est bien fondé. Les trois appels :

La dernière ligne est le cœur de l'affaire : l'ordre lexicographique permet à la seconde composante d'exploser pourvu que la première baisse. C'est ce qu'aucun ordre produit ne permettrait — $(m-1,v)$ et $(m,n)$ sont incomparables pour le produit dès que $v>n$.

3. Les formes closes, obtenues et vérifiées par le calcul :

$$A(1,n)=n+2,A(2,n)=2n+3,A(3,n)=2^{n+3}-3.$$

Valeurs mesurées : $A(2,\mathrm{0..4})=3,5,7,9,11$ ; $A(3,\mathrm{0..4})=5,13,29,61,125$ ; et $A(3,6)=509=2^9-3$.

Le prix de la terminaison. Le nombre d'appels a été compté :

et $A(3,6)=509$ demande $172233$ appels. La fonction termine pour tout couple — c'est démontré — et pourtant $A(4,2)$ compte $19729$ chiffres. Terminaison et faisabilité sont deux questions différentes, et l'ordre bien fondé ne répond qu'à la première.