Hyperopération

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 : addition, multiplication et exponentiation.

En termes simples et partant du constat suivant :

  1. addition
  2. multiplication
  3. exponentiation

Les hyperopérateurs visent à répondre à la question intuitive suivante "Qu'y a-t-il au-delà de l'exponentiation ?".

On montre qu'on peut créer des opérations de rang supérieur à l'exponentiation en les construisant de manière itérative d'après la précédente, et en utilisant l'égalité suivante, (exprimée dans la notation des flèches de Knuth): . Chacune croît plus vite que la précédente.

Reuben Goodstein[4] proposa de baptiser les opérations au-delà de l'exponentiation par "tétration", "pentation" etc.. .

Des suites similaires ont historiquement porté diverses appellations, telles que la fonction d'Ackermann[1], 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 > 0, b réel, ou a non nul, b un entier. Extensions dans l'ensemble des nombres complexes.
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

Historique[modifier | modifier le code]

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 tetration, pentation etc., 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.)

Notations[modifier | modifier le code]

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 ≥ 2), 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 crochets Utilisée sur des forums, pour des raisons de simplicité.

Voir aussi[modifier | modifier le code]

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


  1. a, b et c (en) Daniel Geisler, « What lies beyond exponentiation? »,‎ (consulté le 17 avril 2009)
  2. a et b (en) A. J. Robbins, « Home of Tetration »,‎ (consulté le 17 avril 2009)
  3. a et b (en) C. A. Rubtsov and G. F. Romerio, « Ackermann's Function and New Arithmetical Operation »,‎ (consulté le 17 avril 2009)
  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, lire en ligne)
  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)
  6. (en) Manuel Lameiras Campagnola and Cristopher Moore and José Félix Costa, « Transfinite Ordinals in Recursive Number Theory », Journal of Complexity, vol. 18, no 4,‎ , p. 977–1000 (lire en ligne)
  7. (en) Marc Wirz, « Characterizing the Grzegorczyk hierarchy by safe recursion », CiteSeer,‎ (consulté le 21 avril 2009)
  8. (en) Markus Müller, « Reihenalgebra »,‎ (consulté le 17 avril 2009)
  9. a et b (en) Robert Munafo, « Inventing New Operators and Functions », Large Numbers at MROB,‎ (consulté le 17 avril 2009)
  10. (en) I. N. Galidakis, « Mathematics »,‎ (consulté le 17 avril 2009)
  11. (en) Albert A. Bennett, « Note on an Operation of the Third Grade », Annals of Mathematics, Second Series, vol. 17, no 2,‎ , p. 74–75 (lire en ligne)
  12. a et b (en) 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 » (ArchiveWikiwixArchive.isGoogleQue faire ?), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology (NIST), 2009-03-16, consulté le 2009-04-17
  14. (en) Robert Munafo, « Versions of Ackermann's Function », Large Numbers at MROB,‎ (consulté le 17 avril 2009)
  15. (en) J. Cowles and T. Bailey, « Several Versions of Ackermann's Function », Dept. of Computer Science, University of Wyoming, Laramie, WY,‎ (consulté le 17 avril 2009)
  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)
  17. (en) Daniel Zwillinger, CRC standard mathematical tables and formulae, 31st Edition, Boca Raton, CRC Press, , 31e éd. (ISBN 978-1-58488-291-6), p. 4
  18. (en) Eric W. Weisstein, CRC concise encyclopedia of mathematics, 2nd Edition, Boca Raton, CRC Press, , 2e éd. (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)