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

Эта статья об арифметической концепции. Для концепции гипероперации теории групп см. Гиперструктуру .

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

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

$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{ copies of }}a},\quad n\geq 2$

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

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

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

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

Определение

Определение, наиболее распространенное

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

$H_{n}(a,b)=a[n]b={\begin{cases}b+1&{\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{otherwise}}\end{cases}}$

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

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

${\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}}$

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

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

${\begin{aligned}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{aligned}}$

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

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

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

${\begin{aligned}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{aligned}}$

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

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

Определение с использованием итерации

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

$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}}$

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

${\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}}$

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

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

Вычисление

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

ИВВ на основе определения подпункта 1.1

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

${\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}}$

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

Затем, неоднократно, пока это становится невозможным, три элемента выдвигаются и заменяются в соответствии с правилами.

${\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}}$

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

ПОКА  stackLength <> 1 
  { 
     POP  3 элемента; 
     НАЖМИТЕ  1 или 5 элементов по правилам r1, r2, r3, r4, r5; 
  } 
 

Пример

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

Последовательность сокращения

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

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

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

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

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

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

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

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

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

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

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

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

ИВВ на основе определения подпункта 1.2

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

${\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 можно определить

${\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}}$

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

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

Затем до момента завершения вытаскиваются и заменяются четыре элемента по правилам.

${\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}}$

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

ПОКА  stackLength <> 1 
  { 
     POP  4 элемента; 
     НАЖИМАЙТЕ  1 или 7 элементов по правилам r6, r7, r8, r9, r10, r11; 
  } 
 

Пример

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

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

${\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}}$

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

${\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, стек преобразуется в соответствии с

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

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

${\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}}$

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

${\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}}$

Примечания

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

Примеры

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

н	Операция, Ч н ( а , б )	Определение	Имена	Домен
0	$1+b$ или $a[0]b$	$1+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}$	Приращение, преемник , зерация, гипер0	Произвольный
1	$a+b$ или $a[1]b$	$a+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}$	Дополнение , гипер1
2	$a\times {b}$ или $a[2]b$	$\underbrace {a+a+a+\cdots +a+a+a} _{\displaystyle b{\mbox{ copies of }}a}$	Умножение , гипер2
3	$a^{b}$ или $a[3]b$	$\underbrace {a\times a\times a\times \;\cdots \;\times a\times a\times a} _{\displaystyle b{\mbox{ copies of }}a}$	Возведение в степень , гипер3	b действительный, с некоторыми многозначными расширениями комплексных чисел
4	$^{b}a$ или $a[4]b$	$\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 (с некоторыми предлагаемыми расширениями)
5	$_{b}a$ или $a[5]b$	$\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
6	$a[6]b$	$\underbrace {a[5](a[5](a[5](\cdots [5](a[5](a[5]a))\cdots )))} _{\displaystyle b{\mbox{ copies of }}a}$	Гексация, гипер6

Особые случаи

ЧАС _{( 0} , б ) =

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

б , когда n = 1

0, когда n = 2

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

0, когда n = 3 и b > 0

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

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

ЧАС ₍ 1, б ) =

б , когда n = 2

1, когда n ≥ 3

Hn _а ( , 0) =

0, когда n = 2

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

а , когда n = 1

Hn _а ( , 1) =

а, когда n ≥ 2

Hn _а ( , а ) =

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

Hn _а ( , −1) =

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

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

− а , когда n = 2

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

Ч _н (2, 2) =

3, когда n = 0

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

История

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

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

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

Обозначения

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

Имя	Обозначение, эквивалентное $H_{n}(a,b)$	Комментарий
Обозначение Кнута со стрелкой вверх	$a\uparrow ^{n-2}b$	Используется Кнутом (при n ≥ 3) и встречается в нескольких справочниках.
Обозначение Гильберта	$\phi _{n}(a,b)$	Используется Дэвидом Гилбертом .
Обозначение Гудштейна	$G(n,a,b)$	Используется Рубеном Гудштейном .
Оригинальная функция Аккермана	${\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)
Функция Аккермана – Петера	$A(n,b-3)+3\ {\text{for }}a=2$	Это соответствует гипероперациям для базы 2 ( a = 2)
Обозначения Намбиара	$a\otimes ^{n-1}b$	Используется Намбиаром (при n ≥ 1)
Надстрочное обозначение	$a{}^{(n)}b$	Используется Робертом Мунафо
Обозначение индекса (для нижних гиперопераций)	$a{}_{(n)}b$	Используется для нижних гиперопераций Робертом Мунафо.
Обозначение оператора (для «расширенных операций»)	$aO_{n-1}b$	Используется для нижних гиперопераций Джоном Донером и Альфредом Тарским (при n ≥ 1).
Обозначение квадратных скобок	$a[n]b$	Используется на многих интернет-форумах; удобно для ASCII .
Обозначение цепной стрелки Конвея	$a\to b\to (n-2)$	Используется Джоном Хортоном Конвеем (для n ≥ 3)

Вариант, начинающийся править

Основная статья: функция Аккермана

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

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

Другое начальное условие, которое использовалось, это $A(0,b)=2b+1$ (где база постоянна $a=2$), благодаря Rózsa Péter , который не образует иерархию гиперопераций.

Вариант начиная с 0

В 1984 году К.В. Кленшоу и Ф.В.Дж. Олвер начали обсуждение использования гиперопераций для предотвращения компьютерных переполнений с плавающей запятой . С тех пор многие другие авторы возобновился интерес к применению гиперопераций к представлению чисел с плавающей запятой . (Поскольку все H _n ( a , b ) определены для b = -1.) Обсуждая тетратирование , Clenshaw et al. принял начальное состояние $F_{n}(a,0)=0$, что создает еще одну иерархию гиперопераций. Как и в предыдущем варианте, четвертая операция очень похожа на тетрацию , но смещена на единицу.

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

Нижние гипероперации

Альтернатива этим гипероперациям получается путем вычисления слева направо. С

${\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}}$

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

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

с

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

Донер и Тарский распространили это на порядковые числа. к :

${\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

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

Но это терпит своего рода коллапс, поскольку не удается сформировать «энергетическую башню», традиционно ожидаемую от гипероператоров:

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

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

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

н	Операция	Комментарий
0	$F_{0}(a,b)=a+1$	приращение, преемник, зерация
1	$F_{1}(a,b)=a+b$
2	$F_{2}(a,b)=a\cdot b$
3	$F_{3}(a,b)=a^{b}$
4	$F_{4}(a,b)=a^{\left(a^{(b-1)}\right)}$	Не путать с тетрацией .
5	$F_{5}(a,b)=\left(x\mapsto x^{x^{(a-1)}}\right)^{b-1}(a)$	Не путать с пентацией . Похоже на тетрацию .

Коммутативные гипероперации

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

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

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

н	Операция	Комментарий
0	$F_{0}(a,b)=\ln \left(e^{a}+e^{b}\right)$	Плавный максимум
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^{\ln(b)}=e^{\ln(a)\ln(b)}$
4	$F_{4}(a,b)=e^{e^{\ln(\ln(a))\ln(\ln(b))}}$	Не путать с тетрацией .

Системы счисления, основанные на последовательности гиперопераций

Р.Л. Гудстейн использовал последовательность гипероператоров для создания систем счисления неотрицательных целых чисел. Так называемое полное наследственное представление целого числа n на уровне k и базе b можно выразить следующим образом, используя только первые k гипероператоров и используя в качестве цифр только 0, 1, ..., b − 1 вместе с базой сам б :

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

б [ k ] x _k [ k - 1] x _{k - 1} [ k - 2] ... [2] x ₂ [1] x ₁

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

б [ k ] x _k ≤ n

б [ k ] x _k [ k - 1] x _{k - 1} ≤ n

...

б [ k ] x _k [ k - 1] x _{k - 1} [ k - 2] ... [2] x ₂ [1] x ₁ ≤ 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, тогда как наследственное представление уровня 3 по основанию 2 равно 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 по основанию 2 на уровне 3 сокращается до 2 [3] 2 [1] 2.

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

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

Уровень 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

См. также

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

Библиография

• Акерманн, Вильгельм (1928). «О гильбертовой структуре действительных чисел» . Математические летописи . 99 : 118–133. дои : 10.1007/BF01459088 . S2CID   123431274 .

• Беннетт, Альберт А. (декабрь 1915 г.). «Записка об операции третьего класса». Анналы математики . Вторая серия. 17 (2): 74–75. дои : 10.2307/2007124 . JSTOR   2007124 .

• Брум, Марк; Клоп, Ян Виллем; Де Вриер, Роэль (2003). «Системы переписывания терминов первого порядка». Системы переписывания терминов от «Терезы» . Издательство Кембриджского университета. стр. 38–39. ISBN  0-521-39115-6 .

• Блэк, Пол Э. (16 марта 2009 г.). «Функция Аккермана» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий США (NIST) . Проверено 29 августа 2021 г.

• Кампаньола, Мануэль Ламейрас; Мур, Кристофер ; Феликс Коста, Хосе (декабрь 2002 г.). «Трансфинитные ординалы в рекурсивной теории чисел» . Журнал сложности . 18 (4): 977–1000. дои : 10.1006/jcom.2002.0655 .

• Кленшоу, CW; Олвер, FWJ (апрель 1984 г.). «За пределами плавающей точки» . Журнал АКМ . 31 (2): 319–328. дои : 10.1145/62.322429 . S2CID   5132225 .

• Корнелиус, Би Джей; Кирби, GH (1975). «Глубина рекурсии и функция Аккермана». БИТ Численная математика . 15 (2): 144–150. дои : 10.1007/BF01932687 . S2CID   120532578 .

• Коулз, Дж.; Бейли, Т. (30 сентября 1988 г.). «Несколько версий функции Аккермана» . Кафедра компьютерных наук, Университет Вайоминга, Ларами, Вайоминг . Проверено 29 августа 2021 г.

• Донер, Джон; Тарский, Альфред (1969). «Расширенная арифметика порядковых чисел » Фундамента математики 65 : 95–127. дои : 10.4064/fm-65-1-95-127 .

• Фридман, Харви М. (июль 2001 г.). «Длинные конечные последовательности» . Журнал комбинаторной теории . Серия А. 95 (1): 102–144. дои : 10.1006/jcta.2000.3154 .

• Галидакис, Индиана (2003). "Математика" . Архивировано из оригинала 20 апреля 2009 года . Проверено 17 апреля 2009 г.

• Гейслер, Дэниел (2003). «Что лежит за пределами возведения в степень?» . Проверено 17 апреля 2009 г.

• Гудштейн, Рубен Луи (декабрь 1947 г.). «Трансфинитные ординалы в рекурсивной теории чисел». Журнал символической логики . 12 (4): 123–129. дои : 10.2307/2266486 . JSTOR   2266486 . S2CID   1318943 .

• Гильберт, Дэвид (1926). «О Бесконечном». Математические летописи . 95 : 161-190. дои : 10.1007/BF01206605 . S2CID   121888793 .

• Холмс, WN (март 1997 г.). «Композитная арифметика: предложение нового стандарта» . Компьютер . 30 (3): 65–73. дои : 10.1109/2.573666 . Проверено 21 апреля 2009 г.

• Кнут, Дональд Эрвин (декабрь 1976 г.). «Математика и информатика: борьба с конечностью» . Наука . 194 (4271): 1235–1242. Бибкод : 1976Sci...194.1235K . дои : 10.1126/science.194.4271.1235 . ПМИД   17797067 . S2CID   1690489 . Проверено 21 апреля 2009 г.

• Литтлвуд, JE (июль 1948 г.). «Большие числа». Математический вестник . 32 (300): 163–171. дои : 10.2307/3609933 . JSTOR   3609933 . S2CID   250442130 .

• Мейер, Альберт Р .; Ричи, Деннис Макалистер (1967). Сложность циклических программ . ACM '67: Материалы 22-й национальной конференции 1967 года. дои : 10.1145/800196.806014 .

• Мюллер, Маркус (1993). «Алгебра рядов» (PDF) . Проверено 6 ноября 2021 г.

• Мунафо, Роберт (1999a). «Варианты функции Аккермана» . Большие числа в MROB . Проверено 28 августа 2021 г.

• Мунафо, Роберт (1999b). «Изобретение новых операторов и функций» . Большие числа в MROB . Проверено 28 августа 2021 г.

• Намбияр, К.К. (1995). «Функции Аккермана и трансфинитные ординалы» . Письма по прикладной математике . 8 (6): 51–53. дои : 10.1016/0893-9659(95)00084-4 .

• Перштейн, Миллард Х. (1 июня 1962 г.). «Алгоритм 93: Арифметика общего порядка» . Коммуникации АКМ . 5 (6). Нью-Йорк : Ассоциация вычислительной техники : 344. doi : 10.1145/367766.368160 . ISSN   0001-0782 .

• Пинкевич, Т.; Холмс, Н.; Джамиль, Т. (2000). «Проектирование составной арифметической единицы рациональных чисел». Материалы конференции IEEE Southeast Con 2000. «Подготовка к новому тысячелетию» (кат. № 00CH37105) . Труды IEEE. стр. 245–252. дои : 10.1109/SECON.2000.845571 . ISBN  0-7803-6312-4 . S2CID   7738926 .

• Роббинс, Эй Джей (ноябрь 2005 г.). «Дом Тетрации» . Архивировано из оригинала 13 июня 2015 года . Проверено 17 апреля 2009 г.

• Ромерио, GF (21 января 2008 г.). «Терминология гиперопераций» . Тетрационный форум . Проверено 21 апреля 2009 г.

• Рубцов, Калифорния; Ромерио, Г.Ф. (декабрь 2005 г.). «Функция Аккермана и новая арифметическая операция» . Проверено 17 апреля 2009 г.

• Таунсенд, Адам (12 мая 2016 г.). «Имена для больших чисел» . Журнал «Меловая пыль» .

• Вайсштейн, Эрик В. (2003). Краткая математическая энциклопедия CRC, 2-е издание ЦРК Пресс. стр. 100-1 127–128. ISBN  1-58488-347-2 .

• Вирц, Марк (1999). «Характеристика иерархии Гжегорчика с помощью безопасной рекурсии» (PDF) . Берн: Институт компьютерных наук и прикладной математики. CiteSeerX   10.1.1.42.3374 . S2CID   117417812 .

• Циммерманн, Р. (1997). «Компьютерная арифметика: принципы, архитектура и проектирование СБИС» (PDF) . Конспекты лекций, Лаборатория интегрированных систем, ETH Zürich. Архивировано из оригинала (PDF) 17 августа 2013 г. Проверено 17 апреля 2009 г.

• Цвиллингер, Дэниел (2002). Стандартные математические таблицы и формулы CRC, 31-е издание . ЦРК Пресс. п. 4. ISBN  1-58488-291-3 .