notation de Conway des grands nombres

Écrire 2 → 3 revient d'abord à écrire 2³, donc 8. Ajouter un troisième entier ne prolonge pas une simple suite de calculs : dans 2 → 3 → 2, le dernier 2 indique qu'il faut passer à l'opération suivante, la double flèche de Knuth. On obtient alors une tour de puissances de trois 2, soit 16.

Les flèches chaînées de Conway condensent ainsi des répétitions d'opérations qui deviendraient vite impossibles à écrire en toutes lettres. La chaîne décrit le nombre sans demander d'en afficher les chiffres.

Une chaîne de Conway est une suite finie d'entiers strictement positifs reliés par des flèches vers la droite. Une chaîne réduite au seul entier a vaut a. Avec deux termes, a → b vaut a^b. Avec trois termes, le dernier entier r donne le nombre de flèches de Knuth placées entre a et b :Cette correspondance suppose a, b et r strictement positifs.

Pour définir une chaîne plus longue, notons X tout son préfixe avant les deux derniers termes. Une chaîne terminée par 1 perd ce dernier terme. Si les deux derniers entiers p et q sont supérieurs à 1, la règle récursive est :La définition est bien fondée par récurrence imbriquée : l’appel interne porte sur p − 1, tandis que la chaîne extérieure porte sur q − 1 ; avec les règles de base, elle ramène donc la chaîne à des exponentiations ordinaires.

À partir de quatre termes, la récursion fait varier le niveau même de l'opération au lieu de conserver un nombre fixé de flèches de Knuth. C'est cette compression hiérarchique, et non l'existence d'une nouvelle sorte d'entier, qui donne à la notation sa puissance : toute chaîne finie désigne encore un entier positif fini.

Calculons la chaîne 2 → 3 → 2. Elle reste assez petite pour être vérifiée à la main tout en montrant le passage de l'exponentiation à l'opération suivante.

Données :
premier entier : 2 ;
deuxième entier : 3 ;
dernier entier : 2, donc deux flèches de Knuth.

1. Remplacer la chaîne de longueur trois par l'écriture de Knuth correspondante : 2 → 3 → 2 = 2 ↑↑ 3.
2. Lire la double flèche comme une tour de trois 2, associée depuis le sommet : 2 ↑↑ 3 = 2⁽²²⁾.
3. Calculer d'abord l'exposant supérieur : 2² = 4.
4. Calculer enfin 2⁴ = 16.

Le résultat est donc 16. Pour le contrôler, on peut développer la tour en 2 × 2 × 2 × 2 : elle comporte quatre facteurs et vaut bien 16. L'ordre des parenthèses est décisif, car (2²)² vaut aussi 16 ici, mais cette coïncidence ne vaut pas en général.

Pour lire une chaîne courte, on compte d'abord ses termes. Un seul terme est déjà un entier ; deux termes appellent une puissance ; trois termes se traduisent directement en flèches de Knuth. Cette traduction est préférable tant qu'elle garde le calcul lisible.

Pour comparer des chaînes plus longues, on applique les règles récursives symboliquement au lieu d'essayer d'écrire leurs chiffres. Le geste utile consiste à repérer les deux termes de droite, à vérifier qu'ils dépassent 1, puis à utiliser la règle qui les diminue.

Dans une démonstration sur la croissance des grands nombres, la notation de Knuth suffit si le nombre de flèches reste fixé et explicite. Une chaîne de Conway devient pertinente lorsque la construction doit aussi condenser la croissance de ce nombre de flèches.

Les flèches de Knuth forment une notation d'hyperopérations : dans a ↑↑ b, les deux flèches fixent l'opération avant le calcul. Dans une chaîne de Conway d'au moins quatre termes, la récursion peut faire dépendre ce niveau du reste de la chaîne ; la longueur de l'écriture fournit le critère qui tranche.

La suite de Conway, dite aussi suite audioactive, transforme des suites de chiffres en décrivant leurs répétitions. Malgré le même nom propre, elle ne contient pas de flèches chaînées et ne sert pas à condenser des hyperopérations.

Un très grand entier n'est pas « le plus grand nombre ». Quel que soit l'entier désigné par une chaîne finie, lui ajouter 1 donne un entier plus grand. La notation décrit une taille gigantesque, jamais un maximum parmi les entiers.

Les termes doivent être strictement positifs. Les règles données ici ne couvrent ni 0 ni les entiers négatifs. Si l'un de ces nombres apparaît, il faut d'abord préciser une convention étendue au lieu d'appliquer mécaniquement la récursion.

Une flèche chaînée n'est pas une opération associative. L'écriture a → b → c est un objet défini globalement, pas l'expression (a → b) → c ni a → (b → c). Il faut employer les règles de Conway, sans ajouter de parenthèses ordinaires.

Le terme final 1 est un cas charnière. Une chaîne X → p → 1 se réduit à X → p ; la formule récursive réservée à p > 1 et q > 1 ne s'applique donc pas. Le bon réflexe est de simplifier d'abord toute fin égale à 1.

« Dépasser la notation de Knuth » décrit une capacité de condensation. Toute chaîne finie vaut un entier fini, que l'on pourrait toujours nommer par sa valeur si l'espace était illimité. La différence pertinente porte sur la brièveté et sur le niveau d'itération encodé.

Le glossaire Conway John Horton situe le mathématicien auquel la notation doit son nom.

L'article Repousser les limites de l’imagination prolonge la réflexion sur les écritures capables de désigner des nombres hors d'échelle.