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

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

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

После этого последовательность переходит к дальнейшим двоичным операциям, выходящим за рамки возведения в степень, используя правую ассоциативность . Для операций, выходящих за рамки возведения в степень, n- й член этой последовательности назван Рубеном Гудштейном в честь греческого префикса n с суффиксом -ация (например, тетрация ( 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{ copies of }}a},\quad n\geq 2}$

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

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

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

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

Определение

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

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

${\displaystyle 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 это определение воспроизводит основные арифметические операции преемника (который является унарной операцией), сложения , умножения и возведения в степень соответственно, как

${\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 {tetration} (a,3)=a^{a^{a}},}$

${\displaystyle {\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 таким образом, чтобы оно согласовывалось со всей последовательностью гиперопераций, за исключением задержки в индексации:

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

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

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

проиллюстрирована взаимосвязь между основными арифметическими операциями, что позволяет естественным образом определить более высокие операции, как указано выше. Параметры иерархии гиперопераций иногда называют аналогичным термином возведения в степень; ^[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) .

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

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

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

Затем, неоднократно, пока это становится невозможным, три элемента извлекаются и заменяются в соответствии с правилами ^{[nb 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 }$

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

Пример

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

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

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

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

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

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

Затем, до завершения, четыре элемента извлекаются и заменяются в соответствии с правилами ^{[nb 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 }$

ПОКА stackLength <> 1{ POP 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}$это особый случай. См. ниже. ^{[количество 3] [номер 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} в этом отношении более эффективно. Реализация итерации as имитирует повторное выполнение процедуры 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).

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

ЧАС ( ₀ , б ) =

б + 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 нечетно

ЧАС ₍ 1, б ) =

б , когда n = 2

1, когда n ≥ 3

ЧАС _п ( а , 0) =

0, когда n = 2

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

а , когда n = 1

ЧАС _п ( а , 1) =

а, когда n ≥ 2

ЧАС _п ( а , а ) знак равно

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

ЧАС _п ( а , −1) = ^{[nb 5]}

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

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

− а , когда n = 2

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

Ч _н (2, 2) =

3, когда n = 0

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

История

Одним из первых обсуждений гиперопераций было обсуждение Альберта Беннета ^[6] в 1914 году, который разработал часть теории коммутативных гиперопераций (см. ниже). Примерно 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 in и т. д . для операций более высокого уровня. ( Подробнее см. в статье о функции Аккермана .) ${\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}$

Обозначения

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

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

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

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

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

В 1984 году К.В. Кленшоу и Ф.В.Дж. Олвер начали обсуждение использования гиперопераций для предотвращения компьютерных переполнений с плавающей запятой . ^[29] С тех пор многие другие авторы ^{[30] [31] [32]} возобновили интерес к применению гиперопераций к представлению с плавающей запятой . (Поскольку все H _n ( a , b ) определены для b = -1.) Обсуждая тетратирование , Clenshaw et al. принял начальное условие , что создает еще одну иерархию гиперопераций. Как и в предыдущем варианте, четвертая операция очень похожа на тетрацию , но смещена на единицу. ${\displaystyle F_{n}(a,0)=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] [nb 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 ).}$

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

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

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

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

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

Р. Л. Гудштейн ^[5] использовал последовательность гипероператоров для создания систем счисления неотрицательных целых чисел. Так называемое полное наследственное представление целого числа 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

Смотрите также

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

Примечания

1. Последовательности, подобные последовательности гиперопераций, исторически назывались под многими именами, в том числе: функция Аккермана ^[1] (3-аргумент), иерархия Аккермана , ^[2] иерархия Гжегорчика [ ^{3] [4]} (что более в общем), версия Гудштейна функции Аккермана , ^[5] операция n-го класса , ^[6] z-кратное итерированное возведение в степень x с y , ^[7] стрелочные операции , ^[8] рейхеналгебра ^[9] и гипер-n . ^{[1] [9] [10] [11] [12]}
2. Это реализует самую левую внутреннюю (одношаговую) стратегию .
3. Для получения более подробной информации см. Степени нуля .
4. Для получения более подробной информации см. Ноль в нулевой степени .
5. Пусть x = a [ n ](−1). По рекурсивной формуле a [ n ]0 = a [ n − 1]( a [ n ](−1)) ⇒ 1 = a [ n − 1] x . Одним из решений является x = 0, поскольку a [ n − 1]0 = 1 по определению, когда n ≥ 4. Это решение единственное, поскольку a [ n − 1] b > 1 для всех a > 1, b > 0 (доказательство рекурсия).
6. Порядковое сложение не коммутативно; см. порядковую арифметику для получения дополнительной информации

Рекомендации

1. Гейслер 2003.
2. Фридман 2001.
3. Кампаньола, Мур и Феликс Коста 2002.
4. Вирц 1999.
5. Гудстейн 1947.
6. Беннетт 1915.
7. Блэк 2009.
8. Литтлвуд 1948.
9. Мюллер 1993.
10. Мунафо 1999а.
11. Роббинс 2005.
12. Галидакис 2003.
13. Рубцов и Ромерио 2005.
14. Таунсенд 2016.
15. Ромерио 2008.
16. Безем, Клоп и Де Вриер 2003.
17. На каждом этапе подчеркнутый редекс перезаписывается.
18. Максимальная глубина рекурсии относится к количеству уровней активации процедуры, которые существуют во время самого глубокого вызова процедуры. Корнелиус и Кирби (1975)
19. LOOP n РАЗ DO H.
20. Аккерманн 1928.
21. Munafo 1999b.
22. Коулз и Бейли 1988.
23. Кнут 1976.
24. Цвиллингер 2002.
25. Вайсштейн 2003.
26. Гильберт 1926.
27. Намбиар 1995.
28. Донер и Тарский 1969.
29. Кленшоу и Олвер 1984.
30. Холмс 1997.
31. Циммерманн 1997.
32. Пинкевич, Холмс и Джамиль 2000.
33. Донер и Тарский 1969, Определение 1.
34. Донер и Тарский, 1969, Теорема 3(iii).

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

• Акерманн, Вильгельм (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Математические Аннален . 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). «Über das Unendliche». Математические Аннален . 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. PMID  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-е издание . ЦРК Пресс. стр. 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.