Notation des puissances itérées de Knuth

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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.

Introduction[modifier | modifier le code]

Si une rangée de dominos représente un nombre, « incrémenter » ce nombre consiste à ajouter un domino.

Itération d'une fonction simple[modifier | modifier le code]

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

Généralisation[modifier | modifier le code]

À 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[2], 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[3] n-flèche est une suite de opérateurs (n − 1)-flèches. Plus généralement,

Parenthèses et associativité[modifier | modifier le code]

L'exponentiation n'est pas associative, par conséquent l’ordre dans lequel les opérations sont effectuées est important. Ainsi (à savoir ) n'est pas (à savoir ). Dans ce qui précède, les opérations sont effectuées de la droite vers la gauche, autrement dit, on associe les parenthèse de la droite vers la gauche. On choisit 6 561 plutôt que 729. Ce que l'on fait pour , on le fait pour , pour , etc.

Commutativité[modifier | modifier le code]

L'exponentiation n'est pas commutative : si a et b sont différents, est différent de .

Définition des puissances itérées[modifier | modifier le code]

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

pour tous entiers a, b et nb ≥ 0 et n ≥ 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
    R := 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[modifier | modifier le code]

Dans une expression ab, on écrit l'exposant b en lettre supérieure[4]. Mais beaucoup d'environnements, comme les langages de programmation et les courriels en format de texte brut, ne supportent pas cet agencement bidimensionnel. Ils ont donc proposé une notation linéaire, a ** b pour Fortran et ab pour d'autres environnements ; la flèche dirigée vers le haut suggère l'élévation à une puissance. Si le 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 ↑n pour indiquer un opérateur flèche d'ordre n (où ↑1 équivaut à ↑ seul)

Comme nous l'avons dit plus haut, tous ces opérateurs (y compris l'exponentiation classique ab) 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, abc signifie a↑(bc), et non (ab)↑c qui serait alors écrit a↑(b×c) :

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[modifier | modifier le code]

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 hyperopérateurs ou les flèches chaînées de Conway peuvent alors être utilisées.

La flèche de Knuth sera utilisée pour les nombres petits par rapport à ceux-là, tandis que les flèches chaînées ou les hyperopérateurs seront adaptées aux plus grands ; lorsque ces notations elles-mêmes deviennent insuffisantes, comme c'est par exemple le cas pour les suites de Goodstein, il est encore possible d'employer la hiérarchie de croissance rapide (qui revient à peu près à définir la notation , où α est un nombre ordinal quelconque)

Références[modifier | modifier le code]

  1. L'incrémentation est l’opération qui consiste à ajouter à un nombre. Par exemple, dans une notation des entiers par des dominos (ou des petits cailloux), elle consisterait à ajouter un domino (ou un caillou).
  2. Suite A014222 dans l'Encyclopédie en ligne des suites de nombres entiers.
  3. Nous omettons le qualificatif « vers le haut ».
  4. « Lettre supérieure » est l'expression consacrée en typographie.

Bibliographie[modifier | modifier le code]

  • Knuth, Donald E., « Mathematics and Computer Science: Coping with Finiteness », Science, vol. 194, no 4271,‎ , p. 1235–1242 (PMID 17797067, DOI 10.1126/science.194.4271.1235)
  • Knuth, Donald E., « Mathematics and Computer Science : Coping with Finiteness », dans Selected papers on Computer Science, CSLI & Cambridge University Press,

Liens externes[modifier | modifier le code]