puissances itérées de Knuth

notation des puissances itérées de Knuth
notation de Knuth
symbole de Knuth
flèche de Knuth

ARITHMETIQUE

La notation des puissances itérées de Knuth est une notation qui permet d’écrire simplement de très grands nombres. Elle a été introduite par Donald Knuth en 1976.
On connaît déjà le symbole a^b , symbole de l’exponentiation, qui est défini comme une multiplication itérée.
a^b = a*a*…*a où il y a b exemplaires de a.

De façon à généraliser le principe d’itération, Knuth représente l’exponentiation par une flèche orientée vers le haut a ↑ b = a^b

Il note alors : a ↑ ↑ b = a ↑ a ↑ a … ↑ a
Il y a b exemplaires de facteurs a (b « étages » en notation classique).
Exemples : 3 ↑ ↑ 2 = 3² = 27
3 ↑ ↑ 3 = 3²⁷

La notation de Knuth se poursuit avec des triples flèches, etc.

L’exponentiation n’est pas commutative, il en est donc de même pour les doubles flèches et les notations suivantes (triples, etc.).
De plus elle n’est pas associative. 3 ↑ (2 ↑ 3) = 3 ↑ (8) = 3⁸ = 6561 .
(3 ↑ 2) ↑ 3 = 9 ↑ 3 = 729
On n’écrit pas les parenthèses, l’associativité choisie est la priorité à droite (ici celle dont le résultat est 6561)
On obtient très vite des nombres extrêmement grands, qu’on ne peut pas envisager d’écrire avec les notations mathématiques « classiques ».

Il existe d’autres notations permettant d’écrire de très grands nombres, notamment celle due à Conway (voir notation de Conway des grands nombres )