Hyperopération

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 qui prolonge logiquement la suite des opérations arithmétiques élémentaires suivantes :

1. addition (n = 1) :

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

2. multiplication (n = 2) :

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

3. exponentiation (n = 3) :

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

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

La flêche de Knuth au rang m est définie récursivement par : $a\uparrow ^{-1}b=a+b\,$ et $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 : $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 (à 3 arguments), la hiérarchie d'Ackermann, la hiérarchie de Grzegorczyk (plus générale), la version de Goodstein de la fonction d'Ackermann, hyper-n.

Définition

La suite d'hyperopérateurs est la suite d'opérations binaires $H_{n}:\mathbb {N} \times \mathbb {N} \to \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\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	$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 et b réels
4	$H_{4}(a,b)$	$a\uparrow \uparrow b=\ ^{b}a$	${{\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

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 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)$ qui s'approche de la séquence d'hyperopérateurs.

Dans son article de 1947, 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 : $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érent en cela des hyperopérations au-delà de l'exponentiation. 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

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 (pour n ≥ 3), et rencontrée dans divers ouvrages.
Notation de Goodstein	$G(n,a,b)$	Utilisée par Reuben Goodstein.
Fonction d'Ackermann originelle	${\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.
Fonction d'Ackermann-Péter	$A(n,b-3)+3\ {\text{pour }}a=2$	Ceci correspond aux hyperopérations en base 2 ($H_{n}(2,b)$).
Notation de Nambiar	$a\otimes ^{n}b$	Utilisée par Nambiar
Notation boîte	$a{\,{\begin{array}{|c|}\hline {\!n\!}\\\hline \end{array}}\,}b$	Utilisée par Rubtsov et Romerio.
Notation exposant	$a{}^{(n)}b$	Utilisée par Robert Munafo.
Notation indice	$a{}_{(n)}b$	Utilisée par John Donner et Alfred Tarski (pour n ≥ 1).
Notation crochets	$a[n]b$	Utilisée sur des forums, pour des raisons de simplicité.
Notation des flèches chaînées de Conway	$a\rightarrow b\rightarrow (n-2)$	Utilisée par John Horton Conway (pour n ≥ 3).
Notation de Bowers	$\{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 $\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 $\phi$ était moins similaire aux hyperopérations modernes, car ses conditions initiales commencent avec $\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	$F_{0}(a,b)=a+b$
1	$F_{1}(a,b)=a\cdot b$
2	$F_{2}(a,b)=a^{b}$
3	$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	$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 $A(0,b)=2b+1$ (où la base est constante $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. Depuis lors, de nombreux autres auteurs 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 $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	$F_{0}(a,b)=b+1$
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b=e^{\ln(a)+\ln(b)}$
3	$F_{3}(a,b)=a^{b}$
4	$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	$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

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hyperoperation » (voir la liste des auteurs).