Concept
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. vignette|Si une rangée de dominos représente un nombre, « incrémenter » ce nombre consiste à ajouter un domino. 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 successives, l'addition est ainsi définie comme une incrémentation itérée : La multiplication est définie comme une addition itérée : De même, l'exponentiation est définie comme une multiplication itérée : À 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 : 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 : Conformément à cette définition, on obtient : etc. Le terme est de la forme et a chiffres, soit plus 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 : (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 : et ainsi de suite. La règle générale stipule que l'opérateur n-flèche est une suite de opérateurs (n − 1)-flèches. Plus généralement, L'exponentiation n'est pas commutative : si a et b sont différents, est différent de .