Voir la source de 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 [[Entier naturel|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 [[produit mathématique|multiplication]] itérée ou la multiplication en une [[addition]] itérée.

== Introduction ==
[[Fichier:Dominoeffect.png|vignette|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''<ref>L'''incrémentation'' est l’opération qui consiste à ajouter <math>1</math> à un nombre. Par exemple, dans une notation des entiers par des dominos (ou des petits cailloux), elle consisterait à ajouter un domino (ou un caillou).</ref> successives, l'addition est ainsi définie comme une [[incrémentation]] itérée :
:<math>
  \begin{matrix}
   a + b=a+\underbrace{1_{}+1+\dots+1}\\
   \qquad\quad\ \ b\mbox{ exemplaires de }1
  \end{matrix}
 </math>

La multiplication est définie comme une addition itérée :
:<math>
  \begin{matrix}
   a\times b=\underbrace{a_{}+a+\dots+a}\\
   \qquad\quad\ \ b\mbox{ exemplaires de }a
  \end{matrix}
 </math>

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

:<math>
  \begin{matrix}
   a^b=\underbrace{a_{}\times a\times\dots\times a}\\
   \qquad\ b\mbox{ exemplaires de }a
  \end{matrix}
 </math>

=== 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 (symbole)#Affichage|flèche vers le haut]]'' :

:<math>a\uparrow b=a^b</math>

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]] :

:<math>
  \begin{matrix}
   a\uparrow\uparrow b=\underbrace{a\uparrow a\uparrow\cdots\uparrow a}=a_{}^{a^{{}^{.\,^{.\,^{.\,^a}}}}}\\
   \ \ \ b\mbox{ exemplaires de }a
  \end{matrix}
 </math>

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

:<math>3\uparrow\uparrow2=3^3=27\,\!</math>
:<math>3\uparrow\uparrow3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987\,\!</math>
:<math>3\uparrow\uparrow4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\,\!</math>
:<math>3\uparrow\uparrow5=3^{3^{3^{3^3}}}\,\!</math>
:etc.

Le terme <math>3\uparrow\uparrow4=3^{3^{3^{3}}}</math> est de la forme <math>12580...39387</math> et a <math>3\,638\,334\,640\,025</math> chiffres<ref>Suite [http://oeis.org/A014222 A014222] dans l'[[Encyclopédie en ligne des suites de nombres entiers]].</ref>, soit plus de <math>3,6 \times 10^{12}</math> (3600 milliards) de 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'' :

:<math>
  \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}
 </math> (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'' :

:<math>
  \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}
 </math>

et ainsi de suite. La règle générale stipule que l'opérateur<ref>Nous omettons le qualificatif « vers le haut ».</ref> ''n''-flèche <math>b</math> est une suite de <math>b</math> opérateurs (''n''&nbsp;−&nbsp;1)-flèches. Plus généralement,

:<math>
  \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}
 </math>

==== Commutativité ====
L'exponentiation n'est pas [[Commutativité|commutative]] : si a et b sont différents, <math>a\uparrow b</math> est différent de <math>b\uparrow a</math>. Il en est de même pour les opérateurs qui suivent :<math>\uparrow</math>, <math>\uparrow\uparrow</math>, <math>\uparrow\uparrow\uparrow</math>, 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 <math>\uparrow</math>, <math>\uparrow\uparrow</math>, <math>\uparrow\uparrow\uparrow</math>, etc.

Exemple : <math>3\uparrow 2\uparrow \uparrow 3 \uparrow 4</math> = <math>3\uparrow (2\uparrow \uparrow (3 \uparrow 4)))</math>

En effet, l'exponentiation n'est pas [[Associativité|associative]], par conséquent l’ordre dans lequel les opérations sont effectuées est important. Ainsi <math>3\uparrow(2\uparrow 3)</math> (à savoir <math>3\uparrow 8 = 6\,561</math>) n'est pas <math>(3\uparrow 2)\uparrow 3</math> (à savoir <math>9\uparrow 3 = 729</math>). 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    <math>(3\uparrow 2)\uparrow 3</math> = <math>(3\uparrow 2)\times(3\uparrow 2)\times(3\uparrow 2)</math> = <math>3\uparrow (2\times 3)</math>. 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é) :

<math>3\uparrow (2\uparrow 3)</math> = <math>3\uparrow (2\times 2\times 2)</math> = <math>3\uparrow 8</math> est supérieur à <math>(3\uparrow 2)\uparrow 3</math> = <math>(3\times 3)\uparrow 3</math> = <math>9\uparrow 3</math> .

L'association est choisie prioritaire à droite. Le résultat de <math>3\uparrow 2\uparrow 3</math> sera donc {{formatnum:6561}} et non {{formatnum:729}}.

== Définition des puissances itérées ==
Les puissances itérées de Knuth sont définies formellement de la façon suivante :
:<math>
  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.
 </math>
pour tous entiers ''a'', ''b'' et ''n'' où ''b''&nbsp;≥&nbsp;0 et ''n''&nbsp;≥&nbsp;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''<sup>''b''</sup>, on écrit l'exposant ''b'' en ''[[Exposant (typographie)|lettre supérieure]]''<ref>« Lettre supérieure » est l'expression consacrée en typographie.</ref>. Mais beaucoup d'environnements, comme les [[langages de programmation]] et les [[courriel]]s en format de texte brut, ne supportent pas cet agencement bidimensionnel. Ils ont donc proposé une notation linéaire, <code>a**b</code> 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 [[Codage des caractères|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 ↑<sup>''n''</sup> pour indiquer un opérateur flèche d'ordre ''n'' (où ↑<sup>1</sup> é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'') :

: <math>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.</math>

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 [[Notation des flèches chaînées de Conway|flèches chaînées de Conway]] peuvent alors être utilisées.

:<math>
  \begin{matrix}
   a\uparrow^n b&&=&&a\to b\to n\\
   \mbox{(Knuth)}&&&&\mbox{(Conway)}
  \end{matrix}
 </math>

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 [[Théorème de Goodstein|suites de Goodstein]], il est encore possible d'employer la [[hiérarchie de croissance rapide]] (qui revient à peu près à définir la notation <math>a\uparrow^\alpha b</math>, où α est un [[nombre  ordinal]] quelconque).

== Références ==
{{références}}

== Bibliographie ==
* {{article |langue=en |auteur=Knuth, Donald E. |année=1976 |date= |titre=Mathematics and Computer Science: Coping with Finiteness |périodique=Science |volume=194 |numéro=4271 |lire en ligne= |pages=1235–1242 |doi=10.1126/science.194.4271.1235 |pmid=17797067 }}

== Voir aussi ==
=== Articles connexes ===
* [[Puissance d'un nombre]]

=== Liens externes ===
* [https://www.youtube.com/watch?v=oqMYAVV-hsA Sur le blog] de [[Mickaël Launay]]

{{Portail|mathématiques}}

[[Catégorie:Grand nombre]]
[[Catégorie:Symbole mathématique]]