Fonction d'Ackermann

La fonction d'Ackermann A(x,y) est une fonction récursive qui a été inventée à l'origine par Wilhelm Ackermann et simplifiée plus tard par Rózsa Péter puis par Raphael Robinson. La définition exacte de la fonction d'Ackermann varie légèrement selon les auteurs. La nombre d'Ackermann sont définis avec la définition originale de la fonction d'Ackermann.

Définition

Définition originale

La définition originale de la fonction d'Ackermann est la suivante. Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://mathoid-facade/v1/ » :): {\displaystyle \begin{array}{rl} A(0,x,y)&:=x+y\\ A(n+1,x,y)&:=\underbrace{A(n,A(\cdots(A(n,x))\cdots)}_{y \text{times}} \end{array} } Elle peut être exprimée avec la notation des puissances itérées, qui n'a pas été conçue lorsque cette fonction a été publiée, comme A(n+2,x,y) = x{up}}ⁿ y. Elle a été définie en termes de récursion primitive d'ordre supérieur (c'est-à-dire, récursion primitive sur la fonctionnelle).

La définition de Robinson

La version de Robinson est la définition de la fonction d'Ackermann la plus souvent citée en référence et est définie comme suit :

• A(x,y) = y + 1 if x = 0, else
• A(x,y) = A(x - 1,1) if y = 0, otherwise,
• A(x,y) = A(x - 1,A(x,y - 1))

L'expansion de A(2,2) utilisant cette définition est donnée ci-dessous à titre d'exemple :

Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « http://mathoid-facade/v1/ » :): {\displaystyle \begin{array}{rl} A(2,2) &=& A(1,A(2,1))\\ &=& A(1,A(1,A(2,0)))&&\\ &=& A(1,A(1,A(1,1)))\\ &=& A(1,A(1,A(0,A(1,0))))\\ &=& A(1,A(1,A(0,A(0,1))))\\ &=& A(1,A(1,A(0,2)))\\&=& A(1, A(1, 3))\\ &=& A(1, A(0, A(1, 2)))\\ &=& A(1, A(0, A(0, A(1, 1))))\\ &=& A(1, A(0, A(0, A(0, A(1, 0)))))\\ &=& A(1, A(0, A(0, A(0, A(0, 1)))))\\ &=& A(1, A(0, A(0, A(0, 2))))\\ &=& A(1, A(0, A(0, 3)))\\ &=& A(1, A(0, 4))\\ &=& A(1, 5)\\ &=& A(0, A(1, 4))\\ &=& A(0, A(0, A(1, 3)))\\ &=& A(0, A(0, A(0, A(1, 2))))\\ &=& A(0, A(0, A(0, A(0, A(1, 1)))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(1, 0))))))\\ &=& A(0, A(0, A(0, A(0, A(0, A(0, 1))))))\\ &=& A(0, A(0, A(0, A(0, A(0, 2)))))\\ &=& A(0, A(0, A(0, A(0, 3))))\\ &=& A(0, A(0, A(0, 4)))\\ &=& A(0, A(0, 5))\\ &=& A(0, 6)\\ &=& 7 \end{array} }

La fonction d'Ackermann est liée à la notation des puissances itérées comme suit :

A(x,y) = 2↑^x-2(y+3)-3

Il est donc capable de taux de croissance considérablement rapides. Par exemple, A(4,2) se calcule à la valeur suivante :

A(4,2) = 2↑↑5 -3 = 2↑↑5 -3 = 2↑2↑2↑2↑2 -3 ≈ 2 × 10¹⁹⁷²⁸

La définition de Friedman

Harvey Friedman a défini la fonction d'Ackermann A(x,y) (x,y > 0) comme suit :

• A(x,y) = 2 (if y=1)
• A(x,y) = 2y (if x=1 and y > 1)
• A(x,y) = A(x-1,A(x,y-1)) (if x > 1 and y > 1)

Selon cette définition, A(x,y) est défini pour tout entier positif x et y, et égal à 2↑^x-1y.

L'extension de Taro

Taro a étendu la fonction d'Ackermann et a défini une fonction d'Ackermann multivariable pour atteindre un taux de croissance plus élevé.

Vidéo

Source: Langage C : Fonction d'Ackermann (Darija)