Wiki Googologie
Advertisement

La fonction d'Ackermann A(x,y) est une fonction récursive qui a été inventée à l'origine par Wilhelm Ackermann[1] 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.

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}}n 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).[2][3][4]

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[5] :

  • 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 :

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

It is thus capable of significantly fast growth rates. For example, A(4,2) computes to the following value:

A(4,2) = 2↑↑5 -3 = 2↑↑5 -3 = 2↑2↑2↑2↑2 -3 ≈ 2 × 1019728

Friedman's definition

Harvey Friedman defined the Ackermann function A(x,y) (x,y > 0) like so:[6]

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

According to this definition, A(x,y) is defined for any positive integers x and y, and equal to 2↑x-1y.

Taro's extention

Taro extended the Ackermann function and defined fonction d'Ackermann multivariable‏‎ for achieving higher growth rate.

Vidéo

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

Références

  1. Ackermann, Wilhelm (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. doi:10.1007/BF01459088
  2. Takayuki Kihara "アッカーマン関数とヒルベルト (fonction d'Ackermann et Hilbert)" 数学セミナー juillet 2019 pp.22-27.
  3. Takayuki Kihara.pdf 2019年度 数理情報学基礎論概論 2・講義ノート.2019.
  4. en:User_blog:Kyodaisuu/Lecture de l'article d'Ackermann
  5. Ackermann Function
  6. THE ACKERMANN FUNCTION IN ELEMENTARY ALGEBRAIC GEOMETRY
Advertisement