Aller au contenu

Hyperopération

Un article de Wikipédia, l'encyclopédie libre.
Les trois premières valeurs de la fonction de pentation H5(a,2). La valeur approximative de H5(3,2) est 7.626x10^12.

En mathématiques, les hyperopérations (ou hyperopérateurs) constituent une suite infinie d'opérations[1],[2],[3] qui prolonge logiquement la suite des opérations arithmétiques élémentaires suivantes :

  1. addition (n = 1) :
  2. multiplication (n = 2) :
  3. exponentiation (n = 3) :

Reuben Goodstein[4] proposa de baptiser les opérations au-delà de l'exponentiation en utilisant des préfixes grecs : tétration (n = 4), pentation (n = 5), hexation (n = 6), etc. L'hyperopération à l'ordre n peut se noter à l'aide d'une flèche de Knuth au rang n – 2. .

La flêche de Knuth au rang m est définie récursivement par : et

Elle peut aussi se définir à l'aide de la règle : . Chacune croît plus vite que la précédente.

Des suites similaires ont historiquement porté diverses appellations, telles que la fonction d'Ackermann[1] (à 3 arguments), la hiérarchie d'Ackermann[5], la hiérarchie de Grzegorczyk[6],[7] (plus générale), la version de Goodstein de la fonction d'Ackermann[4], hyper-n[1],[8],[9],[2],[10].

Définition

[modifier | modifier le code]

La suite d'hyperopérateurs est la suite d'opérations binaires indexée par , définie récursivement comme suit :

(Remarque : pour n = 0, on peut ignorer le premier argument, car alors l'hyperopérateur consiste simplement à incrémenter le second argument d'une unité : succession.)

Pour n = 0, 1, 2, 3, cette définition reproduit les opérations arithmétiques élémentaires, dans l'ordre : succession, addition, multiplication, exponentiation. Par convention donc, les opérations arithmétiques élémentaires sont également à considérer comme des hyperopérateurs.

Pour n ≥ 4, cette suite se poursuit par des nouvelles opérations.

Voici la liste des 7 premières hyperopérations :

n Operation Définition Noms Domaines de validité
0 successeur, « zération » b réel
1 addition a et b réels
2 multiplication a et b réels
3 exponentiation a et b réels
4 tétration a > 0, b entier ≥ −1 (extensions proposées)
5 ou pentation a et b entiers, a > 0, b ≥ 0
6 hexation a et b entiers, a > 0, b ≥ 0

Cas spéciaux

[modifier | modifier le code]

Hn(0, b) =

0, où n = 2, ou n = 3, b ≥ 1, ou n ≥ 4, b impair (≥ −1)
1, où n = 3, b = 0, ou n ≥ 4, b pair (≥ 0)
b, où n = 1
b + 1, où n = 0

Hn(a, 0) =

0, où n = 2
1, où n = 0, ou n ≥ 3
a, où n = 1

Hn(a, −1) =

0, où n = 0, ou n ≥ 4
a − 1, où n = 1
a, où n = 2
1/a , où n = 3

Hn(2, 2) =

3, où n = 0
4, où n ≥ 1, démontrable facilement par récurrence.

Une des premières discussions autour des hyperopérateurs fut celle d'Albert Bennet[11] en 1914, qui développa la théorie des hypéropérations commutatives.

12 ans plus tard, Wilhelm Ackermann définit la fonction [12] qui s'approche de la séquence d'hyperopérateurs.

Dans son article de 1947[4], Reuben Goodstein introduit la suite d'opérations maintenant appelée hyperopérations et suggéra les noms de tétration, pentationetc. pour les opérations au-delà de l'exponentiation (car ils correspondent aux indices 4, 5, etc. de la suite). C'est une fonction à trois arguments : , la suite des hyperopérations peut être rapprochée de la fonction d'Ackermann . La fonction d'Ackermann originelle utilise la même règle récursive que Goodstein mais diffère d'elle de deux manières : Tout d'abord définit une suite d'opérations partant de l'addition (n = 0) plutôt que de la succession. Ensuite, les conditions initiales pour sont , différent en cela des hyperopérations au-delà de l'exponentiation[13],[14],[15]. La signification du b + 1 dans l'expression qui précède vient que = , où b compte le nombre d'opérateurs plutôt que le nombre d'opérandes a, comme le fait b dans , etc pour les opérations de niveau supérieur (voir la fonction d'Ackermann pour davantage de détails).

De nombreuses notations ont été développées et sont applicables aux hyperopérateurs.

Nom Notation équivalente à Commentaire
Notation des flèches de Knuth Utilisée par Knuth[16] (pour n ≥ 3), et rencontrée dans divers ouvrages[17],[18].
Notation de Goodstein Utilisée par Reuben Goodstein[4].
Fonction d'Ackermann originelle Utilisée par Wilhelm Ackermann[12].
Fonction d'Ackermann-Péter Ceci correspond aux hyperopérations en base 2 ().
Notation de Nambiar Utilisée par Nambiar[19]
Notation boîte Utilisée par Rubtsov et Romerio[3].
Notation exposant Utilisée par Robert Munafo[9].
Notation indice Utilisée par John Donner et Alfred Tarski (pour n ≥ 1)[20].
Notation crochets Utilisée sur des forums, pour des raisons de simplicité.
Notation des flèches chaînées de Conway Utilisée par John Horton Conway (pour n ≥ 3).
Notation de Bowers Utilisée par Jonathan Bowers (pour n ≥ 1).

Variante de départ à partir de a

[modifier | modifier le code]

En 1928, Wilhelm Ackermann a défini une fonction à 3 arguments qui a progressivement évolué vers une fonction à 2 arguments connue sous le nom de la fonction d'Ackermann. La fonction originelle d'Ackermann était moins similaire aux hyperopérations modernes, car ses conditions initiales commencent avec pour tout n > 2. En outre, l'addition est assignée à n = 0, la multiplication à n = 1 et exponentiation à n = 2, de sorte que les conditions initiales produisent des opérations très différentes de la tétration et des hyperopérations suivantes.

n Opération Commentaire
0
1
2
3 L'itération de cette opération est différente de l'itération de la tétration.
4 À ne pas confondre avec la pentation.

Une autre condition initiale qui a été utilisée est (où la base est constante ), due à Rózsa Péter, qui ne forme pas une hiérarchie d'hyperopérations.

Variante de départ à partir de 0

[modifier | modifier le code]

En 1984, C. W. Clenshaw et F. W. J. Olver ont commencé à discuter de l'utilisation des hyperopérations pour empêcher une erreur d'un ordinateur à virgule flottante[21]. Depuis lors, de nombreux autres auteurs[22],[23],[24] ont eu un intérêt pour l'application des hyperopérations à la représentation à virgule flottante (car Hn(a, b) sont tous définis pour b = –1). Tout en discutant de tétration, Clenshaw et al. ont soutenu[pas clair] la condition initiale , et réalise[pas clair] encore une autre hiérarchie d'hyperopérations. Tout comme dans la variante précédente, la quatrième opération est très similaire à la tétration, mais est différente de celle-ci.

n Opération Commentaire
0
1
2
3
4 L'itération de cette opération est différente de l'itération de la tétration.
5 À ne pas confondre avec Pentation.

Références

[modifier | modifier le code]
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hyperoperation » (voir la liste des auteurs).
  1. a b et c (en) Daniel Geisler, « What lies beyond exponentiation? », (consulté le ).
  2. a et b (en) A. J. Robbins, « Home of Tetration », (consulté le )
  3. a et b (en) C. A. Rubtsov et G. F. Romerio, « Ackermann's Function and New Arithmetical Operation », (consulté le ).
  4. a b c et d (en) R. L. Goodstein, « Transfinite ordinals in recursive number theory », Journal of Symbolic Logic, vol. 12, no 4,‎ , p. 123-129 (DOI 10.2307/2266486, JSTOR 2266486).
  5. (en) Harvey M. Friedman, « Long Finite Sequences », Journal of Combinatorial Theory, Series A, vol. 95, no 1,‎ , p. 102-144 (DOI 10.1006/jcta.2000.3154, lire en ligne, consulté le ).
  6. (en) Manuel Lameiras Campagnola, Cristopher Moore et José Félix Costa, « Transfinite Ordinals in Recursive Number Theory », Journal of Complexity, vol. 18, no 4,‎ , p. 977-1000 (lire en ligne, consulté le ).
  7. (en) Marc Wirz, « Characterizing the Grzegorczyk hierarchy by safe recursion », CiteSeer, (consulté le ).
  8. (en) Markus Müller, « Reihenalgebra », (consulté le )
  9. a et b (en) Robert Munafo, « Inventing New Operators and Functions », Large Numbers at MROB, (consulté le ).
  10. (en) I. N. Galidakis, « Mathematics », (consulté le ).
  11. (en) Albert A. Bennett, « Note on an Operation of the Third Grade », Annals of Mathematics, 2e série, vol. 17, no 2,‎ , p. 74-75 (JSTOR 2007124).
  12. a et b (de) Wilhelm Ackermann, « Zum Hilbertschen Aufbau der reellen Zahlen' », Mathematische Annalen, vol. 99,‎ , p. 118-133 (DOI 10.1007/BF01459088).
  13. (en) Paul E. Black, « Ackermann's function »(Archive.orgWikiwixArchive.isGoogleQue faire ?), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology (NIST), (consulté le ).
  14. (en) Robert Munafo, « Versions of Ackermann's Function », Large Numbers at MROB, (consulté le ).
  15. (en) J. Cowles et T. Bailey, « Several Versions of Ackermann's Function », Dept. of Computer Science, University of Wyoming, Laramie, WY, (consulté le ).
  16. (en) Donald E. Knuth, « Mathematics and Computer Science: Coping with Finiteness », Science, vol. 194, no 4271,‎ , p. 1235-1242 (PMID 17797067, DOI 10.1126/science.194.4271.1235, lire en ligne, consulté le ).
  17. (en) Daniel Zwillinger, CRC standard mathematical tables and formulae, Boca Raton, CRC Press, , 31e éd. (ISBN 978-1-58488-291-6), p. 4.
  18. (en) Eric W. Weisstein, CRC Concise Encyclopedia of Mathematics, Boca Raton, CRC Press, , 2e éd., 3242 p. (ISBN 978-1-58488-347-0, LCCN 2002074126), p. 127-128.
  19. (en) K. K. Nambiar, « Ackermann Functions and Transfinite Ordinals », Applied Mathematics Letters, vol. 8, no 6,‎ , p. 51-53 (DOI 10.1016/0893-9659(95)00084-4, lire en ligne, consulté le ).
  20. (en) John Donner et Alfred Tarski, « An extended arithmetic of ordinal numbers », Fundamenta Mathematicae, vol. 65,‎ , p. 95-127.
  21. (en) C. W. Clenshaw et F. W. J. Olver, « Beyond floating point », Journal of the ACM, vol. 31, no 2,‎ , p. 319-328 (DOI 10.1145/62.322429, lire en ligne).
  22. (en) W. N. Holmes, « Composite Arithmetic: Proposal for a New Standard », Computer, vol. 30, no 3,‎ , p. 65-73 (DOI 10.1109/2.573666, lire en ligne, consulté le ).
  23. (en) R. Zimmermann, « Computer Arithmetic: Principles, Architectures, and VLSI Design », Lecture notes, Integrated Systems Laboratory, ETH Zürich, (consulté le ).
  24. (en) T. Pinkiewicz, N. Holmes et T. Jamil, « Design of a composite arithmetic unit for rational numbers », Proceedings of the IEEE, (consulté le ), p. 245-252.