Fonction d'Ackermann
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
La fonction d'Ackermann (aussi appelée fonction d'Ackermann-Peter), est une fonction récursive qui prend deux paramètres entiers naturels comme arguments et qui retourne un entier naturel comme valeur. Cette fonction est considérée en théorie de la programmation, comme un exemple important de fonction récursive, aux deux sens du terme.
Sommaire |
[modifier] Définition
La fonction d'Ackermann est définie récursivement comme suit :
[modifier] Table de valeurs
| 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)) |
[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. 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.
[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.
[modifier] Histoire
En 1928, Wilhelm Ackermann considéra une fonction A(m, n, p) de trois variables, le p-ème itéré de l'élévation de m à la puissance n, et prouva que c'est une fonction récursive mais pas récursive primitive. Cette définition fut plus tard simplifiée par Rosza Peter et Raphael Robinson en la définition avec deux paramètres donnée précédemment.
[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] Voir aussi
|
|
