Notation des puissances itérées de Knuth

En mathématiques, la notation des puissances itérées de Knuth est une notation qui permet d'écrire de très grands entiers et qui a été introduite par Donald Knuth en 1976. L'idée de cette notation est fondée sur la notion d'exponentiation répétée, au même titre que l'exponentiation consiste en une multiplication itérée ou la multiplication en une addition itérée.

Introduction

Si une rangée de dominos représente un nombre, « incrémenter » ce nombre consiste à ajouter un domino.

Itération d'une fonction simple

L'itération d'une fonction simple est utilisée en arithmétique pour définir une opération plus complexe. À partir de la fonction successeur, qui permet de construire les entiers naturels par incrémentations^[1] successives, l'addition est ainsi définie comme une incrémentation itérée :

${\displaystyle {\begin{matrix}a+b=a+\underbrace {1_{}+1+\dots +1} \\\qquad \quad \ \ b{\mbox{ exemplaires de }}1\end{matrix}}}$

La multiplication est définie comme une addition itérée :

${\displaystyle {\begin{matrix}a\times b=\underbrace {a_{}+a+\dots +a} \\\qquad \quad \ \ b{\mbox{ exemplaires de }}a\end{matrix}}}$

De même, l'exponentiation est définie comme une multiplication itérée :

${\displaystyle {\begin{matrix}a^{b}=\underbrace {a_{}\times a\times \dots \times a} \\\qquad \ b{\mbox{ exemplaires de }}a\end{matrix}}}$

Généralisation

À partir de l'incrémentation comme opération primitive, les itérations successives permettent de définir d'abord l'addition, puis la multiplication, puis l'exponentiation. Knuth a voulu généraliser ce principe ; pour cela il a introduit une notation nouvelle pour l’exponentiation, la flèche vers le haut :

${\displaystyle a\uparrow b=a^{b}}$

qu'il peut ainsi généraliser, utilisant la double flèche vers le haut pour l'exponentiation itérée — qu'il appelle la tétration :

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=\underbrace {a\uparrow a\uparrow \cdots \uparrow a} =a_{}^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}\\\ \ \ b{\mbox{ exemplaires de }}a\end{matrix}}}$

Conformément à cette définition, on obtient :

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27\,\!}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987\,\!}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\,\!}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}\,\!}$

etc.

Le terme ${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}}$ est de la forme ${\displaystyle 12580...39387}$ et a ${\displaystyle 3\,638\,334\,640\,025}$ chiffres^[2], soit plus de ${\displaystyle 3,6\times 10^{12}}$ chiffres décimaux.

Cela permet assurément d'écrire de très grands nombres, mais Knuth ne s'est pas arrêté là. Il a poursuivi en définissant l'opérateur triple flèche vers le haut qui est l'application itérée de l'opérateur double flèche vers le haut :

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} =a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a)))\\\qquad \qquad \ \,b{\mbox{ exemplaires de }}a\end{matrix}}}$ (les opérations étant effectuées de la droite vers la gauche)

puis il a poursuivi avec l'opérateur quadruple flèche vers le haut :

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\\qquad \qquad \quad b{\mbox{ exemplaires de }}a\end{matrix}}}$

et ainsi de suite. La règle générale stipule que l'opérateur^[3] n-flèche ${\displaystyle b}$ est une suite de ${\displaystyle b}$ opérateurs (n − 1)-flèches. Plus généralement,

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\ \dots \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\!-\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b{\mbox{ exemplaires de }}a\end{matrix}}}$

Commutativité

L'exponentiation n'est pas commutative : si a et b sont différents, ${\displaystyle a\uparrow b}$ est différent de ${\displaystyle b\uparrow a}$. Il en est de même pour les opérateurs qui suivent :${\displaystyle \uparrow }$, ${\displaystyle \uparrow \uparrow }$, ${\displaystyle \uparrow \uparrow \uparrow }$, etc.

Parenthèses et associativité

Même si aucune parenthèse n'est écrite, les calculs sont associés prioritairement à droite pour chacun des opérateurs ${\displaystyle \uparrow }$, ${\displaystyle \uparrow \uparrow }$, ${\displaystyle \uparrow \uparrow \uparrow }$, etc.

Exemple : ${\displaystyle 3\uparrow 2\uparrow \uparrow 3\uparrow 4}$ = ${\displaystyle 3\uparrow (2\uparrow \uparrow (3\uparrow 4)))}$

En effet, l'exponentiation n'est pas associative, par conséquent l’ordre dans lequel les opérations sont effectuées est important. Ainsi ${\displaystyle 3\uparrow (2\uparrow 3)}$ (à savoir ${\displaystyle 3\uparrow 8=6\,561}$) n'est pas ${\displaystyle (3\uparrow 2)\uparrow 3}$ (à savoir ${\displaystyle 9\uparrow 3=729}$). Dans ce qui précède, les opérations sont effectuées de la droite vers la gauche, autrement dit, on associe les parenthèses de la droite vers la gauche.

Remarquons qu'en vertu des règles de la puissance, on obtient ${\displaystyle (3\uparrow 2)\uparrow 3}$ = ${\displaystyle (3\uparrow 2)\times (3\uparrow 2)\times (3\uparrow 2)}$ = ${\displaystyle 3\uparrow (2\times 3)}$. Si on choisissait l'association prioritaire à gauche, cela rapporterait le deuxième opérateur de puissance à une 'simple' opération de multiplication. La croissance d'une puissance est plus forte quand on fait croître le terme de droite (c'est à l'origine de la non-commutativité) :

${\displaystyle 3\uparrow (2\uparrow 3)}$ = ${\displaystyle 3\uparrow (2\times 2\times 2)}$ = ${\displaystyle 3\uparrow 8}$ est supérieur à ${\displaystyle (3\uparrow 2)\uparrow 3}$ = ${\displaystyle (3\times 3)\uparrow 3}$ = ${\displaystyle 9\uparrow 3}$ .

L'association est donc choisie prioritaire à droite ; c'est le seul choix qui produit une croissance digne d'un nouveau signe opératoire.
Le résultat de ${\displaystyle 3\uparrow 2\uparrow 3}$ sera donc 6 561 et non 729.

Définition des puissances itérées

Les puissances itérées de Knuth sont définies formellement de la façon suivante :

${\displaystyle a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b}\qquad \qquad \qquad \qquad &&{\mbox{si }}n=1\quad \\1\qquad \qquad \qquad \qquad \ &&{\mbox{si }}b=0\quad \,\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))&&{\mbox{sinon}}\ \,\end{matrix}}\right.}$

pour tous entiers a, b et n où b ≥ 0 et n ≥ 1.

Cette famille de fonctions peut se définir par un programme itératif :

function Knuth(rang: naturel; a, b: naturel) : naturel
begin
if rang = 1
then R = a^b
else begin
    RR:= 1 (* 1 est élément neutre à droite pour l'exponentiation *)
    (* Application b fois de l'opérateur à gauche "a Knuth(rang-1)" *)
    for compteur := 1 to b do R := Knuth(rang-1, a, R)
    end
return R
end.

ou par un programme récursif (en Haskell par exemple) :

(↑) :: Integer -> (Integer, Integer) -> Integer
a ↑ (1,b) = a^b
_ ↑ (_,0) = 1
a ↑ (n,b) = a ↑ (n-1,a ↑ (n,b-1))

Remarques sur la notation

Dans une expression a^b, on écrit l'exposant b en lettre supérieure^[4]. Mais beaucoup d'environnements, comme les langages de programmation et les courriels en format de texte brut, ne supportent pas cet agencement bidimensionnel. Ils ont donc proposé une notation linéaire, a**b pour Fortran et a↑b pour d'autres environnements ; la flèche dirigée vers le haut suggère l'élévation à une puissance. Si le jeu de caractères ne contient pas de flèche, l'accent circonflexe ^ ou les deux astérisques ** sont utilisés.

Une autre notation utilisée dans cet article est ↑ⁿ pour indiquer un opérateur flèche d'ordre n (où ↑¹ équivaut à ↑ seul).

Comme nous l'avons dit plus haut, tous ces opérateurs (y compris l'exponentiation classique a↑b) ne sont pas associatifs, et, en l'absence de parenthèses, doivent être associés, de droite à gauche, c'est-à-dire que l'évaluation se fait de la droite vers la gauche pour une expression qui contient au moins deux de ces opérateurs. Par exemple, a↑b↑c signifie a↑(b↑c), et non (a↑b)↑c qui serait alors écrit a↑(b×c) :

${\displaystyle 3\uparrow \uparrow 3=3\uparrow ^{2}3=3^{3^{3}}{\mbox{ vaut }}3^{(3^{3})}=3^{27}=7\,625\,597\,484\,987{\text{ et non }}\left(3^{3}\right)^{3}=27^{3}=3^{(3\cdot 3)}=3^{9}=19\,683.}$

Il existe une bonne raison de choisir cette évaluation de droite à gauche ; en effet, si le choix avait été de gauche à droite, alors a↑↑b aurait signifié a↑(a↑(b-1)) et ↑↑ n'aurait pas été un nouvel opérateur.

Généralisations de la notation de Knuth

Certains nombres sont si grands que la notation en flèche de Knuth devient trop encombrante pour les décrire. C'est par exemple le cas du nombre de Graham. Les flèches chaînées de Conway peuvent alors être utilisées.

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&&=&&a\to b\to n\\{\mbox{(Knuth)}}&&&&{\mbox{(Conway)}}\end{matrix}}}$

La flèche de Knuth sera utilisée pour les nombres petits par rapport à ceux-là, tandis que les flèches chaînées seront adaptées aux plus grands ; lorsque ces notations elles-mêmes deviennent insuffisantes, comme c'est par exemple le cas pour les suites de Goodstein, il est encore possible d'employer la hiérarchie de croissance rapide (qui revient à peu près à définir la notation ${\displaystyle a\uparrow ^{\alpha }b}$, où α est un nombre ordinal quelconque).

Références

1. L'incrémentation est l’opération qui consiste à ajouter ${\displaystyle 1}$ à un nombre. Par exemple, dans une notation des entiers par des dominos (ou des petits cailloux), elle consisterait à ajouter un domino (ou un caillou).
2. Suite A014222 dans l'Encyclopédie en ligne des suites de nombres entiers.
3. Nous omettons le qualificatif « vers le haut ».
4. « Lettre supérieure » est l'expression consacrée en typographie.

Bibliographie

• (en) Knuth, Donald E., « Mathematics and Computer Science: Coping with Finiteness », Science, vol. 194, n^o 4271,‎ 1976, p. 1235–1242 (PMID 17797067, DOI 10.1126/science.194.4271.1235)

Voir aussi

Articles connexes

• Puissance d'un nombre

Liens externes

• Sur le blog de Mickaël Launay