Гипероперация

В математике последовательность гиперопераций ^{[nb 1]} представляет собой бесконечную последовательность арифметических операций ( в данном контексте называемых гипероперациями ) ^{[1] [11] [13]} , которая начинается с унарной операции ( функции-последователя с n = 0). Последовательность продолжается бинарными операциями сложения ( n = 1), умножения ( n = 2) и возведения в степень ( n = 3).

После этого последовательность продолжается с дальнейшими бинарными операциями, выходящими за пределы возведения в степень, используя правую ассоциативность . Для операций за пределами возведения в степень n-й член этой последовательности назван Рубеном Гудштейном в честь греческого префикса n с суффиксом -ation (например, тетрация ( n = 4), пентация ( n = 5), гексация ( n = 6) и т. д.) ^[5] и может быть записан как с использованием n − 2 стрелок в нотации Кнута со стрелкой вверх . Каждая гипероперация может быть понята рекурсивно в терминах предыдущей следующим образом:

${\displaystyle a[n]b=\underbrace {a[n-1](a[n-1](a[n-1](\cdots [n-1](a[n-1](a[n-1]a))\cdots )))} _{\displaystyle b{\mbox{ копий }}a},\quad n\geq 2}$

Его также можно определить в соответствии с частью определения, содержащей правило рекурсии, как в версии функции Аккермана со стрелкой вверх Кнута :

${\displaystyle a[n]b=a[n-1]\left(a[n]\left(b-1\right)\right),\quad n\geq 1}$

Это можно использовать для простого отображения чисел, намного больших, чем те, которые может показать научная запись , например, число Скьюза и гуголплексплекс (например, намного больше числа Скьюза и гуголплексплекса), но есть некоторые числа, которые даже они не могут легко показать, например, число Грэма и TREE(3) . ^[14]${\displaystyle 50[50]50}$

Это правило рекурсии является общим для многих вариантов гиперопераций.

Последовательность гиперопераций — это последовательность бинарных операций , рекурсивно определяемая следующим образом:${\displaystyle H_{n}(a,b)\двоеточие (\mathbb {N} _{0})^{3}\rightarrow \mathbb {N} _{0}}$ ${\displaystyle H_{n}\двоеточие (\mathbb {N} _{0})^{2}\rightarrow \mathbb {N} _{0}}$

${\displaystyle H_{n}(a,b)=a[n]b={\begin{cases}1+b&{\text{if }}n=0\\a&{\text{if }}n=1{\text{ and }}b=0\\0&{\text{if }}n=2{\text{ and }}b=0\\1&{\text{if }}n\geq 3{\text{ and }}b=0\\H_{n-1}(a,H_{n}(a,b-1))&{\text{inotherwise}}\end{cases}}}$

(Обратите внимание, что при n = 0 бинарная операция по сути сводится к унарной операции ( функции-последователя ) путем игнорирования первого аргумента.)

Для n = 0, 1, 2, 3 это определение воспроизводит основные арифметические операции следования (которая является унарной операцией), сложения , умножения и возведения в степень соответственно, как

${\displaystyle {\begin{aligned}H_{0}(a,b)&=1+b,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\\H_{3}(a,b)&=a\uparrow {b}=a^{b}.\end{aligned}}}$

Операции для n ≥ 3 можно записать в нотации Кнута со стрелкой вверх .${\displaystyle H_{n}}$

Так какая же будет следующая операция после возведения в степень? Мы определили умножение так, что и определили возведение в степень так, что поэтому кажется логичным определить следующую операцию, тетрацию, так, что с башней из трех «а». Аналогично, пентация (a, 3) будет тетрацией(a, тетрацией(a, a)), с тремя «а» в ней.${\displaystyle H_{2}(a,3)=a[2]3=a\times 3=a+a+a,}$${\displaystyle H_{3}(a,3)=a[3]3=a\uparrow 3=a^{3}=a\times a\times a,}$${\displaystyle H_{4}(a,3)=a[4]3=a\uparrow \uparrow 3=\operatorname {тетрация} (a,3)=a^{a^{a}},}$

${\displaystyle {\begin{align}H_{4}(a,b)&=a\uparrow \uparrow {b},\\H_{5}(a,b)&=a\uparrow \uparrow \uparrow {b},\\\ldots &\\H_{n}(a,b)&=a\uparrow ^{n-2}b{\text{ for }}n\geq 3,\\\ldots &\\\end{align}}}$

Обозначение Кнута можно распространить на отрицательные индексы ≥ −2 таким образом, чтобы оно согласовывалось со всей последовательностью гиперопераций, за исключением задержки в индексации:

${\displaystyle H_{n}(a,b)=a\uparrow ^{n-2}b{\text{ для }}n\geq 0.}$

Таким образом, гипероперации можно рассматривать как ответ на вопрос «что дальше» в последовательности : преемник , сложение , умножение , возведение в степень и т. д. Отмечая, что

${\displaystyle {\begin{align}a+b&=1+(a+(b-1))\\a\cdot b&=a+(a\cdot (b-1))\\a^{b}&=a\cdot \left(a^{(b-1)}\right)\\a[4]b&=a^{a[4](b-1)}\end{align}}}$

проиллюстрирована связь между основными арифметическими операциями, что позволяет естественным образом определить более высокие операции, как указано выше. Параметры иерархии гиперопераций иногда называют их аналогичным термином возведения в степень; ^[15] так, a — это основание , b — это показатель степени (или гиперпоказатель степени ), ^[12] и n — это ранг (или степень ), ^[6] и, кроме того, читается как « b -я n -ация числа a », например, читается как «9-я тетрация числа 7» и читается как «789-я 123-ация числа 456».${\displaystyle H_{n}(a,b)}$${\displaystyle H_{4}(7,9)}$${\displaystyle H_{123}(456,789)}$

В общих чертах, гипероперации — это способы соединения чисел, которые увеличиваются в росте на основе итерации предыдущей гипероперации. Концепции следования, сложения, умножения и возведения в степень — все это гипероперации; операция следования (производящая x + 1 из x ) является наиболее примитивной, оператор сложения указывает, сколько раз 1 должна быть добавлена ​​к себе самой для получения конечного значения, умножение указывает, сколько раз число должно быть добавлено к себе самой, а возведение в степень относится к тому, сколько раз число должно быть умножено само на себя.

Определим итерацию функции f двух переменных как

${\displaystyle f^{x}(a,b)={\begin{cases}f(a,b)&{\text{if }}x=1\\f(a,f^{x-1}(a,b))&{\text{if }}x>1\end{cases}}}$

Последовательность гиперопераций может быть определена в терминах итерации следующим образом. Для всех целых чисел определите${\displaystyle x,n,a,b\geq 0,}$

${\displaystyle {\begin{array}{lcl}H_{0}(a,b)&=&b+1\\H_{1}(a,0)&=&a\\H_{2}(a,0)&=&0\\H_{n+3}(a,0)&=&1\\H_{n+1}(a,b+1)&=&H_{n}^{b+1}(a,H_{n+1}(a,0))\\H_{n}^{x+2}(a,b)&=&H_{n}(a,H_{n}^{x+1}(a,b))\end{array}}}$

Так как итерация ассоциативна , последнюю строку можно заменить на

${\displaystyle {\begin{array}{lcl}H_{n}^{x+2}(a,b)&=&H_{n}^{x+1}(a,H_{n}(a,b))\end{array}}}$

Определения последовательности гиперопераций естественным образом могут быть перенесены в системы переписывания терминов (TRS) .

Основное определение последовательности гиперопераций соответствует правилам редукции

${\displaystyle {\begin{array}{lll}{\text{(r1)}}&H(0,a,b)&\rightarrow &S(b)\\{\text{(r2)}}&H(S(0),a,0)&\rightarrow &a\\{\text{(r3)}}&H(S(S(0)),a,0)&\rightarrow &0\\{\text{(r4)}}&H(S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r5)}}&H(S(n),a,S(b))&\rightarrow &H(n,a,H(S(n),a,b))\end{array}}}$

Для вычисления можно использовать стек , который изначально содержит элементы .${\displaystyle H_{n}(a,b)}$${\displaystyle \langle n,a,b\rangle }$

Затем, до тех пор, пока это невозможно, три элемента выталкиваются и заменяются в соответствии с правилами ^{[примечание 2]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r1)}}&0&,&a&,&b&\rightarrow &(b+1)\\{\text{(r2)}}&1&,&a&,&0&\rightarrow &a\\{\text{(r3)}}&2&,&a&,&0&\rightarrow &0\\{\text{(r4)}}&(n+3)&,&a&,&0&\rightarrow &1\\{\text{(r5)}}&(n+1)&,&a&,&(b+1)&\rightarrow &n&,&a&,&(n+1)&,&a&,&b\end{array}}}$

Схематически, начиная с :${\displaystyle \langle n,a,b\rangle }$

WHILE длина стека <> 1{ ВЫТЯНУТЬ 3 элемента; ВЫТЯНУТЬ 1 или 5 элементов согласно правилам r1, r2, r3, r4, r5;}

Пример

Вычислить . ^[16]${\displaystyle H_{2}(2,2)\rightarrow _{*}4}$

Последовательность редукции: ^{[nb 2] [17]}

${\displaystyle {\underline {H(S(S(0)),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),S(0))}})}$

${\displaystyle \rightarrow _{r5}H(S(0),S(S(0)),H(S(0),S(S(0)),{\underline {H(S(S(0)),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r3}H(S(0),S(S(0)),{\underline {H(S(0),S(S(0)),0)}})}$

${\displaystyle \rightarrow _{r2}{\underline {H(S(0),S(S(0)),S(S(0)))}}}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),{\underline {H(S(0),S(S(0)),S(0))}})}$

${\displaystyle \rightarrow _{r5}H(0,S(S(0)),H(0,S(S(0)),{\underline {H(S(0),S(S(0)),0)}}))}$

${\displaystyle \rightarrow _{r2}H(0,S(S(0)),{\underline {H(0,S(S(0)),S(S(0)))}})}$

${\displaystyle \rightarrow _{r1}{\underline {H(0,S(S(0)),S(S(S(0))))}}}$

${\displaystyle \rightarrow _{r1}S(S(S(S(0))))}$

При реализации с использованием стека, на входе${\displaystyle \langle 2,2,2\rangle }$

конфигурации стека	представляют уравнения
${\displaystyle {\underline {2,2,2}}}$	${\displaystyle H_{2}(2,2)}$
${\displaystyle \rightarrow _{r5}1,2,{\underline {2,2,1}}}$	${\displaystyle =H_{1}(2,H_{2}(2,1))}$
${\displaystyle \rightarrow _{r5}1,2,1,2,{\underline {2,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,H_{2}(2,0)))}$
${\displaystyle \rightarrow _{r3}1,2,{\underline {1,2,0}}}$	${\displaystyle =H_{1}(2,H_{1}(2,0))}$
${\displaystyle \rightarrow _{r2}{\underline {1,2,2}}}$	${\displaystyle =H_{1}(2,2)}$
${\displaystyle \rightarrow _{r5}0,2,{\underline {1,2,1}}}$	${\displaystyle =H_{0}(2,H_{1}(2,1))}$
${\displaystyle \rightarrow _{r5}0,2,0,2,{\underline {1,2,0}}}$	${\displaystyle =H_{0}(2,H_{0}(2,H_{1}(2,0)))}$
${\displaystyle \rightarrow _{r2}0,2,{\underline {0,2,2}}}$	${\displaystyle =H_{0}(2,H_{0}(2,2))}$
${\displaystyle \rightarrow _{r1}{\underline {0,2,3}}}$	${\displaystyle =H_{0}(2,3)}$
${\displaystyle \rightarrow _{r1}4}$	${\displaystyle =4}$

Определение с использованием итерации приводит к другому набору правил редукции.

${\displaystyle {\begin{array}{lll}{\text{(r6)}}&H(S(0),0,a,b)&\rightarrow &S(b)\\{\text{(r7)}}&H(S(0),S(0),a,0)&\rightarrow &a\\{\text{(r8)}}&H(S(0),S(S(0)),a,0)&\rightarrow &0\\{\text{(r9)}}&H(S(0),S(S(S(n))),a,0)&\rightarrow &S(0)\\{\text{(r10)}}&H(S(0),S(n),a,S(b))&\rightarrow &H(S(b),n,a,H(S(0),S(n),a,0))\\{\text{(r11)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(0),n,a,H(S(x),n,a,b))\end{array}}}$

Так как итерация ассоциативна , то вместо правила r11 можно определить

${\displaystyle {\begin{array}{lll}{\text{(r12)}}&H(S(S(x)),n,a,b)&\rightarrow &H(S(x),n,a,H(S(0),n,a,b))\end{array}}}$

Как и в предыдущем разделе, вычисление можно реализовать с использованием стека.${\displaystyle H_{n}(a,b)=H_{n}^{1}(a,b)}$

Первоначально стек содержит четыре элемента .${\displaystyle \langle 1,n,a,b\rangle }$

Затем, до окончания, четыре элемента выталкиваются и заменяются в соответствии с правилами ^{[примечание 2]}

${\displaystyle {\begin{array}{lllllllll}{\text{(r6)}}&1&,0&,a&,b&\rightarrow &(b+1)\\{\text{(r7)}}&1&,1&,a&,0&\rightarrow &a\\{\text{(r8)}}&1&,2&,a&,0&\rightarrow &0\\{\text{(r9)}}&1&,(n+3)&,a&,0&\rightarrow &1\\{\text{(r10)}}&1&,(n+1)&,a&,(b+1)&\rightarrow &(b+1)&,n&,a&,1&,(n+1)&,a&,0\\{\text{(r11)}}&(x+2)&,n&,a&,b&\rightarrow &1&,n&,a&,(x+1)&,n&,a&,b\end{array}}}$

Схематически, начиная с :${\displaystyle \langle 1,n,a,b\rangle }$

WHILE длина стека <> 1{ ВЫТЯНУТЬ 4 элемента; ВЫТЯНУТЬ 1 или 7 элементов согласно правилам r6, r7, r8, r9, r10, r11;}

Пример

Вычислить .${\displaystyle H_{3}(0,3)\rightarrow _{*}0}$

На входе последовательные конфигурации стека${\displaystyle \langle 1,3,0,3\rangle }$

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r11}1,2,0,{\underline {2,2,0,1}}\rightarrow _{r11}1,2,0,1,2,0,{\underline {1,2,0,1}}\\&\rightarrow _{r10}1,2,0,1,2,0,1,1,0,{\underline {1,2,0,0}}\rightarrow _{r8}1,2,0,1,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0.\end{aligned}}}$

Соответствующие равенства имеют вид

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}(0,H_{2}^{2}(0,1))=H_{2}(0,H_{2}(0,H_{2}(0,1))\\&=H_{2}(0,H_{2}(0,H_{1}(0,H_{2}(0,0))))=H_{2}(0,H_{2}(0,H_{1}(0,0)))=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0.\end{aligned}}}$

Когда правило редукции r11 заменяется правилом r12, стек преобразуется в соответствии с

${\displaystyle {\begin{array}{lllllllll}{\text{(r12)}}&(x+2)&,n&,a&,b&\rightarrow &(x+1)&,n&,a&,1&,n&,a&,b\end{array}}}$

Последовательные конфигурации стека будут тогда

${\displaystyle {\begin{aligned}&{\underline {1,3,0,3}}\rightarrow _{r10}3,2,0,{\underline {1,3,0,0}}\rightarrow _{r9}{\underline {3,2,0,1}}\rightarrow _{r12}2,2,0,{\underline {1,2,0,1}}\rightarrow _{r10}2,2,0,1,1,0,{\underline {1,2,0,0}}\\&\rightarrow _{r8}2,2,0,{\underline {1,1,0,0}}\rightarrow _{r7}{\underline {2,2,0,0}}\rightarrow _{r12}1,2,0,{\underline {1,2,0,0}}\rightarrow _{r8}{\underline {1,2,0,0}}\rightarrow _{r8}0\end{aligned}}}$

Соответствующие равенства имеют вид

${\displaystyle {\begin{aligned}&H_{3}(0,3)=H_{2}^{3}(0,H_{3}(0,0))=H_{2}^{3}(0,1)=H_{2}^{2}(0,H_{2}(0,1))=H_{2}^{2}(0,H_{1}(0,H_{2}(0,0)))\\&=H_{2}^{2}(0,H_{1}(0,0))=H_{2}^{2}(0,0)=H_{2}(0,H_{2}(0,0))=H_{2}(0,0)=0\end{aligned}}}$

Замечания

• ${\displaystyle H_{3}(0,3)=0}$это особый случай. См. ниже. ^{[nb 3] [nb 4]}
• Вычисление по правилам {r6 - r10, r11} является сильно рекурсивным. Виновником является порядок выполнения итерации: . Первый исчезает только после того, как вся последовательность развернута. Например, сходится к 65536 за 2863311767 шагов, максимальная глубина рекурсии ^[18] составляет 65534.${\displaystyle H_{n}(a,b)}$${\displaystyle H^{n}(a,b)=H(a,H^{n-1}(a,b))}$${\displaystyle H}$${\displaystyle H_{4}(2,4)}$
• Вычисление по правилам {r6 - r10, r12} более эффективно в этом отношении. Реализация итерации как имитирует повторное выполнение процедуры H. ^[19] Глубина рекурсии, (n+1), соответствует вложенности цикла. Мейер и Ритчи (1967) формализовали это соответствие. Вычисление по правилам {r6-r10, r12} также требует 2863311767 шагов для сходимости к 65536, но максимальная глубина рекурсии составляет всего 5, поскольку тетрация является 5-м оператором в последовательности гиперопераций.${\displaystyle H^{n}(a,b)}$${\displaystyle H^{n-1}(a,H(a,b))}$${\displaystyle H_{4}(2,4)}$
• Приведенные выше соображения касаются только глубины рекурсии. Любой из способов итерации приводит к одинаковому числу шагов редукции, включающих одни и те же правила (когда правила r11 и r12 считаются «одинаковыми»). Как показывает пример, редукция сходится за 9 шагов: 1 X r7, 3 X r8, 1 X r9, 2 X r10, 2 X r11/r12. Modus iterandi влияет только на порядок, в котором применяются правила редукции.${\displaystyle H_{3}(0,3)}$

Ниже приведен список первых семи (от 0-й до 6-й) гиперопераций ( 0⁰ определяется как 1).

н	Операция, H n ( а , б )	Определение	Имена	Домен
0	${\displaystyle 1+b}$или${\displaystyle a[0]b}$	${\displaystyle 1+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}$	Инкремент, преемник , зерация, гипер0	Произвольный
1	${\displaystyle a+b}$или${\displaystyle a[1]b}$	${\displaystyle a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}$	Дополнение , hyper1
2	${\displaystyle a\times {b}}$или${\displaystyle a[2]b}$	${\displaystyle \underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}}$	Умножение , hyper2
3	${\displaystyle a^{b}}$или${\displaystyle a[3]b}$	${\displaystyle \underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}}$	Возведение в степень , hyper3	b действительный, с некоторыми многозначными расширениями до комплексных чисел
4	${\displaystyle ^{b}a}$или${\displaystyle a[4]b}$	${\displaystyle \underbrace {a[3](a[3](a[3](\cdots [3](a[3](a[3]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	Тетрация , гипер4	a ≥ 0 или целое число, b целое число ≥ −1 [nb 5] (с некоторыми предлагаемыми расширениями)
5	${\displaystyle _{b}a}$или${\displaystyle a[5]b}$	${\displaystyle \underbrace {a[4](a[4](a[4](\cdots [4](a[4](a[4]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	Пентацион , гипер5	a , b целые числа ≥ −1 [nb 5]
6	${\displaystyle a[6]b}$	${\displaystyle \underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}}$	Гексация, гипер6

Н _n (0, б ) =

b + 1, когда n = 0

б , когда n = 1

0, когда n = 2

1, когда n = 3 и b = 0 ^{[nb 3] [nb 4]}

0, когда n = 3 и b > 0 ^{[nb 3] [nb 4]}

1, когда n > 3 и b четное (включая 0)

0, когда n > 3 и b нечетное

Н _n (1, б ) =

б , когда n = 2

1, когда n ≥ 3

Н _н ( а , 0) =

0, когда n = 2

1, когда n = 0 или n ≥ 3

а , когда n = 1

Н _н ( а , 1) =

2, когда n = 0

а + 1, когда n = 1

а , когда n ≥ 2

Н _н ( а , а ) =

H _n+1 ( a , 2), когда n ≥ 1

H _n ( a , −1) = ^{[nb 5]}

0, когда n = 0 или n ≥ 4

а − 1, когда n = 1

− а , когда n = 2

⁠1/а⁠ , когда n = 3

Н _n (2, 2) =

3, когда n = 0

4, когда n ≥ 1, легко демонстрируется рекурсивно.

Одно из самых ранних обсуждений гиперопераций было проведено Альбертом Беннетом в 1914 году, который разработал некоторые теории коммутативных гиперопераций (см. ниже). ^[6] Примерно 12 лет спустя Вильгельм Аккерман определил функцию , которая несколько напоминает последовательность гиперопераций. ^[20]${\displaystyle \phi (a,b,n)}$

В своей статье 1947 года ^[5] Рубен Гудстейн ввел конкретную последовательность операций, которые теперь называются гипероперациями , а также предложил греческие названия тетрация , пентация и т. д. для расширенных операций за пределами возведения в степень (потому что они соответствуют индексам 4, 5 и т. д.). Как функция с тремя аргументами, например, , последовательность гиперопераций в целом рассматривается как версия исходной функции Аккермана — рекурсивной , но не примитивно рекурсивной — модифицированной Гудстейном для включения примитивной функции-последователя вместе с другими тремя основными операциями арифметики ( сложение , умножение , возведение в степень ) и для более плавного расширения их за пределы возведения в степень.${\displaystyle G(n,a,b)=H_{n}(a,b)}$ ${\displaystyle \phi (a,b,n)}$

Первоначальная функция Аккермана с тремя аргументами использует то же правило рекурсии, что и ее версия Гудстейна (т. е. последовательность гиперопераций), но отличается от нее двумя способами. Во-первых, определяет последовательность операций, начиная со сложения ( n = 0), а не функции-последователя , затем умножение ( n = 1), возведение в степень ( n = 2) и т. д. Во-вторых, начальные условия для результата в , таким образом, отличаясь от гиперопераций за пределами возведения в степень. ^{[7] [21] [22]} Значение b + 1 в предыдущем выражении заключается в том, что = , где b подсчитывает количество операторов (возведений в степень), а не подсчитывает количество операндов ("a"), как это делает b в , и так далее для операций более высокого уровня. (Подробнее см . в статье о функции Аккермана .)${\displaystyle \phi }$${\displaystyle \phi (a,b,n)}$${\displaystyle \phi }$${\displaystyle \phi (a,b,3)=G(4,a,b+1)=a[4](b+1)}$${\displaystyle \phi (a,b,3)}$${\displaystyle a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}}$${\displaystyle a[4]b}$

Это список обозначений, которые использовались для гиперопераций.

Имя	Обозначение, эквивалентное${\displaystyle H_{n}(a,b)}$	Комментарий
Обозначение Кнута со стрелкой вверх	${\displaystyle a\uparrow ^{n-2}b}$	Используется Кнутом [23] (для n ≥ 3) и встречается в нескольких справочниках. [24] [25]
Обозначение Гильберта	${\displaystyle \phi _{n}(a,b)}$	Использовал Дэвид Гильберт . [26]
Обозначение Гудстейна	${\displaystyle G(n,a,b)}$	Использовал Рубен Гудштейн . [5]
Оригинальная функция Аккермана	${\displaystyle {\begin{matrix}\phi (a,b,n-1)\ {\text{ for }}1\leq n\leq 3\\\phi (a,b-1,n-1)\ {\text{ for }}n\geq 4\end{matrix}}}$	Использовал Вильгельм Аккерман (для n ≥ 1) [20]
Функция Аккермана–Петера	${\displaystyle A(n,b-3)+3\ {\text{for }}a=2}$	Это соответствует гипероперациям для основания 2 ( a = 2)
Обозначение Намбиара	${\displaystyle a\otimes ^{n-1}b}$	Используется Намбиаром (для n ≥ 1) [27]
Верхний индекс	${\displaystyle a{}^{(n)}b}$	Используется Робертом Мунафо. [21]
Нижняя индексная нотация (для нижних гиперопераций)	${\displaystyle a{}_{(n)}b}$	Используется для нижних гиперопераций Робертом Мунафо. [21]
Обозначение оператора (для «расширенных операций»)	${\displaystyle aO_{n-1}b}$	Используется для нижних гиперопераций Джоном Донером и Альфредом Тарским (для n ≥ 1). [28]
Обозначение квадратных скобок	${\displaystyle a[n]b}$	Используется на многих интернет-форумах; удобен для ASCII .
Обозначение цепочечных стрелок Конвея	${\displaystyle a\to b\to (n-2)}$	Используется Джоном Хортоном Конвеем (для n ≥ 3)

В 1928 году Вильгельм Аккерман определил функцию с тремя аргументами , которая постепенно превратилась в функцию с двумя аргументами, известную как функция Аккермана . Первоначальная функция Аккермана была менее похожа на современные гипероперации, поскольку его начальные условия начинались с для всех n > 2. Кроме того, он назначил сложение на n = 0, умножение на n = 1 и возведение в степень на n = 2, поэтому начальные условия производят совершенно разные операции для тетрации и далее.${\displaystyle \phi (a,b,n)}$${\displaystyle \phi }$${\displaystyle \phi (a,0,n)=a}$

н	Операция	Комментарий
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[4](b+1)}$	Смещенная форма тетрации . Итерация этой операции отличается от итерации тетрации.
4	${\displaystyle F_{4}(a,b)=(x\mapsto a[4](x+1))^{b}(a)}$	Не путать с пентацией .

Другое начальное условие, которое использовалось, — это (где база постоянна ), предложенное Рожей Петером , которое не образует иерархию гиперопераций.${\displaystyle A(0,b)=2b+1}$${\displaystyle a=2}$

В 1984 году CW Clenshaw и FWJ Olver начали обсуждение использования гиперопераций для предотвращения переполнения вычислений с плавающей точкой . ^[29] С тех пор многие другие авторы ^{[30] [31] [32]} возобновили интерес к применению гиперопераций к представлению с плавающей точкой . (Поскольку H _n ( a , b ) все определены для b = -1.) При обсуждении тетрации Кленшоу и др. предположили начальное условие , что создает еще одну иерархию гиперопераций. Как и в предыдущем варианте, четвертая операция очень похожа на тетрацию , но смещена на единицу.${\displaystyle F_{n}(a,0)=0}$

н	Операция	Комментарий
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[4](b-1)}$	Смещенная форма тетрации . Итерация этой операции сильно отличается от итерации тетрации.
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto a[4](x-1)\right)^{b}(0)=0{\text{ if }}a>0}$	Не путать с пентацией .

Альтернатива для этих гиперопераций получается путем оценки слева направо. ^[9] Поскольку

${\displaystyle {\begin{aligned}a+b&=(a+(b-1))+1\\a\cdot b&=(a\cdot (b-1))+a\\a^{b}&=\left(a^{(b-1)}\right)\cdot a\end{aligned}}}$

определить (с ° или нижним индексом)

${\displaystyle a_{(n+1)}b=\left(a_{(n+1)}(b-1)\right)_{(n)}a}$

с

${\displaystyle {\begin{aligned}a_{(1)}b&=a+b\\a_{(2)}0&=0\\a_{(n)}1&=a&{\text{for }}n>2\\\end{aligned}}}$

Это было распространено на порядковые числа Донером и Тарским ^[33] :

${\displaystyle {\begin{aligned}\alpha O_{0}\beta &=\alpha +\beta \\\alpha O_{\gamma }\beta &=\sup \limits _{\eta <\beta ,\xi <\gamma }(\alpha O_{\gamma }\eta )O_{\xi }\alpha \end{aligned}}}$

Из Определения 1(i), Следствия 2(ii) и Теоремы 9 следует, что при a ≥ 2 и b ≥ 1 ^{[ оригинальное исследование? ]}

${\displaystyle aO_{n}b=a_{(n+1)}b}$

Но это терпит своего рода крах, не способствуя формированию «силовой башни», традиционно ожидаемой от гипероператоров: ^{[34] [примечание 6]}

${\displaystyle \alpha _{(4)}(1+\beta )=\alpha ^{\left(\alpha ^{\beta }\right)}.}$

Если α ≥ 2 и γ ≥ 2, ^{[28] [Следствие 33(i)] [nb 6]}

${\displaystyle \alpha _{(1+2\gamma +1)}\beta \leq \alpha _{(1+2\gamma )}(1+3\alpha \beta ).}$

н	Операция	Комментарий
0	${\displaystyle F_{0}(a,b)=a+1}$	Инкремент, преемник, нуль
1	${\displaystyle F_{1}(a,b)=a+b}$
2	${\displaystyle F_{2}(a,b)=a\cdot b}$
3	${\displaystyle F_{3}(a,b)=a^{b}}$
4	${\displaystyle F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}}$	Не путать с тетрацией .
5	${\displaystyle F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)}$	Не путать с пентацией . Аналогично тетрации .

Коммутативные гипероперации рассматривались Альбертом Беннетом еще в 1914 году, ^[6] , что, возможно, является самым ранним замечанием о любой последовательности гиперопераций. Коммутативные гипероперации определяются правилом рекурсии

${\displaystyle F_{n+1}(a,b)=\exp(F_{n}(\ln(a),\ln(b)))}$

которая симметрична относительно a и b , что означает, что все гипероперации коммутативны. Эта последовательность не содержит возведения в степень , и поэтому не образует иерархию гиперопераций.

н	Операция	Комментарий
0	${\displaystyle F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)}$	Максимум плавности
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^{\ln(b)}=e^{\ln(a)\ln(b)}}$	В конечном поле это операция обмена ключами Диффи–Хеллмана .
4	${\displaystyle F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}}$	Не путать с тетрацией .

RL Goodstein ^[5] использовал последовательность гипероператоров для создания систем счисления неотрицательных целых чисел. Так называемое полное наследственное представление целого числа n на уровне k и основании b можно выразить следующим образом, используя только первые k гипероператоров и используя в качестве цифр только 0, 1, ..., b − 1 вместе с самим основанием b :

• Для 0 ≤ n ≤ b − 1 n представляется просто соответствующей цифрой.
• При n > b − 1 представление n находится рекурсивно, сначала представляя n в виде

б [ к ] х _к [ к − 1] х _{к − 1} [ к - 2] ... [2] х ₂ [1] х ₁

где x _k , ..., x ₁ — наибольшие целые числа, удовлетворяющие (в свою очередь)

б [ к ] х _к ≤ n

б [ к ] х _к [ к − 1] х _{к − 1} ≤ n

...

б [ к ] х _к [ к − 1] х _{к − 1} [ к - 2] ... [2] х ₂ [1] х ₁ ≤ n

Любое x _i, превышающее b − 1, затем переписывается таким же образом и так далее, повторяя эту процедуру до тех пор, пока результирующая форма не будет содержать только цифры 0, 1, ..., b − 1 вместе с основанием b .

Ненужных скобок можно избежать, предоставив операторам более высокого уровня более высокий приоритет в порядке оценки; таким образом,

представления уровня 1 имеют вид b [1] X, где X также имеет этот вид;

представления уровня 2 имеют вид b [2] X [1] Y, где X , Y также имеют этот вид;

представления уровня 3 имеют вид b [3] X [2] Y [1] Z, причем X , Y , Z также имеют этот вид;

представления уровня 4 имеют вид b [4] X [3] Y [2] Z [1] W, причем X , Y , Z , W также имеют этот вид;

и так далее.

В этом типе наследственного представления с основанием b в выражениях появляется само основание, а также «цифры» из набора {0, 1, ..., b − 1}. Это сопоставимо с обычным представлением с основанием 2, когда последнее записано в терминах основания b ; например, в обычной нотации с основанием 2 6 = (110) ₂ = 2 [3] 2 [2] 1 [1] 2 [3] 1 [2] 1 [1] 2 [3] 0 [2] 0, тогда как наследственное представление с основанием 2 уровня 3 равно 6 = 2 [3] (2 [3] 1 [2] 1 [1] 0) [2] 1 [1] (2 [3] 1 [2] 1 [1] 0). Наследственные представления можно сократить, опустив любые примеры [1] 0, [2] 1, [3] 1, [4] 1 и т. д.; например, приведенное выше представление числа 6 на уровне 3 с основанием 2 сокращается до 2 [3] 2 [1] 2.

Примеры: Уникальные представления числа 266 в двоичной системе счисления на уровнях 1, 2, 3, 4 и 5 следующие:

Уровень 1: 266 = 2 [1] 2 [1] 2 [1] ... [1] 2 (с 133 двоек)

Уровень 2: 266 = 2 [2] (2 [2] (2 [2] (2 [2] 2 [2] 2 [2] 2 [2] 2 [1] 1)) [1] 1)

Уровень 3: 266 = 2 [3] 2 [3] (2 [1] 1) [1] 2 [3] (2 [1] 1) [1] 2

Уровень 4: 266 = 2 [4] (2 [1] 1) [3] 2 [1] 2 [4] 2 [2] 2 [1] 2

Уровень 5: 266 = 2 [5] 2 [4] 2 [1] 2 [5] 2 [2] 2 [1] 2

Wikifunctions имеет функцию гипероперации .

• Большие числа