Notation des puissances itérées de Knuth Article, Signification, Explication
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.
| Table of contents |
|
2 Notation 3 Définition 4 Généralisations |
La multiplication peut être définie comme une addition itérée :
Dans des expressions comme ab, la notation pour l'exponentiation consiste généralement à écrire l'exposant b comme une annotation à la base numérique a. Le problème est que bon nombre d'environnements — comme les langages de programmation et le format « texte brut » dans les e-mails — n'acceptent pas une telle notation bi-dimensionnelle. Les gens ont adopté l'écriture linéaire a↑b pour ce genre d'environnements; la flèche « ↑ » suggère l'expression «élever à la puissance de». Si le jeu de caractères ne comporte pas cette flèche, l'accent circonflexe « ^ » est alors utilisé.
L'écriture annotée ab se prête mal à une généralisation, ce qui explique pourquoi Donald Knuth a choisi de travailler plutôt sur l'écriture linéaire a↑b.
Juste après dans cet article on utilisera la notation ↑n pour indiquer l'opération de « puissance itérée d'ordre n ».
Les puissances itérées de Knuth sont définies formellement de la façon suivante :
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 :
C'est un article concernant le Notation des puissances itérées de Knuth. La page contient la signification du Notation des puissances itérées de Knuth , Description et explication au sujet de Notation des puissances itérées de Knuth Introduction
et l'exponentiation peut être définie comme une multiplication itérée :
Cela a inspiré Knuth pour définir un opérateur double flèche pour une exponention itérée :
D'après cette définition,
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 :
ainsi que l'opérateur quadruple flèche :
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,Notation
Définition
pour tous entiers a, b et n où b ≥ 0 et n ≥ 1.
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 qui apparaît dans le développement de a↑n+1b comme étant égale à , 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 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és.
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.