Fonction d'Ackermann

Un article de Wikipédia, l'encyclopédie libre.

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

Sommaire

1 Histoire
2 Définition
3 Table de valeurs
4 Fonction récursive, mais pas récursive primitive
5 Description explicite
6 Réciproque
7 Implémentation récursive
8 Implémentation: récursivité non terminale
9 Applications pratiques
10 Voir aussi
11 Références

[modifier] 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]. A 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 le papier 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, connue aujourd'hui sous le nom de fonction d'Ackermann.

[modifier] 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}$

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))\,$

[modifier] 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	8×2ⁿ − 3
4	13	65533	2⁶⁵⁵³⁶ − 3	A(3, 2⁶⁵⁵³⁶ − 3)	A(3, A(4, 3))	2^{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))

[modifier] 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 d'atomes dans l'univers 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 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 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.

[modifier] 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

[modifier] 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.

[modifier] Implémentation 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))

[modifier] Implémentation: récursivité non terminale

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

[modifier] 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, language très efficace dans le traitement des fonctions récursives.

[modifier] Voir aussi

[modifier] Références

↑ Cristian Calude, Solomon Marcus et Ionel Tevy, The first example of a recursive function which is not primitive recursive, Historia Math., vol. 6, n. 4, 1979, pp. 380–84
↑ Wilhelm Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Mathematische Annalen, vol. 99, 1928, pp. 118–33.