Hyperopération

Ci-dessous figure la liste des sept premières hyperopérations (de la 0e à la 6e) ( 0⁰ est défini comme 1).

H _n (0, b ) =

b + 1, lorsque n = 0

b , lorsque n = 1

0, lorsque n = 2

1, lorsque n = 3 et b = 0

0, lorsque n = 3 et b > 0

1, lorsque n > 3 et b est pair (y compris 0)

0, lorsque n > 3 et b est impair

H _n (1, b ) =

b , lorsque n = 2

1, lorsque n ≥ 3

H _n ( a , 0) =

0, lorsque n = 2

1, lorsque n = 0, ou n ≥ 3

a , lorsque n = 1

H _n ( a , 1) =

2, lorsque n = 0

a + 1, lorsque n = 1

a , lorsque n ≥ 2

H _n ( a , a ) =

H _n+1 ( a , 2), lorsque n ≥ 1

H _n ( a , −1) =

0, lorsque n = 0, ou n ≥ 4

a − 1, lorsque n = 1

− a , lorsque n = 2

⁠1/un⁠ , lorsque n = 3

H _n (2, 2) =

3, lorsque n = 0

4, lorsque n ≥ 1, facilement démontrable de manière récursive.

L'une des premières discussions sur les hyperopérations est celle d'Albert Bennett en 1914, qui a développé une partie de la théorie des hyperopérations commutatives (voir Wilhelm Ackermann a défini la fonction qui ressemble quelque peu à la séquence d'hyperopérations.

Dans son article de 1947 , Reuben Goodstein a introduit la séquence d'opérations que l'on appelle aujourd'hui hyperopérations , et a également suggéré les noms grecs de tétration , pentation, etc., pour les opérations étendues au-delà de l'exponentiation (car elles correspondent aux indices 4, 5, etc.). En tant que fonction à trois arguments, par exemple, la séquence d'hyperopérations dans son ensemble est considérée comme une version de la fonction d'Ackermann originale — récursive mais non récursive primitive — modifiée par Goodstein pour intégrer la fonction successeur primitive ainsi que les trois autres opérations arithmétiques de base ( addition , multiplication , exponentiation ), et pour réaliser une extension plus continue de celles-ci au-delà de l'exponentiation.

La fonction d'Ackermann originale à trois arguments utilise la même règle de récursion que la version de Goodstein (c'est-à-dire la séquence d'hyperopérations), mais s'en distingue par deux aspects. Premièrement, elle définit une séquence d'opérations commençant par l'addition ( n = 0) plutôt que par la fonction successeur , puis la multiplication ( n = 1), l'exponentiation ( n = 2), etc. Deuxièmement, les conditions initiales de cette fonction donnent , ce qui la différencie des hyperopérations au-delà de l'exponentiation. La signification du b + 1 dans l'expression précédente est que = , où b compte le nombre d' opérateurs (exponentiations), et non le nombre d' opérandes (« a ») comme le fait le b dans , et ainsi de suite pour les opérations de niveau supérieur. (Voir l' article sur la fonction d'Ackermann pour plus de détails.)

Voici une liste des notations utilisées pour les hyperopérations.

Variante commençant par 0

En 1984, C.W. Clenshaw et F.W.J. Olver ont initié la discussion sur l'utilisation des hyperopérations pour prévenir les dépassements de capacité des nombres à virgule flottante . Depuis, de nombreux auteurs ont renouvelé l'intérêt pour l'application des hyperopérations à la représentation en virgule flottante . (Puisque H _{_n} ( a , b ) est défini pour b = -1.) En abordant la tétration , Clenshaw et al. ont supposé la condition initiale , ce qui constitue une nouvelle 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 décalée d'une unité.

n	Opération	Commentaire
0
1
2
3
4		Une forme décalée de tétration . L'itération de cette opération est très différente de celle de la tétration .
5	0" $0F_5(a,b)={\left(x\mapsto a\left[4\right](x-1)\right)}^b\left(0\right)=0\text{if}a>0$0	À ne pas confondre avec la pentecôtisme.

RL Goodstein a utilisé la séquence d'hyperopérateurs pour créer des systèmes de numération pour les entiers non négatifs. La représentation héréditaire complète de l'entier n , au niveau k et en base b , peut être exprimée comme suit en utilisant uniquement les k premiers hyperopérateurs et en utilisant comme chiffres uniquement 0, 1, ..., b − 1, ainsi que la base b elle-même :

• Pour 0 ≤ n ≤ b − 1, n est représenté simplement par le chiffre correspondant.
• Pour n > b − 1, la représentation de n est trouvée récursivement, en représentant d'abord n ​​sous la forme

b [ k ] x _k [ k − 1] x _{k − 1} [ k − 2] ... [2] x ₂ [1] x ₁

où x _k , ..., x ₁ sont les plus grands entiers satisfaisant (à leur tour)

b [ k ] x _k ≤ n

b [ k ] x _k [ k − 1] x _{k − 1} ≤ n

...

b [ k ] x _k [ k − 1] x _{k − 1} [ k − 2] ... [2] x ₂ [1] x ₁ ≤ n

Tout x _i dépassant b − 1 est alors réexprimé de la même manière, et ainsi de suite, en répétant cette procédure jusqu'à ce que la forme résultante ne contienne que les chiffres 0, 1, ..., b − 1, ainsi que la base b .

On peut éviter les parenthèses inutiles en accordant une priorité plus élevée aux opérateurs de niveau supérieur dans l'ordre d'évaluation ; ainsi,

Les représentations de niveau 1 ont la forme b [1] X, avec X également de cette forme ;

Les représentations de niveau 2 ont la forme b [2] X [1] Y, avec X , Y également de cette forme ;

Les représentations de niveau 3 ont la forme b [3] X [2] Y [1] Z, avec X , Y , Z également de cette forme ;

Les représentations de niveau 4 ont la forme b [4] X [3] Y [2] Z [1] W, avec X , Y , Z , W également de cette forme ;

et ainsi de suite.

Dans ce type de représentation héréditaire en base b , la base elle-même apparaît dans les expressions, ainsi que des « chiffres » de l'ensemble {0, 1, ..., b − 1}. Ceci se compare à la représentation ordinaire en base 2 lorsque cette dernière est écrite en fonction de la base b ; par exemple, en notation ordinaire en base 2, 6 = (110) ₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, tandis que la représentation héréditaire de niveau 3 en base 2 est 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). Les représentations héréditaires peuvent être abrégées en omettant les occurrences de [1] 0, [2] 1, [3] 1, [4] 1, etc. ; par exemple, la représentation de niveau 3 en base 2 de 6 ci-dessus s'abrège en 2 [3] 2 [1] 2.

Exemples : Les représentations uniques en base 2 du nombre 266 , aux niveaux 1, 2, 3, 4 et 5, sont les suivantes :

Niveau 1 : 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (avec 133 2)

Niveau 2 : 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)

Niveau 3 : 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

Niveau 4 : 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

Niveau 5 : 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

Les définitions de la séquence d'hyperopération peuvent naturellement être transposées aux systèmes de réécriture de termes (TRS) .

TANT QUE longueur de pile <> 1 { POP 3 éléments ; PUSH 1 ou 5 éléments selon les règles r1, r2, r3, r4, r5 ; }

TANT QUE longueur de pile <> 1 { POP 4 éléments ; PUSH 1 ou 7 éléments selon les règles r6, r7, r8, r9, r10, r11 ; }