fonction d'Ackermann

Imaginez un compteur organisé en rangées. Dans la première, il ajoute simplement 1. Dans la suivante, chaque résultat devient l'entrée du calcul suivant. Plus on descend, plus les appels s'emboîtent avant de rendre un nombre.

Ainsi, A(2, 0) vaut 3, puis A(2, 1) vaut 5 et A(2, 2) vaut 7. Ces débuts modestes cachent une croissance vertigineuse dès que le premier nombre augmente. La fonction d'Ackermann montre qu'une règle peut toujours finir et rester calculable, tout en dépassant toute construction par récursion primitive.

La fonction d'Ackermann associe un entier naturel à chaque couple d'entiers naturels. Le premier argument est noté m et le second n. Sa valeur A(m, n) est fixée par trois clauses :

Le cas m = 0 arrête la récursion. Dans les deux autres cas, le premier argument finit par diminuer. Lorsque n est positif, il faut toutefois calculer un appel intérieur avant de pouvoir lancer l'appel extérieur. Cette imbrication définit une valeur pour toute paire (m, n), même si l'évaluation directe devient vite impraticable.

La fonction est totale et calculable : un algorithme peut, en principe, produire chaque valeur. Elle n'est pourtant pas récursive primitive : aucune définition obtenue seulement par composition et récursion primitive ne donne cette fonction à deux variables. Plus précisément, la fonction diagonale qui associe n à A(n, n) finit par dépasser toute fonction récursive primitive d'une variable. Le prototype historique comportait trois variables ; la forme à deux variables est associée aux travaux ultérieurs de Rózsa Péter et Raphael Robinson.

La définition repose sur quatre éléments liés. Le domaine fournit deux entiers naturels m et n. Le cas de base, lorsque m vaut 0, renvoie le successeur de n et met fin à une branche de calcul. Le cas de bord, lorsque n vaut 0 et m est positif, remplace le couple par (m − 1, 1). Le cas imbriqué, lorsque les deux arguments sont positifs, calcule d'abord A(m, n − 1), puis utilise ce résultat comme second argument d'un appel dont le premier argument vaut m − 1.

Le cas de base dépend donc de la descente du premier argument, tandis que l'appel extérieur dépend du résultat complet de l'appel intérieur. Ces règles suffisent à construire chaque valeur. Ce sont l'imbrication et la réutilisation des résultats, non la lettre A ni la disposition graphique, qui caractérisent cette version de la fonction.

Calculons A(2, 2) en appliquant uniquement les trois clauses de la définition.

Données :
le premier argument vaut m = 2 ;
le second argument vaut n = 2 ;
A(0, n) = n + 1, donc A(1, n) = n + 2.

1. Au bord, A(2, 0) = A(1, 1) = 3.
2. Ensuite, A(2, 1) = A(1, A(2, 0)) = A(1, 3) = 5.
3. Enfin, A(2, 2) = A(1, A(2, 1)) = A(1, 5) = 7.

Le résultat est donc A(2, 2) = 7. Pour le contrôler, on peut établir par récurrence que A(2, n) = 2n + 3 : en remplaçant n par 2, on retrouve 2 × 2 + 3 = 7. La figure récapitule la chaîne 3, 5, 7 produite par les appels emboîtés.

Dans un cours de programmation, la fonction sert à éprouver une compréhension de la récursion imbriquée. Tracer les appels de A(2, 2) révèle immédiatement si le résultat intérieur est bien calculé avant l'appel extérieur. Pour apprendre la récursion ordinaire, une factorielle reste toutefois plus lisible.

En théorie de la calculabilité, elle fournit un témoin concret lorsqu'il faut séparer fonctions calculables et fonctions récursives primitives. Une croissance rapide seule ne suffit pas : c'est la preuve de domination de toute fonction récursive primitive qui établit la séparation.

Pour tester un évaluateur récursif, de petites entrées peuvent exposer la profondeur de pile et le coût des appels répétés. Dès que m atteint 4, il vaut mieux raisonner symboliquement sur les formules connues que tenter un calcul naïf.

Une fonction récursive au sens informatique s'appelle elle-même dans sa définition. Une fonction récursive primitive appartient à une classe formelle plus restrictive. La fonction d'Ackermann est récursive dans le premier sens, calculable, mais elle n'appartient pas à cette classe restrictive.

La fonction inverse d'Ackermann mesure combien il faut remonter dans une croissance de type Ackermann pour atteindre ou dépasser une valeur. Ici, on retient la convention α(n) = min {m ∈ ℕ | A(m, m) ≥ n}. Elle croît extrêmement lentement. Rencontrer α(n) dans l'analyse d'un algorithme ne signifie donc pas que cet algorithme calcule A(m, n).

La convention choisie compte. Plusieurs fonctions dites d'Ackermann emploient des valeurs initiales ou un décalage d'indices différents. Avant de comparer deux nombres, il faut vérifier les trois clauses utilisées, et pas seulement le nom A.

L'exposant doit être recalculé. Avec les clauses affichées ici, A(3, n) = 2^{n + 3} − 3. Comme A(4, 1) = 65 533, on obtient A(4, 2) = A(3, 65 533) = 2^{65 536} − 3. L'exposant 65 533 parfois recopié est incompatible avec cette convention.

Une valeur gigantesque reste calculable en principe. L'impossibilité pratique de développer A(4, 2) en écriture décimale ne rend pas la fonction indécidable. Il faut distinguer l'existence d'un algorithme qui termine pour chaque entrée des ressources nécessaires à son exécution.

Une implémentation naïve peut échouer avant le calcul mathématique. Un dépassement de pile ou de mémoire décrit la machine et la méthode choisies, pas une absence de valeur. Une formule fermée pour une rangée basse ou une représentation symbolique évite alors de dérouler tous les appels.

La fiche fonction calculable précise ce que signifie l'existence d'un algorithme qui termine sur toute entrée.

La fiche fonction récursive distingue l'auto-appel en programmation des classes formelles étudiées en calculabilité.

La fiche suite de Goodstein présente un autre phénomène où des processus élémentaires atteignent des tailles extrêmes.