Notation des flèches chaînées

Explication du fonctionnement de la notation des flèches chaînées du 5ème épisode de Sushi Kokuu Hen.

La notation des flèches chaînées de Conway est une généralisation de la notation des puissances itérées introduite par J. H. Conway et R. K. Guy pour avoir montré que 3→3→3→3 est plus grand que le nombre de Graham.

Définition

Une "chaîne de Conway" est définie comme suit :

• Tout entier positif est une chaîne de longueur 1.
• Une chaîne de longueur n, suivie d'une flèche droite → et d'un entier positif, forment ensemble une chaîne de longueur n+1.

Pour des entiers positifs a, b, c et une sous-chaîne X,

1. a→b→c = a↑^cb (voir notation des puissances itérées)
2. X→1 = X
3. X→1→b = X
4. X→(b + 1)→(c + 1) = X→(X→b→(c + 1))→c

Notez que la flèche → n'est pas un opérateur au sens classique du terme; a→b→c n'est égal ni à a→(b→c) ni à (a→b)→c. La chaîne entière (qui pourrait être considérée comme un tableau) représente une seule opération.

En substituant c=1 à la règle 1, et en utilisant la règle 2, on obtient la relation suivante pour la chaîne de longueur 2.

• a→b = a^b

Exemples

Voici quelques petits exemples de la notation par flèches chaînées en action :

• 2→2→2→2 = 2→2→(2→2→1→2)→1 = 2→2→4→1 = 2↑↑↑↑2 = 4
• 3→3→2 = 3↑↑3 = 7625597484987

Fonction CG

En utilisant la notation des flèches chaînées, Conway et Guy ont écrit : "The first three of our rapidly increasing sequence of numbers 1, 2→2, 3→3→3, 4→4→4→4, ...", ce qui implique qu'ils ont défini la fonction suivante.

$cg(n) = \underbrace{n \rightarrow n \rightarrow \ldots \rightarrow n \rightarrow n}_n$

Le taux de croissance de cette fonction est d'environ $f_{\omega^2}(n)$ dans la hiérarchie de croissance rapide.

Approximation

Oyakata finit d'expliquer G < 3→3→3→3 et est satisfait. Oyakata "Voila !" Source: 5ème épisode de Sushi Kokuu Hen

Conway a écrit que le nombre de Graham = G est compris entre 3→3→64→2 et 3→3→65→2, et donc inférieur à 3→3→3→3. Il peut être confirmé comme suit. Soit g(x) = 3↑^x3 = 3→3→x, et G = g⁶⁴(4).

• 3→3→1→2 = 3→3→1 = g(1) = 27
• 3→3→2→2 = 3→3→(3→3→1→2)→1 = 3→3→(3→3→1) = g(g(1)) = g²(1) = 3→3→27 = g(27)
• 3→3→3→2 = 3→3→(3→3→2→2) = g³(1) = g²(27)
• 3→3→n→2 = gⁿ(1) = g^n-1(27)
• 3→3→64→2 = g⁶⁴(1) < g⁶⁴(4) = G
• 3→3→65→2 = g⁶⁴(27) > g⁶⁴(4) = G
• 3→3→3→3 = 3→3→(3→3→2→3)→2 > 3→3→65→2 > G

En utilisant cette approximation, comme Moser ≈ g(10↑↑257) < g(g(3)),

• 3→3→2→2 < Moser < 3→3→3→2

La notation de la flèche enchaînée peut être approximée avec la fonction d'Ackermann multivariable comme suit pour x=1, y>1 ou x>1, y+z>0.

$A(x,y,z) < \underbrace{3 \rightarrow3 \rightarrow \cdots \rightarrow 3}_{x+1} \rightarrow z+2 \rightarrow y+1 < A(x,y,z+1)$

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)

Elle peut être approximée par la hiérarchie de croissance rapide avec des ordinaux ayant la séquence fondamentale de la hiérarchie de Wainer comme suit.

• $3 \rightarrow 3 \rightarrow n \approx f_\omega (n)$
• $3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \approx f_\omega (27)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \approx f^2_\omega (27)$
• $3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \approx f^3_\omega (27)$
• $3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \approx f_{\omega +1} (n)$
• $3 \rightarrow 3 \rightarrow 2 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 2 \approx f_{\omega +1} (26)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 3) \rightarrow 2 \approx f^2_{\omega +1} (26)$
• $3 \rightarrow 3 \rightarrow 4 \rightarrow 3 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3) \rightarrow 2 \approx f^3_{\omega +1} (26)$
• $3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \approx f_{\omega +2} (n)$
• $3 \rightarrow 3 \rightarrow 2 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1) \rightarrow 3 \approx f_{\omega +2} (26)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 2 \rightarrow 4) \rightarrow 3 \approx f^2_{\omega +2} (26)$
• $3 \rightarrow 3 \rightarrow 4 \rightarrow 4 = 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 4) \rightarrow 3 \approx f^3_{\omega +2} (26)$
• $3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \approx f_{\omega +3} (n)$
• $3 \rightarrow 3 \rightarrow (n+1) \rightarrow 5 \approx f_{\omega +4} (n)$
• $3 \rightarrow 3 \rightarrow (n+1) \rightarrow 6 \approx f_{\omega +5} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \approx f_{\omega \times 2} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3) \approx f_{\omega \times 2} (f_4 (3))$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 2 \rightarrow 2) \approx f^2_{\omega \times 2} (f_4 (3))$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 = 3 \rightarrow 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 2) \approx f^3_{\omega \times 2} (f_4 (3))$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \approx f_{\omega \times 2 +1} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \approx f_{\omega \times 2 +2} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \approx f_{\omega \times 2 +3} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \approx f_{\omega \times 3} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 2 \approx f_{\omega \times 3 +1} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 3 \approx f_{\omega \times 3 +2} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \rightarrow 4 \approx f_{\omega \times 3 +3} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \approx f_{\omega \times 4} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \approx f_{\omega \times 5} (n)$
• $3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 \rightarrow (n+1) \approx f_{\omega \times 6} (n)$
• $\underbrace{3 \rightarrow 3 \rightarrow \ldots \rightarrow 3 \rightarrow 3}_{n+2} \approx f_{\omega^2}(n)$