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
     {{a + b} \atop \,}  {= \atop \,}  {a  \, + \atop \, }  {{\underbrace{1 + 1 + \cdots + 1}} \atop b \text{ termes}}
  2. multiplication
    {{a \times b = \ } \atop {\ }} {{\underbrace{a + a + \cdots + a}} \atop b\text{ termes}}
  3. exponentiation
    {{a^b = \ } \atop {\ }} {{\underbrace{a \times a \times \cdots \times a}} \atop b\text{ facteurs}}

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): \scriptstyle{a \uparrow^n b = a \uparrow^{n-1} \left(a \uparrow^n (b-1)\right)}. 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 H_n: \mathbb{N} \times \mathbb{N}  \rightarrow \mathbb{N}\,\! indexée par n \in \mathbb{N}, définie récursivement comme suit:


  H_n(a, b) =  
   \begin{cases}
    b + 1 & \text{si } n = 0 \\
    a & \text{si } n = 1, b = 0 \\
    0 & \text{si } n = 2, b = 0 \\
    1 & \text{si } n \ge 3, b = 0 \\
    H_{n-1}(a, H_n(a, b - 1)) & \text{sinon}
   \end{cases}\,\!

(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 H_n Operation Définition Noms Domaines de validité
0 H_0(a,b) b + 1 { 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } successeur, "zération" b réel
1 H_1(a,b) a + b { a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } addition a et b réels
2 H_2(a,b) a\cdot b { {\underbrace{a + a + a + \cdots + a}} \atop{b} } multiplication a et b réels
3 H_3(a,b) a \uparrow b = a^b { {\underbrace{a \cdot a \cdot a \cdot a \cdot \ldots \cdot a}} \atop{b} } exponentiation a > 0, b réel, ou a non nul, b un entier. Extensions dans l'ensemble des nombres complexes.
4 H_4(a,b) a \uparrow\uparrow b { {\underbrace{a \uparrow a \uparrow a \uparrow \cdots \uparrow a}} \atop{b} } tétration a > 0, b entier ≥ −1 (extensions proposées)
5 H_5(a,b) a \uparrow\uparrow\uparrow b ou a \uparrow^3 b { {\underbrace{a \uparrow\uparrow a \uparrow\uparrow \cdots \uparrow\uparrow a}} \atop{b} } pentation a et b entiers, a > 0, b ≥ 0
6 H_6(a,b) a \uparrow^4 b { {\underbrace{a \uparrow^3 a \uparrow^3 \cdots \uparrow^3 a}} \atop{b} } 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 \phi(a, b, n)\,\![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: G(n,a,b) = H_n(a,b)\,\!, la suite des hyperopérations peut être rapprochée de la fonction d'Ackermann \phi(a,b,n)\,\!. La fonction d'Ackermann originelle \phi\,\! utilise la même règle récursive que Goodstein mais diffère d'elle de deux manières : Tout d'abord \phi(a,b,n)\,\! définit une suite d'opérations partant de l'addition (n = 0) plutôt que de la succession. Ensuite, les conditions initiales pour \phi\,\! sont \phi(a, b, 3) = a \uparrow\uparrow (b + 1)\,\!, différant 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 \phi(a,b,3)\,\! = a^{a^{\cdot^{\cdot^{\cdot^a}}}}\,\!, où b compte le nombre d'opérateurs plutôt que le nombre d'opérandes a, comme le fait b dans a\uparrow\uparrow b\,\!, 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 à H_n(a, b)\,\! Commentaire
Notation des flèches de Knuth a \uparrow^{n-2} b\,\! Utilisée par Knuth[16] (pour n ≥ 2), et rencontrée dans divers ouvrages[17],[18].
Notation de Goodstein G(n, a, b)\,\! Utilisée par Reuben Goodstein[4].
Fonction d'Ackermann originelle 
  \begin{matrix}
  \phi(a, b, n-1) \ \text{ pour } 1 \le n \le 3 \\
  \phi(a, b-1, n-1) \ \text{ pour } n > 3
  \end{matrix}\,\!
  Utilisée par Wilhelm Ackermann[12].
Fonction d'Ackermann–Péter A(n, b - 3) + 3 \ \text{pour } a = 2\,\! Ceci correspond aux hyperopérations en base 2.
Notation de Nambiar a \otimes^n b\,\! Utilisée par Nambiar[19]
Notation boîte a {\,\begin{array}{|c|}\hline{\!n\!}\\\hline\end{array}\,} b\,\! Utilisée par Rubtsov et Romerio[3].
Notation exposant a {}^{(n)} b\,\! Utilisée par Robert Munafo[9].
Notation crochets a[n]b\,\! 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? »,‎ 2003 (consulté en 2009-04-17)
  2. a et b (en) A. J. Robbins, « Home of Tetration »,‎ 2005-11 (consulté en 2009-04-17)
  3. a et b (en) C. A. Rubtsov and G. F. Romerio, « Ackermann's Function and New Arithmetical Operation »,‎ 2005-12 (consulté en 2009-04-17)
  4. a, b, c et d (en) R. L. Goodstein, « Transfinite Ordinals in Recursive Number Theory », Journal of Symbolic Logic, vol. 12, no 4,‎ décembre 1947, 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,‎ Jul. 2001, 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,‎ décembre 2002, p. 977–1000 (lire en ligne)
  7. (en) Marc Wirz, « Characterizing the Grzegorczyk hierarchy by safe recursion », CiteSeer,‎ 1999 (consulté en 2009-04-21)
  8. (en) Markus Müller, « Reihenalgebra »,‎ 1993 (consulté en 2009-04-17)
  9. a et b (en) Robert Munafo, « Inventing New Operators and Functions », Large Numbers at MROB,‎ 1999-11 (consulté en 2009-04-17)
  10. (en) I. N. Galidakis, « Mathematics »,‎ 2003 (consulté en 2009-04-17)
  11. (en) Albert A. Bennett, « Note on an Operation of the Third Grade », Annals of Mathematics, Second Series, vol. 17, no 2,‎ décembre 1915, p. 74–75 (lire en ligne)
  12. a et b (en) Wilhelm Ackermann, « Zum Hilbertschen Aufbau der reellen Zahlen », Mathematische Annalen, vol. 99,‎ 1928, 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,‎ 1999-11-03 (consulté en 2009-04-17)
  15. (en) J. Cowles and T. Bailey, « Several Versions of Ackermann's Function », Dept. of Computer Science, University of Wyoming, Laramie, WY,‎ 1988-09-30 (consulté en 2009-04-17)
  16. (en) Donald E. Knuth, « Mathematics and Computer Science: Coping with Finiteness », Science, vol. 194, no 4271,‎ décembre 1976, 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,‎ 2002, 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,‎ 2003, 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,‎ 1995, p. 51–53 (DOI 10.1016/0893-9659(95)00084-4, lire en ligne)