Fonction d'Ackermann
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Dans la théorie de la récursivité, la fonction d'Ackermann (aussi appelée fonction d'Ackermann-Péter), est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle prend deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(n,m).

Histoire

Dans les années 1920, Wilhelm Ackermann et Gabriel Sudan, alors étudiants sous la direction de David Hilbert, étudiaient les fondements de la calculabilité (La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l'informatique théorique. Alors que la...). Sudan est le premier à donner un exemple de fonction récursive (En informatique et en mathématiques, le terme fonction récursive désigne deux concepts liés, mais distincts. Plus généralement les termes « récursif », « récursivement », « récursion », « récursivité »,...) mais non récursive primitive, appelée alors fonction de Sudan. Peu après et indépendamment, en 1928, Ackermann a publié son propre exemple de fonction récursive mais non récursive primitive[1]. A l'origine, Ackermann considéra une fonction A (m, N, p) dépendant de trois variables, et consistant à calculer la puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) itérée p fois de m par n, c'est-à-dire m → n → p pour utiliser la notation de Conway.

Ackermann démontra que sa fonction A était bien une fonction récursive, i.e. une fonction qu'un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données sous forme binaire,...) idéalisé peut calculer. Dans Sur l'infini, David Hilbert conjectura que la fonction d'Ackermann n'était pas primitivement récursive. Cette conjecture (En mathématiques, une conjecture est une assertion qui a été proposée comme vraie, mais que personne n'a encore pu démontrer ou réfuter.) fut établie par Ackermann lui même dans son article Zum Hilbertschen Aufbau der reellen Zahlen[2]. Sur l'infini était le papier (Le papier (du latin papyrus) est une matière fabriquée à partir de fibres cellulosiques végétales et animales. Il se présente sous forme de feuilles minces et est considéré comme un...) le plus important de Hilbert sur les bases des mathématiques (Les mathématiques constituent un domaine de connaissances abstraites construites à l'aide de raisonnements logiques sur des concepts tels que les nombres,...), servant de cœur au programme de Hilbert pour fixer la base des nombres transfinis.

Une fonction semblable de seulement deux variables fut donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement,...) plus tard par Rózsa Péter et Raphael Robinson, connue aujourd'hui sous le nom de fonction d'Ackermann.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les...)

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

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}

Ackermann a lui même initialement donné cette définition :

\phi(a, b, 0)=a+b\,
\phi(a, 0, n+1)=\psi(a, n)\,
\phi(a, b+1, n+1)=\phi(a, \phi(a, b, n+1), n)\,

Elle satisfait aux égalités suivantes :

\phi(a, b, 0) = a+b\,
\phi(a, b, 1) = a \cdot b
\phi(a, b, 2) = a^b\,
\ldots

Rózsa Péter a également donné la définition suivante de la fonction :

\textrm{a}(0, m) = m+1\,
\textrm{a}(n+1, 0) = \textrm{a}(n, 1)\,
\textrm{a}(n+1, m+1) = \textrm{a}(n, \textrm{a}(n+1, m))\,

Table de valeurs

Valeurs de A(mn)
m\n 0 1 2 3 4 n
0 1 2 3 4 5 n + 1
1 2 3 4 5 6 n + 2
2 3 5 7 9 11 2n + 3
3 5 13 29 61 125 8×2n − 3
4 13 65533 265536 − 3 A(3, 265536 − 3) A(3, A(4, 3)) 22...2 − 3 (n + 3 termes)
5 65533 A(4, 65533) A(4, A(5, 1)) A(4, A(5, 2)) A(4, A(5, 3))
6 A(5, 1) A(5, A(5, 1)) A(5, A(6, 1)) A(5, A(6, 2)) A(5, A(6, 3))

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, soit bien plus que le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'atomes (Un atome (du grec ατομος, atomos, « que l'on ne peut diviser ») est la plus petite partie d'un corps simple...) dans l'univers (L'Univers est l'ensemble de tout ce qui existe et les lois qui le régissent.) actuel. 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 (On s'intéresse aux fonctions définies sur l'ensemble des entiers naturels, ou sur les ensembles des k-uplets d'entiers naturels, et à valeurs dans .) et ainsi n'est pas primitive récursive.

À noter que 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 (A l'instar de la récursion primitive ou le lambda-calcul, le Système T est un langage de programmation théorique. Il a été inventé par le logicien Kurt Gödel.) de Gödel et ses extensions.

La croissance exponentielle (En mathématique, en économie et en biologie, on parle d'un phénomène à croissance exponentielle (ou géométrique) lorsque la croissance en valeur absolue de la population est proportionnelle à la population...) des problèmes liés aux grands systèmes informatiques est en relation également avec la Thèse (Une thèse (du nom grec thesis, se traduisant par « action de poser ») est l'affirmation ou la prise de position d'un locuteur, à...) de Church.

Description explicite

Intuitivement, la fonction d'Ackermann génère progressivement une multiplication (La multiplication est l'une des quatre opérations de l'arithmétique élémentaire avec l'addition, la soustraction et la division .) par deux (additions réitérées), une exponentiation de base 2 (multiplications réitérées), une exponentiation réitérée, une réitération de cette opération, et ainsi de suite. Elle peut être exprimée en utilisant la notation des puissances itérées de Knuth :

A(1, n) = 2 + (n + 3) - 3
A(2, n) = 2 × (n + 3) - 3
A(3, n) = 2 ↑ (n + 3) - 3
A(4, n) = 2 ↑ (2 ↑ (2 ↑ (... ↑2))) - 3     (n + 3 deux)
            = 2↑↑(n + 3) - 3
A(5, n) = 2↑↑↑(n + 3) - 3 etc.

On montre assez facilement par récurrence que:

A(u, v) = 2↑(u-2)(v + 3) - 3

Réciproque (La réciproque est une relation d'implication.)

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.

Implémentation (Le mot implantation peut avoir plusieurs significations :) récursive

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

Implémentation itérative

function ack(n, m)

 
 while n ≠ 0 
 if m = 0 
 m:= 1 
 else 
 m:= ack(n, m - 1) 
 n:= n - 1 
 return m + 1 
 

Applications pratiques

Dans la programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel...) 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 (Un langage de programmation est un langage informatique, permettant à un être humain d'écrire un code source qui sera analysé par une machine, généralement un ordinateur. Le code source...) Haskell, language très efficace dans le traitement des fonctions récursives.

Page générée en 0.097 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique