Notation des puissances itérées

La notation des puissances itérées de Knuth ou la notation flèche vers le haut est une notation largement utilisée pour les hyperopérateurs, introduite par Donald Knuth en 1976 pour représenter les grands nombres.

Knuth a introduit a↑b comme a^b et $a \underbrace{\uparrow \cdots \uparrow}_{n \textrm{ times}} b$ comme $\underbrace{a \underbrace{\uparrow \cdots \uparrow}_{n-1 \textrm{ times}} \cdots a \underbrace{\uparrow \cdots \uparrow}_{n-1 \textrm{ times}} a}_{b \textrm{ times}}$. En particulier, a↑b est l'exponentiation, a↑↑b est la tétration, a↑↑↑b est la pentation, et en général a↑ⁿb est la (n+2)ème hyperopération.

Définition

Nous expliquons l'intention précise de la définition originale de Knuth. Pour tout entier positif a, b, et n, a↑ⁿb est défini par la voie récursive suivante :

$a \uparrow^n b = \left\{ \begin{array}{ll} a^b & (n = 1) \\ a & (n > 1, b = 1) \\ a \uparrow^{n-1} (a \uparrow^n (b-1)) & (n > 1, b > 1) \end{array} \right.$

Cette notation donne une fonction totale calculable

$\begin{array}{rl} \uparrow \colon \mathbb{N}_{>0}^3 &\to& \mathbb{N}_{>0} \\ (a,b,n) &\mapsto& a \uparrow^n b, \end{array}$

où $\mathbb{N}_{>0}$ désigne l'ensemble des entiers positifs. Le lecteur doit faire attention au fait que certains auteurs l'étendent implicitement pour que a↑ⁿ0 = 1 tienne pour tout entier positif a et n.

Propriétés

Elle satisfait les relations suivantes, qui caractérisent également la notation, pour tout entier positif a, b et n :

$\begin{array}{rl} a \uparrow^1 b &=& a^b \\ a \uparrow^n 1 &=& a \\ a \uparrow^{n + 1} (b + 1) &=& a \uparrow^n (a \uparrow^{n + 1} b) \\ \end{array}$

Ici, a↑ⁿb est considéré comme un raccourci pour $a \uparrow\uparrow\cdots\uparrow\uparrow b$ avec n puissances. Ainsi, par exemple, on a $a \uparrow^2 b = a \uparrow\uparrow b$.

Les opérateurs de la notation puissances itérées sont associatifs à droite ; a↑b↑c signifie toujours a↑(b↑c).

Notations alternatives

L'exponentiation s'écrit a^b, mais dans l'environnement où l'exposant n'est pas disponible, comme le langage de programmation et le courrier électronique, les gens utilisent la notation a↑b pour désigner a^b. Knuth a utilisé cette notation parce qu'elle peut être étendue et généralisée pour ↑↑ et ↑↑↑. Dans un environnement où le jeu de caractères pour ↑ n'est pas disponible, le caractère caret ^ qui est disponible dans le code ASCII est utilisé à la place de ↑. En fait, l'expression a^b pour l'exponentiation est utilisée dans de nombreux langages de programmation aujourd'hui. Par conséquent, les expressions de la notation des puissances itérées en code ASCII sont a^b, a^^b, a^^^b, .... L'expression a**b pour l'exponentiation est également utilisée dans certains langages de programmation, et donc l'expression a**b (exponentiation), a***b (tétration), a****b (pentation), ... est également utilisée pour la notation en code ASCII.

Comparaison avec d'autres notations

Pour la comparaison avec la notation des flèches chaînées,

a↑^cb = a→b→c

Pour la comparaison avec la fonction d'Ackermann,

A(x,y) = 2↑^x-2(y+3) - 3

Pour la comparaison avec la notation hyper-E,

$a \uparrow^{c}b = E(a)\underbrace{1\#1\#...1\#}_{(1\#) \times (c-1)}b$

Par conséquent,

• a↑b = E(a)b
• a↑↑b = E(a)1#b
• a↑↑↑b = E(a)1#1#b

Exemples

• 2↑3 = 2^3 = 8
• 5↑6 = 5^6 = 15625
• 10↑100 = 10^100 = googol
• 3↑↑4 = 3↑3↑3↑3 = 3↑3↑27 = 3^7625597484987 ≈ 1.2580143×10^3638334640024
• 5↑↑3 = 5↑5↑5 = 5^(5^5) ≈ 1.9110126×10^2184
• 2↑↑↑2 = 2↑↑2 = 2↑2 = 2^2 = 4
• 2↑↑↑↑ 2 = 2↑↑↑2 = 2↑↑2 = 2↑2 = 2^2 = 4
• 3↑↑↑2 = 3↑↑3 = 3↑3↑3 = 3^(3^3) = 3^27 = 7625597484987
• 2↑↑↑3 = 2↑↑2↑↑2 = 2↑↑4 = 2↑2↑2↑2 = 2↑2↑4 = 2↑16 = 65536
• 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑7625597484987 = tritri
• a↑ⁿ⁺¹2 = a↑ⁿa

Pour les non entiers

Fish défini pour \(x > 0, n \ge 1, n \in \mathbb{N}\),

\begin{equation} a \uparrow^n x = \begin{cases} a^x & \text{if } 0 < x \le 1 \text{ or } n=1 \\ a \uparrow^{n-1} (a \uparrow^n (x-1)) & \text{if } 1 < x, 1 < n \end{cases} \end{equation}

De cette définition,

\begin{align*} 10^{100} &= 10 \uparrow 10 \uparrow 2 = 10 \uparrow 10 \uparrow 10 \uparrow \log_{10}(2) \\ &\approx 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 2.301 \\ 10^{10^{100}} &= 10 \uparrow 10 \uparrow 10 \uparrow 2 \approx 10 \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.301 = 10 \uparrow \uparrow 3.301 \\ 3 \uparrow \uparrow \uparrow 3 &= 3 \uparrow \uparrow 7625597484987 \\ &\approx 10 \uparrow \uparrow 7625597484986.041 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 12.88227 \\ &\approx 10 \uparrow \uparrow 10 \uparrow 10 \uparrow 10 \uparrow 0.04532 \\ &= 10 \uparrow \uparrow 10 \uparrow \uparrow 2.04532 \\ &\approx 10 \uparrow \uparrow 10 \uparrow \uparrow 10 \uparrow \uparrow 0.31076 \\ &= 10 \uparrow \uparrow \uparrow 2.31076 \\ \end{align*}