Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] \| Liste Catégories \| Une page au hasard \| Pages liées

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

Sommaire

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

Notation

In expressions such as a^b, the notation for exponentiation is usually to write the exponent b as a superscript to the base number a. But many environments—such as programming languages and plain-text e-mail— do not support such two-dimensional layout. People have adopted the linear notation a↑b for such environments; the up-arrow suggests 'raising to the power of'. If the character set doesn't contain an up arrow, the caret ^ is used instead.

The superscript notation a^b doesn't lend itself well for generalization, which explains why Knuth chose to work from the inline notation a↑b instead.

A further notation used in this article is ↑ⁿ to indicate an n-arrow operator.

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.

Généralisations

Certains nombres sont si grands que la notation en flèche de Knuth's devient trop encombrante que 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.

This site support the Wikimedia Foundation. This Article originally from Wikipedia. All text is available under the terms of the