Notation des flèches chaînées de Conway Article, Signification, Explication

La notation des flèches enchaînées de Conway est un moyen d'exprimer de très grands nombres créée par le mathématicien John Horton Conway. Elle consiste en une suite finie d'entiers positifs séparés par des flèches, comme par exemple .

Comme beaucoup d'autres expression combinatoires, sa définition est récursive. Au bout du compte, elle revient à élever le nombre le plus à gauche à une puissance entière et généralement énorme.

Table of contents

1 Définition 2 Propriétés 3 Exemples 4 Nombre de Graham 5 Fonction d'Ackermann 6 Voir aussi

Définition

Dans la définition suivante, et sont des nombres entiers positifs et est une chaîne dont la valeur est supposée connue (en-celà, la définition est récursive). On pose :

1. (exponentiation)
2. (et donc )
3. , avec copies de la chaîne , copies de copies et paires de parenthèses.

En explicitant un peu :

• Une chaîne de longueur 1 est juste un nombre :
• Une chaîne de longueur 2 est un nombre élevé à une puissance entière:
• Une chaîne de longueur 3 correspond à la notation de Knuth et à l'hyper opérateur :

.

• Une chaîne de longueur 4 est généralement trop grande pour être facilement appréhendée.

Propriétés

Cette notation n'est pas associative. En effet :

Une chaîne de trois éléments ou plus se terminant par 2 ou un nombre supérieur peut être transformée en une chaîne de même longueur, avec un avant-dernier élément considérablement plus grand, mais un dernier élément plus petit de 1 :

si et sont plus grands que 1.

Par itération, ceci permet de réduire la chaîne à deux éléments.

Il faut noter que la chaîne peut toujours être exprimée sous la forme , où est un nombre entier considérablement plus grand que et .

Par conséquent :

• Une chaîne commençant par est une puissance de
• Une chaîne commençant par 1 est égale à 1
• Une chaîne commençant par est de la forme et donc égale à 4 (voir ci-dessous)/

Les cas les plus simples avec quatre nombres sont :

Si pour une chaîne on définit la fonction , alors .

Exemples

Il est difficile de donner des exemples pertinents, car ils requièrent 4 éléments et correspondent à des nombres beaucoup trop grands pour pouvoir être explicités. Cependant, dans les exemples suivants, les numéros entre parenthèses à la fin de chaque ligne indique quelle partie de la définition de la notation a été utilisée pour passer d'une ligne à l'autre.

= (3)

= (2)

= (1)

= (1)

= , approximativement

Avec la notation de Knuth :

= (3)

= (3)

= (3)

= (2)

= (1)

=

En fait, toute chaîne commençant par deux 2 est égale à 4.

= (3)

= (d'après l'exemple précédent)

= (3)

= (2)

= (1)

= (1)

= (1)

= (3) avec 65 535 paires de parenthèses

= (2)

= (1)

= (1)

= (1)

=

où est un nombre extrêmement grand.

Il est possible d'écrire l'expression précédente à l'aide de la notation de Knuth :

= (3)

= (1 et 2)

= (3)

= (voir ci-dessus)

= (3)

= (voir ci-dessus)

= (id.)

= (id.)

= (id.)

= ''(d'après l'exemple précédent)

Ici, il devient impossible d'expliciter le nombre plus avant.

À l'aide de la notation de Knuth : .

= (3)

= (1 et 2)

= (3)

Ce qui correspond à un nombre proprement gigantesque.

À l'aide de la notation de Knuth :

Nombre de Graham

Le nombre de Graham — qui est en 2004 le plus grand nombre jamais utilisé dans une démonstration mathématique pertinente — ne peut pas être exprimé de façon succinte dans la notation de Conway, mais si l'on définit la fonction , alors :

• et

Il est possible de prouver le deuxième point :

= (3), avec 128 fois le chiffre 3

= (1)

=

De même,

Comme est strictement croissante, , ce qui conduit à l'inégalité recherchée.

On peut noter que la simple expression est largement plus grande que le nombre de Graham.

Fonction d'Ackermann

La fonction d'Ackermann peut être exprimée à l'aide de la notation de Conway :

pour

et donc :

pour

(les cas et peuvent être considérés en posant et ).

Voir aussi

• Notation des puissances itérées de Knuth
• Notation de Steinhaus-Moser
• Fonction d'Ackermann

C'est un article concernant le Notation des flèches chaînées de Conway. La page contient la signification du Notation des flèches chaînées de Conway , Description et explication au sujet de Notation des flèches chaînées de Conway