Hyperopération

Hyperopération

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 croit 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].

Sommaire

Définition

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)

Pour n = 0, 1, 2, 3, cette définition reproduit les opérations arithmétiques élémentaires. Par convention, 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 Hn Operation Définition Noms Domaines de validité
0 H0(a,b) b + 1 { 1 + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } successeur, "zération" b réel
1 H1(a,b) a + b { a + {\underbrace{1 + 1 + 1 + \cdots + 1}_{b}} } addition a et b réels
2 H2(a,b) a\cdot b { {\underbrace{a + a + a + \cdots + a}} \atop{b} } multiplication a et b réels
3 H3(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 H4(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 H5(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 H6(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

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 ne 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

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

Références


  1. ↑ a, b et c Daniel Geisler, « What lies beyond exponentiation? », 2003. Consulté le 2009-04-17
  2. ↑ a et b A. J. Robbins, « Home of Tetration », 2005-11. Consulté le 2009-04-17
  3. ↑ a et b C. A. Rubtsov and G. F. Romerio, « Ackermann's Function and New Arithmetical Operation », 2005-12. Consulté le 2009-04-17
  4. ↑ a, b, c et d R. L. Goodstein, « Transfinite Ordinals in Recursive Number Theory », dans Journal of Symbolic Logic, vol. 12, no 4, Dec. 1947, p. 123–129 [texte intégral, lien DOI (pages consultées le 2009-04-17)] 
  5. ↑ Harvey M. Friedman, « Long Finite Sequences », dans Journal of Combinatorial Theory, Series A, vol. 95, no 1, Jul. 2001, p. 102–144 [texte intégral, lien DOI (pages consultées le 2009-04-17)] 
  6. ↑ Manuel Lameiras Campagnola and Cristopher Moore and José Félix Costa, « Transfinite Ordinals in Recursive Number Theory », dans Journal of Complexity, vol. 18, no 4, Dec. 2002, p. 977–1000 [texte intégral (page consultée le 2009-04-17)] 
  7. ↑ Marc Wirz, « Characterizing the Grzegorczyk hierarchy by safe recursion », CiteSeer, 1999. Consulté le 2009-04-21
  8. ↑ Markus Müller, « Reihenalgebra », 1993. Consulté le 2009-04-17
  9. ↑ a et b Robert Munafo, « Inventing New Operators and Functions », Large Numbers at MROB, 1999-11. Consulté le 2009-04-17
  10. ↑ I. N. Galidakis, « Mathematics », 2003. Consulté le 2009-04-17
  11. ↑ Albert A. Bennett, « Note on an Operation of the Third Grade », dans Annals of Mathematics, Second Series, vol. 17, no 2, Dec. 1915, p. 74–75 [texte intégral (page consultée le 2009-04-17)] 
  12. ↑ a et b Wilhelm Ackermann, « Zum Hilbertschen Aufbau der reellen Zahlen », dans Mathematische Annalen, vol. 99, 1928, p. 118–133 [lien DOI] 
  13. ↑ Paul E. Black, « Ackermann's function », Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology (NIST), 2009-03-16. Consulté le 2009-04-17
  14. ↑ Robert Munafo, « Versions of Ackermann's Function », Large Numbers at MROB, 1999-11-03. Consulté le 2009-04-17
  15. ↑ J. Cowles and T. Bailey, « Several Versions of Ackermann's Function », Dept. of Computer Science, University of Wyoming, Laramie, WY, 1988-09-30. Consulté le 2009-04-17
  16. ↑ Donald E. Knuth, « Mathematics and Computer Science: Coping with Finiteness », dans Science, vol. 194, no 4271, Dec. 1976, p. 1235–1242 [texte intégral, lien PMID, lien DOI (pages consultées le 2009-04-21)] 
  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. ↑ K. K. Nambiar, « Ackermann Functions and Transfinite Ordinals », dans Applied Mathematics Letters, vol. 8, no 6, 1995, p. 51–53 [texte intégral, lien DOI (pages consultées le 2009-04-21)] 

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Hyperopération de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Hyperstructure — The hyperstructures are algebraic structures equipped with, at least, one multivalued operation, called hyperoperation. The largest classes of the hyperstructures are the ones called Hv – structures. A Hyperoperation (*) on a non empty set H is a …   Wikipedia

  • Fonction d'Ackermann — Dans la théorie de la récursivité, la fonction d Ackermann (aussi appelée fonction d Ackermann Péter), est un exemple simple de fonction récursive non récursive primitive, trouvée en 1926 par Wilhelm Ackermann. Elle est souvent présentée sous la… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Pentation — Le pentation est la répétition de l opération de la tétration, comme la tétration est la répétition de l opération de l exponentiation. Le pentation est un hyperopération. Comme la tétration, le pentation a de petites applications réelles. Il est …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”