Fonction d'Ackermann

Dans les années 1920, Wilhelm Ackermann et Gabriel Sudan, alors étudiants sous la direction de David Hilbert, étudient les fondements de la calculabilité. Sudan est le premier à donner un exemple de fonction récursive mais non récursive primitive, appelée alors fonction de Sudan. Peu après et indépendamment, en 1928, Ackermann publie son propre exemple de fonction récursive mais non récursive primitive[1]. À l'origine, Ackermann considère une fonction ϕ(m, n, p) dépendant de trois variables.

Ackermann démontre que sa fonction ϕ est bien récursive, c'est-à-dire une fonction qu'un ordinateur idéalisé peut calculer. Dans Sur l'infini[2], David Hilbert conjecture que la fonction d'Ackermann n'est pas récursive primitive. Cette conjecture est établie par Ackermann lui-même dans son article « Zum Hilbertschen Aufbau der reellen Zahlen »[3]. Sur l'infini est l'article le plus important de Hilbert sur les fondements des mathématiques, servant de cœur à son programme pour fixer la base des nombres transfinis.

Une fonction de seulement deux variables est donnée plus tard par Rózsa Péter et Raphael Robinson ; c'est cette dernière qui est connue aujourd'hui sous le nom de fonction d'Ackermann.

La fonction d'Ackermann-Péter est définie récursivement comme suit :

${\displaystyle A(m,n)={\begin{cases}n+1&{\mbox{si }}m=0\\A(m-1,1)&{\mbox{si }}m>0{\mbox{ et }}n=0\\A(m-1,A(m,n-1))&{\mbox{si }}m>0{\mbox{ et }}n>0.\end{cases}}}$

Autrement dit :

${\displaystyle A(0,n)=n+1\,}$

${\displaystyle A(m+1,0)=A(m,1)\,}$

${\displaystyle A(m+1,n+1)=A(m,A(m+1,n))\,}$

On montre alors que :

${\displaystyle A(1,n)=2+(n+3)-3}$

${\displaystyle A(2,n)=2\times (n+3)-3}$

${\displaystyle A(3,n)=2^{n+3}-3}$

${\displaystyle A(4,n)=2^{2^{2^{\cdots ^{2}}}}-3}$ avec (n + 3) deux empilés, noté également ${\displaystyle 2\uparrow \uparrow (n+3)-3}$ en utilisant la notation des puissances itérées de Knuth.

${\displaystyle A(5,n)=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow (\cdots \uparrow \uparrow 2)))-3}$ avec (n + 3) deux, également noté ${\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}$.

et plus généralement :

${\displaystyle A(m,n)=2\uparrow ^{(m-2)}(n+3)-3}$

Ackermann a initialement proposé cette fonction à trois paramètres[4] :

${\displaystyle {\begin{cases}\phi (m,n,0)=m+n\\\phi (m,0,p+1)=\alpha (m,p)={\begin{cases}0,&{\text{si }}p=0\\1,&{\text{si }}p=1\\m,&{\text{si }}p\geq 2\end{cases}}\\\phi (m,n+1,p+1)=\phi (m,\phi (m,n,p+1),p)\end{cases}}\,\!}$

Elle satisfait aux égalités suivantes :

${\displaystyle \phi (a,b,0)=a+b\,}$

${\displaystyle \phi (a,b,1)=a\cdot b}$

${\displaystyle \phi (a,b,2)=a^{b}\,}$

et, plus généralement[4], si ${\displaystyle f_{n}}$ est définie par

${\displaystyle f_{n}(c)=\phi (a,c,n)}$

${\displaystyle \phi (a,b,n+1)}$ est la b^ième itérée de ${\displaystyle f_{n}}$ en ${\displaystyle \alpha (a,n)}$

La seule opération effectuée lors du déroulement de la fonction d'Ackermann est l'ajout de 1 (lorsque m est nul). Malgré cela, cette fonction croît extrêmement rapidement : A(4,2) a déjà 19 729 chiffres et représente bien plus que le nombre d'atomes estimé dans l'Univers. Cette extrême croissance peut être exploitée pour montrer que la fonction f définie par f(n) = A(n, n) croît plus rapidement que n'importe quelle fonction récursive primitive et ainsi que A n'en est pas une.

Cette fonction est néanmoins définissable par récursion primitive d'ordre supérieur (système T de Gödel et ses extensions). Elle est aussi calculable par une machine de Turing. La fonction d'Ackermann constitue donc un exemple de fonction récursive, mais non récursive primitive. C'est peut-être l'exemple le plus cité d'une telle fonction (en particulier chez Knuth).

La fonction d'Ackermann montre que la notion de calculabilité introduite par les seules fonctions récursives primitives ne correspond pas à la notion de calculabilité la plus générale, celle de la thèse de Church. En effet, la fonction d'Ackermann est calculable au sens de Turing et de Church, mais pas par une fonction récursive primitive.

D'un point de vue historique, les premiers programmeurs qui utilisaient Fortran affirmaient sans preuve qu'il avait la complexité des fonctions récursives. Pour y apporter une preuve, le logicien Rice a proposé en 1965 un programme en Fortran (bien sûr non récursif) qui calculait la fonction d'Ackermann[5].

L'inverse de la fonction d'Ackermann est aussi utilisée. Puisque la fonction f définie par f(n) = A(n,n) considérée précédemment croît réellement très vite, sa réciproque croît vraiment très lentement. Elle apparaît notamment en algorithmique, pour exprimer des complexités. Dans ce domaine elle est souvent notée ${\displaystyle \alpha (n)}$[6]. On la trouve par exemple dans l'analyse de certaines structures de données comme l'Union-Find, dans un algorithme de calcul de l'arbre couvrant de poids minimal et en géométrie algorithmique[6]. Elle peut être définie simplement sans faire appel à la fonction d'Ackermann, en définissant la hiérarchie inverse d'Ackermann (qui fait aussi apparaître le logarithme itéré)[6] - [7].

La fonction d'Ackermann demandant beaucoup de calculs même pour de petites entrées. Elle est parfois utilisée comme programme de test d'une implémentation d'un langage de programmation ; en particulier, elle utilise de façon très exigeante la récursivité, de même que ses consœurs fib (suite de Fibonacci) et tak (fonction de Takeuchi).

En plus de tester directement les performances d'un langage de programmation, la fonction d'Ackermann a été utilisée comme exemple pour étudier des transformations de programme et des optimisations, en particulier dans le domaine de la spécialisation de programmes et de l'évaluation partielle (en)[8].