Fonction d'Ackermann - Définition

Fonction récursive, mais pas récursive primitive

La fonction d'Ackermann croît extrêmement rapidement; A(4,2) a déjà 19829 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'est pas primitive récursive.

Cette fonction est néanmoins définissable par récursion primitive d'ordre supérieur, un schéma de récursion proposé par le système T de Gödel et ses extensions.

La croissance exponentielle des problèmes liés aux grands systèmes informatiques est en relation également avec la thèse de Church.

Implémentation

en pseudo code (type C, C++, Java) :

      function ackermann(n, m)           if n = 0               return m + 1           else if m = 0               return ackermann(n - 1, 1)           else               return ackermann(n - 1, ackermann(n, m - 1))      

en Caml :

      let rec ackermann = function        | (0, n) -> n + 1        | (m, 0) -> ackermann (m - 1, 1)        | (m, n) -> ackermann (m - 1, ackermann (m, n - 1))      

en Prolog :

       ackermann(0,N,Resultat):- Resultat is N+1.       ackermann(M,0,Resultat):- M>0, M' is M-1, ackermann(M',1,Resultat).       ackermann(M,N,Resultat):- M>0, M' is M-1, N>0, N' is N-1, ackermann(M,N',Resultat'), ackermann(M',Resultat',Resultat).      

Les algorithmes ci-dessus ne prennent pas en compte le fait que la fonction d'Ackermann croit extrêmement rapidement et dépasse rapidement la capacité de stockage des "int 32 bits", "int 64 bits" ou même "int 128 bits". Seules les implémentations permettant un calcul en précision infini permettront d'espérer un calcul effectif de cette fonction.

Réciproque

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. Il est intéressant de remarquer, que la réciproque apparaît dans l'analyse de l'exécution de certains algorithmes, tels l'Union-Find, qui permet de savoir si deux éléments se trouvent être dans un même ensemble.

Applications pratiques

Dans la programmation des grands systèmes, mais aussi entre autres dans le benchmarking, des algorithmes basés sur la fonction d'Ackermann permettent d'optimiser les résultats.

Cette fonction prend toute son utilité dans le langage de programmation Haskell, langage très efficace dans le traitement des fonctions récursives.