puissances itérées de Knuth

Écrire 3 × 3 × 3 donne 3³. Empiler ensuite trois 3 en puissances produit 3 élevé à la puissance 3³. Les flèches de Knuth condensent ce geste : 3 ↑↑ 3 décrit cette tour de trois étages.

Une flèche signifie « élever à une puissance ». Deux flèches répètent l’exponentiation ; trois flèches répètent à leur tour l’opération à deux flèches. Un symbole de plus change donc radicalement l’échelle du nombre.

Introduite par Donald Knuth en 1976, la notation à flèches ascendantes définit une hiérarchie d’opérations sur des entiers. La base est notée a, le second argument b et le nombre de flèches n. Une flèche redonne l’exponentiation : a ↑ b = a^b.

Pour une base a strictement positive, un entier b positif ou nul et un niveau n au moins égal à 1, la définition récursive est :Cette règle fixe notamment a ↑↑ 1 = a et a ↑↑ 2 = a^a.

La double flèche construit une tour d’exponentielles de base a et de hauteur b : a ↑↑ 3 = a élevé à la puissance a^a. La triple flèche itère cette opération à deux flèches, et le principe continue avec davantage de flèches. Les tours se lisent depuis le sommet, donc avec un parenthésage à droite. Ainsi, 3 ↑ (2 ↑ 3) = 3⁸ = 6 561, tandis que (3 ↑ 2) ↑ 3 = 9³ = 729.

Calculons 3 ↑↑ 3. La double flèche demande une tour de puissances de base 3, et son second argument fixe ici une hauteur de trois étages.

Données :
base : 3 ;
nombre de flèches : 2 ;
hauteur de la tour : 3.

1. Développer la double flèche en une tour : 3 ↑↑ 3 = 3 élevé à la puissance 3³.
2. Commencer au sommet : 3³ = 27.
3. Remplacer l’exposant obtenu : 3 ↑↑ 3 = 3²⁷.
4. Calculer la dernière puissance : 3²⁷ = 7 625 597 484 987.

Le résultat exact est donc 7 625 597 484 987. Pour le contrôler sans redévelopper toute la tour, on applique la récurrence : 3 ↑↑ 3 = 3 ↑ (3 ↑↑ 2), puis 3 ↑↑ 2 = 3³ = 27. On retrouve bien 3²⁷.

Pour écrire une petite tour, la forme développée reste la plus lisible. Dès que la hauteur augmente, la double flèche évite une succession d’exposants : le second argument conserve exactement le nombre d’étages.

Pour calculer une expression encore accessible, on commence par la partie la plus haute ou la plus intérieure. Si l’écriture décimale devient impraticable, on garde la notation à flèches : elle décrit le nombre exactement sans prétendre en afficher tous les chiffres.

Pour comparer plusieurs expressions, le nombre de flèches donne un indice sur leur structure, mais il ne suffit pas à les ordonner. Il faut tenir compte ensemble de la base, des arguments et des parenthèses, puis, si nécessaire, comparer des valeurs ou établir des bornes. Une autre notation des grands nombres, comme celle de Conway, exige une traduction de ses propres règles avant toute comparaison.

Une puissance de puissance parenthésée à gauche n’est pas une tour lue à droite. Pour trancher, calculez l’exposant concerné : (3²)³ = 729, alors que 3 élevé à la puissance 2³ vaut 6 561.

La notation scientifique écrit un nombre sous la forme d’un coefficient multiplié par une puissance de dix. Elle expose un ordre de grandeur ; les flèches de Knuth encodent l’itération qui construit le nombre.

La notation de Conway des grands nombres est un autre système compact. La présence d’une chaîne chez Conway, plutôt que de flèches ascendantes, signale qu’il faut appliquer une autre définition.

La hauteur commence à 1 dans la lecture usuelle d’une tour. Avec deux flèches, 3 ↑↑ 1 = 3 et 3 ↑↑ 2 = 3³ = 27. Écrire 3 ↑↑ 2 = 3² confond la hauteur avec un exposant ordinaire.

Les parenthèses changent le résultat. Sans parenthèses, une tour de puissances est conventionnellement évaluée à droite. Si une expression doit être lue à gauche, les parenthèses sont indispensables ; sinon 3 ↑ (2 ↑ 3) et (3 ↑ 2) ↑ 3 seraient confondus.

Ajouter une flèche ne revient pas à ajouter une puissance. Trois flèches itèrent toute l’opération à deux flèches. Il faut revenir à la définition récursive, plutôt que prolonger visuellement une tour comme si seule sa hauteur augmentait.

Une écriture compacte n’est pas une approximation. Lorsque le développement décimal est trop long pour être affiché, l’expression à flèches reste une désignation exacte. On conserve cette forme symbolique au lieu d’annoncer un nombre de chiffres non calculé.

Le glossaire notation de Conway des grands nombres présente une autre syntaxe conçue pour prolonger l’écriture compacte de nombres gigantesques.