Fonction d'Ackermann

Fonction d'Ackermann

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 est souvent présentée sous la forme qu'en a proposé la mathématicienne Rózsa Péter, comme une fonction à deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur, noté en général A(n, m).

Sommaire

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é. 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 a publié son propre exemple de fonction récursive mais non récursive primitive[1]. À l'origine, Ackermann considéra une fonction A (m, n, p) dépendant de trois variables, et consistant à calculer la puissance 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 idéalisé peut calculer. Dans Sur l'infini, David Hilbert conjectura que la fonction d'Ackermann n'était pas primitivement récursive. Cette conjecture fut établie par Ackermann lui-même dans son article Zum Hilbertschen Aufbau der reellen Zahlen[2]. Sur l'infini était l'article le plus important de Hilbert sur les bases des mathématiques, 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 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.

Définition

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}

Autrement dit :

A(0, n) = n+1\,
A(m+1, 0) = A(m, 1)\,
A(m+1, n+1) = A(m, A(m+1, n))\,

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

\begin{cases} \phi(m, n, 0) = m + n \\ \phi(m, 0, 1) = 0 \\ \phi(m, 0, 2) = 1 \\ \phi(m, 0, p+2) = m \\ \phi(m, n+1, p+1) = \phi(m, \phi(m, n, p+1), p) \end{cases}\,\!

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

Table de valeurs

Valeurs de A(m, n)
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 2n + 3 − 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))

Importance épistémologique

La fonction d'Ackermann croît extrêmement rapidement; A(4,2) a déjà 19729 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 et est 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 célèbre de fonction récursive mais non récursive primitive, et c'est ce pour quoi elle est connue principalement, cependant son intérêt épistémologique va au delà.

L'exemple de la fonction d'Ackermann, montre que la notion de calculabilité introduite par les fonctions récursives primitives n'est pas la notion de calculabilité la plus générale, celle atteinte avec un grand succès par la thèse de Church. En effet, la fonction d'Ackermann est calculable au sens de Turing et de Church, mais pas à l'aide d'une fonction récursive primitive. C'est un exemple qui montre que la thèse de Church ne concerne pas tous les systèmes de calcul. Il existe des systèmes de calcul, qui semblent pourtant généralistes et puissants comme les fonctions récursives primitives, et qui effectivement permettent de définir la plupart des fonctions usuelles, mais qui ne sont pas équivalents aux machines de Turing et au Lambda-calcul. La calculabilité de la fonction d'Ackermann sert ici de critère distinctif, ceci révèle sa véritable importance épistémologique.

Description explicite

Intuitivement, la fonction d'Ackermann génère progressivement une multiplication 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

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 cette réciproque apparaît dans l'analyse de la complexité de certains algorithmes, tels que l'algorithme Union-Find et un algorithme de calcul de l'arbre couvrant de poids minimal.

Applications pratiques

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)).

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)[3].

Voir aussi

Références

  1. ↑ Cristian Calude, Solomon Marcus et Ionel Tevy, The first example of a recursive function which is not primitive récursive, Historia Math., vol. 6, n. 4, 1979, pp. 380–84
  2. ↑ Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen, vol. 99, 1928, pp. 118–33.
  3. ↑ Yanhong A. Liu et Scott D. Stoller, Optimizing Ackermann's Function by Incrementalization, Workshop on Partial Evaluation and Semantics Based Program Manipulation, 2003

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fonction d'Ackermann de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Fonction Récursive Primitive — Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont été initialement analysées… …   Wikipédia en Français

  • Fonction recursive primitive — Fonction récursive primitive Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont… …   Wikipédia en Français

  • Fonction De Sudan — En Calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non primitive récursive. Ceci est aussi le cas de la bien plus connue Fonction d Ackermann. Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan élève… …   Wikipédia en Français

  • Fonction de sudan — En Calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non primitive récursive. Ceci est aussi le cas de la bien plus connue Fonction d Ackermann. Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan élève… …   Wikipédia en Français

  • Fonction Récursive — Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

  • Fonction recursive — Fonction récursive Voir « récursif » sur le Wiktionnaire …   Wikipédia en Français

  • Fonction récursive primitive — Une fonction récursive primitive est une fonction définie principalement à l aide de fonctions primitives de récursion et de composition. Ces fonctions constituent un sous ensemble des fonctions récursives. Elles ont été initialement analysées… …   Wikipédia en Français

  • Fonction de Sudan — En calculabilité, la fonction de Sudan est un exemple de fonction récursive mais non primitive récursive. C est aussi le cas de la bien plus connue fonction d Ackermann. Elle fut conçue en 1927 par le mathématicien roumain Gabriel Sudan, élève de …   Wikipédia en Français

  • Fonction récursive — Sur les autres projets Wikimedia : « Fonction récursive », sur le Wiktionnaire (dictionnaire universel) En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de… …   Wikipédia en Français

  • Fonction exponentielle double —  Cet article concerne la fonction exponentielle double. L’expression « distribution exponentielle double » peut désigner la loi de Laplace, qui est une distribution exponentielle bilatérale ou la distribution de Gumbel qui est une… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”