Fonction d'Ackermann
La fonction d'Ackermann (aussi appelée fonction de 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.
| Table of contents |
|
2 Table de valeurs 3 fonction récursive, mais pas récursive primitive 4 description explicite 5 Histoire 6 Réciproque |
La fonction d'Ackermann est définie récursivement comme suit :
Définition
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)) |
La fonction d'Ackermann croît extrêmement rapidement; A(4,2) a déjà 19729 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.
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 de flèche ascendante de Knuth :
En 1928, Wilhelm Ackermann considéra une fonction A(m, n, p) de trois variables, le p-ème itété de l'élévation de m à la puissance n, et prouva que c'est une fonction récursive n'est 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.fonction récursive, mais pas récursive primitive
description explicite
Histoire