Notation des puissances itérées de Knuth

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

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 basé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.

[modifier] Introduction

La multiplication peut être définie comme une addition itérée :

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

et l'exponentiation peut être définie comme une multiplication itérée :

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

Cela a inspiré Knuth pour définir un opérateur double flèche pour une exponentiation itérée :

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

D'après cette définition,

$3\uparrow\uparrow2=3^3=27\,\!$

$3\uparrow\uparrow3=3^{3^3}=3^{27}=7625597484987\,\!$

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}\,\!$

$3\uparrow\uparrow5=3^{3^{3^{3^3}}}\,\!$

etc.

Même si cela permet déjà d'écrire de très grands nombres, Knuth ne s'est pas arrêté là. Il a poursuivi en définissant l'opérateur triple flèche comme l'application itérée de l'opérateur double flèche :

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

ainsi que l'opérateur quadruple flèche :

$\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 n-flèche se développe comme une suite d'opérateurs (n − 1)-flèches. De façon formelle,

$\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}$

[modifier] Notation

Dans des expressions telles que a^b, la notation pour l'exponentiation est ordinairement d'écrire l'exposant b en exposant au nombre de base a. Mais beaucoup d'environnements, comme les langages de programmation et les e-mails en format de texte brut, ne supportent pas cet agencement bidimensionnel. On a adopté la notation linéaire a↑b pour ces environnements ; la flèche dirigée vers le haut suggère l'élévation à une puissance. Si le jeu de caractère ne contient pas de flèche, l'accent circonflexe ^ est utilisé à la place.

La notation avec exposant a^b ne se prête pas bien à la généralisation, c'est pourquoi Knuth a choisi de travailler à partir de la notation a↑b.

Une autre notation utilisée dans cet article est ↑ⁿ pour indiquer un opérateur flèche d'ordre n.

[modifier] Définition

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

$a\uparrow^n b= \left\{ \begin{matrix} 1\qquad\qquad\qquad\qquad\ &&\mbox{si }b=0\quad\,\\ a^b\qquad\qquad\qquad\qquad&&\mbox{si }n=1\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.

Tous ces opérateurs (y compris l'exponentiation classique a↑b) sont associatifs à droite, 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 vaut a↑(b↑c), et non (a↑b)↑c ; autre exemple :

$3\uparrow\uparrow 3=3^{3^3} \mbox{ vaut }3^{(3^3)}=3^{27}=7625597484987 \mbox{ et non } \left(3^3\right)^3=27^3=19683.$

Il existe une bonne raison de choisir ce sens d'évaluation ; en effet, si le choix inverse avait été fait, alors a↑↑b vaudrait a↑(a↑(b-1)), de telle sorte que ↑↑ ne serait pas réellement un opérateur nouveau. L'associativité à droite est également naturelle puisqu'il est alors possible de réécrire l'expression $a\uparrow^n\cdots\uparrow^na$ qui apparaît dans le développement de a↑ⁿ⁺¹b comme étant égale à $a\uparrow^n\cdots\uparrow^na\uparrow^n1$ , de telle sorte que tous les a sont des opérateurs à gauche de l'opérateur flèche. Cela est important puisque les opérateurs flèche ne sont pas commutatifs.

[modifier] Généralisations

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 hyper opérateurs ou la flèche chaînée de Conway peuvent alors être utilisées.

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

On conseille en général l'utilisation de la flèche de Knuth pour les nombres relativement petits, et la flèche chaînée ou les hyper opérateurs pour les plus grands.