Wiki Googologie
Advertisement
Wiki Googologie

La notation des puissances itérées de Knuth[1] ou la notation flèche vers le haut[2] est une notation largement utilisée pour les hyperopérateurs, introduite par Donald Knuth en 1976 pour représenter les grands nombres.[3][4]

Knuth a introduit a↑b comme a^b et comme . En particulier, a↑b est l'exponentiation, a↑↑b est la tétration, a↑↑↑b est la pentation, et en général a↑nb est la (n+2)ème hyperopération.

Définition

Nous expliquons l'intention précise de la définition originale de Knuth. Pour tout entier positif a, b, et n, a↑nb est défini par la voie récursive suivante :

Cette notation donne une fonction totale calculable

désigne l'ensemble des entiers positifs. Le lecteur doit faire attention au fait que certains auteurs l'étendent implicitement pour que a↑n0 = 1 tienne pour tout entier positif a et n.

Propriétés

Elle satisfait les relations suivantes, qui caractérisent également la notation, pour tout entier positif a, b et n :

Ici, a↑nb est considéré comme un raccourci pour avec n puissances. Ainsi, par exemple, on a .

Les opérateurs de la notation puissances itérées sont associatifs à droite ; a↑b↑c signifie toujours a↑(b↑c).

Notations alternatives

L'exponentiation s'écrit ab, mais dans l'environnement où l'exposant n'est pas disponible, comme le langage de programmation et le courrier électronique, les gens utilisent la notation a↑b pour désigner ab. Knuth a utilisé cette notation parce qu'elle peut être étendue et généralisée pour ↑↑ et ↑↑↑. Dans un environnement où le jeu de caractères pour ↑ n'est pas disponible, le caractère caret ^ qui est disponible dans le code ASCII est utilisé à la place de ↑. En fait, l'expression a^b pour l'exponentiation est utilisée dans de nombreux langages de programmation aujourd'hui. Par conséquent, les expressions de la notation des puissances itérées en code ASCII sont a^b, a^^b, a^^^b, .... L'expression a**b pour l'exponentiation est également utilisée dans certains langages de programmation, et donc l'expression a**b (exponentiation), a***b (tétration), a****b (pentation), ... est également utilisée pour la notation en code ASCII.

Comparaison avec d'autres notations

Pour la comparaison avec la notation des flèches chaînées,

a↑cb = a→b→c

Pour la comparaison avec la fonction d'Ackermann,

A(x,y) = 2↑x-2(y+3) - 3

Pour la comparaison avec la notation hyper-E,[5]

Par conséquent,

  • a↑b = E(a)b
  • a↑↑b = E(a)1#b
  • a↑↑↑b = E(a)1#1#b

Exemples

  • 2↑3 = 2^3 = 8
  • 5↑6 = 5^6 = 15625
  • 10↑100 = 10^100 = googol
  • 3↑↑4 = 3↑3↑3↑3 = 3↑3↑27 = 3^7625597484987 ≈ 1.2580143×10^3638334640024
  • 5↑↑3 = 5↑5↑5 = 5^(5^5) ≈ 1.9110126×10^2184
  • 2↑↑↑2 = 2↑↑2 = 2↑2 = 2^2 = 4
  • 2↑↑↑↑ 2 = 2↑↑↑2 = 2↑↑2 = 2↑2 = 2^2 = 4
  • 3↑↑↑2 = 3↑↑3 = 3↑3↑3 = 3^(3^3) = 3^27 = 7625597484987
  • 2↑↑↑3 = 2↑↑2↑↑2 = 2↑↑4 = 2↑2↑2↑2 = 2↑2↑4 = 2↑16 = 65536
  • 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑7625597484987 = tritri
  • a↑n+12 = a↑na

Références

  1. Notation des puissances itérées de Knuth, Wikipédia
  2. David Louapre, Quel est le plus grand nombre possible utile ?, Science étonnante, 28 Avril 2014
  3. Donald E. Knuth, Mathematics and Computer Science: Coping with Finiteness, Advances in Our Ability to Compute are Bringing Us Substantially Closer to Ultimate Limitations, Science 194, pp. 1235--1242, 1976.
  4. Knuth Up-Arrow Notation from Wolfram Mathworld
  5. Fish, Comparison of up-arrow notation with hyper-E notation 1 juillet 2021
Advertisement