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 suivantes :

1. addition (n = 1) :

   ${\displaystyle {{H_{1}(a,b)=a+b} \atop \,}{= \atop \,}{a\,+ \atop \,}{{\underbrace {1+1+\cdots +1} } \atop b{\text{ termes}}}}$

2. multiplication (n = 2) :

   ${\displaystyle {{H_{2}(a,b)=a\times b=\ } \atop {\ }}{{\underbrace {a+a+\cdots +a} } \atop b{\text{ termes}}}}$

3. exponentiation (n = 3) :

   ${\displaystyle {{H_{3}(a,b)=a^{b}=\ } \atop {\ }}{{\underbrace {a\times a\times \cdots \times a} } \atop b{\text{ facteurs}}}}$

Les trois premières valeurs de la fonction de pentation H5(a,2). La valeur approximative de H5(3,2) est 7.626x10^12.

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. ${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b}$.

La flèche de Knuth au rang m est définie récursivement par : ${\displaystyle a\uparrow ^{-1}b=a+b\,}$ et ${\displaystyle a\uparrow ^{m}b=\underbrace {a\uparrow ^{m-1}\left(a\uparrow ^{m-1}\left[a\uparrow ^{m-1}\left(\ldots \left[a\uparrow ^{m-1}\left(a\uparrow ^{m-1}a\right)\right]\ldots \right)\right]\right)} _{\displaystyle b{\mbox{ copies de }}a},\quad m\geq 0}$

Elle peut aussi se définir à l'aide de la règle : ${\displaystyle a\uparrow ^{m}b=a\uparrow ^{m-1}\left(a\uparrow ^{m}(b-1)\right)}$. 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

La suite d'hyperopérateurs est la suite d'opérations binaires ${\displaystyle H_{n}:\mathbb {N} \times \mathbb {N} \to \mathbb {N} }$ indexée par ${\displaystyle n\in \mathbb {N} }$, définie récursivement comme suit :

${\displaystyle 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\geq 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	${\displaystyle H_{n}}$	Operation	Définition	Noms	Domaines de validité
0	${\displaystyle H_{0}(a,b)}$	${\displaystyle b+1}$	${\displaystyle {1+{\underbrace {1+1+1+\cdots +1} _{b}}}}$	successeur, « zération »	b réel
1	${\displaystyle H_{1}(a,b)}$	${\displaystyle a+b}$	${\displaystyle {a+{\underbrace {1+1+1+\cdots +1} _{b}}}}$	addition	a et b réels
2	${\displaystyle H_{2}(a,b)}$	${\displaystyle a\cdot b}$	${\displaystyle {{\underbrace {a+a+a+\cdots +a} } \atop {b}}}$	multiplication	a et b réels
3	${\displaystyle H_{3}(a,b)}$	${\displaystyle a\uparrow b=a^{b}}$	${\displaystyle {{\underbrace {a\cdot a\cdot a\cdot a\cdot \ldots \cdot a} } \atop {b}}}$	exponentiation	a et b réels
4	${\displaystyle H_{4}(a,b)}$	${\displaystyle a\uparrow \uparrow b=\ ^{b}a}$	${\displaystyle {{\underbrace {a\uparrow a\uparrow a\uparrow \cdots \uparrow a} } \atop {b}}}$	tétration	a > 0, b entier ≥ −1 (extensions proposées)
5	${\displaystyle H_{5}(a,b)}$	${\displaystyle a\uparrow \uparrow \uparrow b}$ ou ${\displaystyle a\uparrow ^{3}b}$	${\displaystyle {{\underbrace {a\uparrow \uparrow a\uparrow \uparrow \cdots \uparrow \uparrow a} } \atop {b}}}$	pentation	a et b entiers, a > 0, b ≥ 0
6	${\displaystyle H_{6}(a,b)}$	${\displaystyle a\uparrow ^{4}b}$	${\displaystyle {{\underbrace {a\uparrow ^{3}a\uparrow ^{3}\cdots \uparrow ^{3}a} } \atop {b}}}$	hexation	a et b entiers, a > 0, b ≥ 0

Cas spéciaux

H_n(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

H_n(a, 0) =

0, où n = 2

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

a, où n = 1

H_n(a, −1) =

0, où n = 0, ou n ≥ 4

a − 1, où n = 1

−a, où n = 2

1/a , où n = 3

H_n(2, 2) =

3, où n = 0

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

Histoire

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

12 ans plus tard, Wilhelm Ackermann définit la fonction ${\displaystyle \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 tétration, 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 : ${\displaystyle G(n,a,b)=H_{n}(a,b)}$, la suite des hyperopérations peut être rapprochée de la fonction d'Ackermann ${\displaystyle \phi (a,b,n)}$. La fonction d'Ackermann originelle ${\displaystyle \phi }$ utilise la même règle récursive que Goodstein mais diffère d'elle de deux manières : Tout d'abord ${\displaystyle \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 ${\displaystyle \phi }$ sont ${\displaystyle \phi (a,b,3)=a\uparrow \uparrow (b+1)}$, 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 ${\displaystyle \phi (a,b,3)}$ = ${\displaystyle 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 ${\displaystyle 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 à ${\displaystyle H_{n}(a,b)}$	Commentaire
Notation des flèches de Knuth	${\displaystyle a\uparrow ^{n-2}b}$	Utilisée par Knuth[16] (pour n ≥ 3), et rencontrée dans divers ouvrages[17],[18].
Notation de Goodstein	${\displaystyle G(n,a,b)}$	Utilisée par Reuben Goodstein[4].
Fonction d'Ackermann originelle	${\displaystyle {\begin{matrix}\phi (a,b,n-1)\ {\text{ pour }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ pour }}n>3\end{matrix}}}$	Utilisée par Wilhelm Ackermann[12].
Fonction d'Ackermann-Péter	${\displaystyle A(n,b-3)+3\ {\text{pour }}a=2}$	Ceci correspond aux hyperopérations en base 2 (${\displaystyle H_{n}(2,b)}$).
Notation de Nambiar	${\displaystyle a\otimes ^{n}b}$	Utilisée par Nambiar[19]
Notation boîte	${\displaystyle a{\,{\begin{array}{|c|}\hline {\!n\!}\\\hline \end{array}}\,}b}$	Utilisée par Rubtsov et Romerio[3].
Notation exposant	${\displaystyle a{}^{(n)}b}$	Utilisée par Robert Munafo[9].
Notation indice	${\displaystyle a{}_{(n)}b}$	Utilisée par John Donner et Alfred Tarski (pour n ≥ 1)[20].
Notation crochets	${\displaystyle a[n]b}$	Utilisée sur des forums, pour des raisons de simplicité.
Notation des flèches chaînées de Conway	${\displaystyle a\rightarrow b\rightarrow (n-2)}$	Utilisée par John Horton Conway (pour n ≥ 3).
Notation de Bowers	${\displaystyle \{a,b,n,1\}}$	Utilisée par Jonathan Bowers (pour n ≥ 1).

Variante de départ à partir de a

En 1928, Wilhelm Ackermann a défini une fonction à 3 arguments ${\displaystyle \phi (a,b,n)}$ qui a progressivement évolué vers une fonction à 2 arguments connue sous le nom de la fonction d'Ackermann. La fonction originelle d'Ackermann ${\displaystyle \phi }$ était moins similaire aux hyperopérations modernes, car ses conditions initiales commencent avec ${\displaystyle \phi (a,0,n)=a}$ 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	${\displaystyle F_{0}(a,b)=a+b}$
1	${\displaystyle F_{1}(a,b)=a\cdot b}$
2	${\displaystyle F_{2}(a,b)=a^{b}}$
3	${\displaystyle F_{3}(a,b)=a\uparrow \uparrow (b+1)}$	L'itération de cette opération est différente de l'itération de la tétration.
4	${\displaystyle F_{4}(a,b)=(x\mapsto a\uparrow \uparrow (x+1))^{b}(a)}$	À ne pas confondre avec la pentation.

Une autre condition initiale qui a été utilisée est ${\displaystyle A(0,b)=2b+1}$ (où la base est constante ${\displaystyle a=2}$), due à Rózsa Péter, qui ne forme pas une hiérarchie d'hyperopérations.

Variante de départ à partir de 0

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 H_n(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 ${\displaystyle F_{n}(a,0)=0}$, 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	${\displaystyle F_{0}(a,b)=b+1}$
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a\uparrow \uparrow (b-1)}$	L'itération de cette opération est différente de l'itération de la tétration.
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto a\uparrow \uparrow (x-1)\right)^{b}(0)=0{\text{ si }}a>0}$	À ne pas confondre avec Pentation.

Voir aussi

• Fonction d'Ackermann
• Notation des puissances itérées de Knuth
• Notation des flèches chaînées de Conway
• Hiérarchie de croissance rapide