Wiki Googologie
Advertisement
Wiki Googologie

Explication de la version à trois variables de la fonction d'Ackermann multivariable du 9ème épisode de Sushi Kokuu Hen.

La fonction d'Ackermann multivariable A(x1,x2, ..., xn) est une fonction récursive inventée par un googologue japonais Taro (2007) et décrite par Fish.[1] Elle est similaire à la fonction d'Ackermann de Robinson avec 2 variables, et avec plus de 3 variables, sa croissance est beaucoup plus rapide; A(1,2,2) est plus grand que le nombre de Graham G et que 3→3→3→3, et A(1,0,1,2) est plus grand que . La limite du taux de croissance dans la hiérarchie de croissance rapide est .

Définition

Soit

  • X : vecteur d'entiers supérieurs ou égaux à 0, de longueur supérieure ou égale à 0 (ex. : [3, 1, 0, 0])
  • Y : vecteur de 0 de longueur supérieure ou égale à 0 (ex. [0, 0, 0, 0, 0])
  • a, b : nombre entier supérieur ou égal à 0

et la fonction d'Ackermann multivariable A est définie comme suit.

  1. A(Y, a) = a+1
  2. A(X, b+1, 0) = A(X, b, 1)
  3. A(X, b+1, a+1) = A(X, b, A(X, b+1, a))
  4. A(X, b+1, 0, Y, a) = A(X, b, a, Y, a)

En d'autres termes :

  • Si toutes les variables sauf/et la dernière sont des zéros, la valeur de la fonction est le successeur de la dernière variable. (1er cas)
  • Si l'avant-dernière variable est un non-zéro : (2ème ou 3ème cas)
    • Si la dernière variable est un zéro : (2ème cas)
      • Remplacer la dernière variable à 1. 
      • Réduisez l'avant-dernière variable en 1.
    • Else : (3ème cas)
      • Remplacer la dernière variable par la valeur de la fonction, mais avec sa dernière variable réduite de 1.
      • Réduisez l'avant-dernière variable en 1.
  • Else (l'avant-dernière entrée est une extrémité d'un vecteur Y (qui sera nommé Z)) : (4ème cas)
    • Remplacer la première variable de Z par la dernière variable.
    • Réduisez la dernière variable avant Z par 1.

Calcul

Le secret de la croissance rapide de cette fonction se trouve dans le 4e cas de la définition. Pour réduire la variable "b" de 1, elle diagonalise la variable de droite de 0 à a. Il suffit de faire une récursion forte. Si on compte les variables de droite à gauche, la 2ème variable récure la 1ère variable (récursion primitive dans la fonction d'Ackermann), la 3ème variable récure la 2ème variable, où la récursion de la récursion primitive fait une double récursion, la 4ème variable récure la 3ème variable. Au fur et à mesure que la nième variable récure la (n-1)ième variable, le "niveau" de récursion augmente régulièrement.

Un exemple de calcul est présenté pour comparer cette fonction avec le nombre de Graham à l'aide de la notation des flèches chaînées de Conway. Avec 2 variables, elle est similaire à la fonction d'Ackermann standard et elle est comparée comme suit

A(x,y) ≈ 3 → y → (x-2)

Avec 3 variables,

  • A(1,1,0) = A(1,0,1) = A(0,1,1) = A(1,1) = 3
  • A(1,1,1) = A(1,0,A(1,1,0)) = A(1,0,3) = A(3,3) = 61
  • A(1,1,2) = A(1,0,61) = A(61,61) > 3 → 3 → 2 → 2
  • A(1,1,3) ≈ A(1,0,3 → 3 → 2 → 2) ≈ 3 → 3 → 3 → 2
  • A(1,1,4) ≈ A(1,0,3 → 3 → 2 → 3) ≈ 3 → 3 → 4 → 2
  • A(1,1,x) ≈ 3 → 3 → x → 2
  • A(1,1,65) ≈ 3 → 3 → 65 → 2 > G
  • A(1,2,0) = A(1,1,1) = 61
  • A(1,2,1) = A(1,1,61) > 3 → 3 → 61 → 2
  • A(1,2,2) = A(1,1,A(1,1,61)) > 3 → 3 → (3 → 3 → 61 → 2) → 2 > A(1,1,65)

Et donc A(1,2,2) > A(1,1,65) > nombre de Graham.

La relation suivante a été calculée :[2]

Pour x=1, y>1 or x>1, y+z>0

Par exemple,

  • A(1,2,1) < 3→3→3→3 < A(1,2,2)
  • A(2,2,1) < 3 → 3 → 3 → 3 → 3 < A(2,2,2)
  • A(3,2,1) < 3 → 3 → 3 → 3 → 3 → 3 < A(3,2,2)

Par conséquent, la fonction A(x,y,z) a un niveau récursif correspondant à x+3 variables de la notation des flèches chaînées de Conway, et A(1,0,1,2) dépasse la notation des flèches chaînées de Conway avec la longueur des nombres de Graham.

  • A(1,0,1,0) = A(1,0,0,1) = A(1,0,1) = A(1,1) = 3
  • A(1,0,1,1) = A(1,0,0,A(1,0,1,0)) = A(1,0,0,3) = A(3,0,3) = A(2,3,3)
  • A(1,0,1,2) = A(1,0,0,A(1,0,1,1)) = A(1,0,0,A(2,3,3)) = A(A(2,3,3),0,A(2,3,3)) ≈

Le taux de croissance de cette fonction a été comparé à la hiérarchie de croissance rapide avec la hiérarchie Wainer comme suit.

  • A(n, n) ≈
  • A(1, 0, n) ≈
  • A(a, 0, n) ≈
  • A(n, 0, n) ≈
  • A(1, 0, 0, n) ≈
  • A(a, 0, 0, n) ≈
  • A(n, 0, 0, n) ≈
  • A(1, 0, 0, 0, n) ≈
  • A(a, 0, 0, 0, n) ≈
  • A(n, 0, 0, 0, n) ≈
  • A(..., a3, a2, a1, a0, n) ≈

Références

Advertisement