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

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

После этого последовательность переходит к дальнейшим двоичным операциям, выходящим за пределы возведения в степень, с использованием правоассоциативности . Для операций за пределами экспоненциации, то п - й член этой последовательности назван Реюбен Гудстейн после греческого префикса из п с суффиксом -ation (например, тетрация ( п = 4), пентация ( п = 5), hexation ( п = 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 а [п] б = а [п-1] \ влево (а [п] \ влево (б-1 \ вправо) \ вправо), \ четырехъядерных п \ geq 1}$

Это можно использовать, чтобы легко показать числа, намного большие, чем те, которые могут быть представлены в научных обозначениях , такие как число Скьюза и гуголплексоплекс (например , намного больше, чем число Скьюза и гуголплексоплекс), но есть некоторые числа, которые даже они не могут легко показать, например как число Грэма и ДЕРЕВО (3) .${\ 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)&=b+1,\\H_{1}(a,b)&=a+b,\\H_{2}(a,b)&=a\times b,\end{aligned}}}$

Операции H для n ≥ 3 могут быть записаны в нотации Кнута, направленной вверх, как

${\displaystyle {\begin{aligned}H_{3}(a,b)&=a\uparrow {b}=a^{b},\end{aligned}}}$

Так какой будет следующая операция после возведения в степень? Мы определили умножение так, что и определили возведение в степень так, что кажется логичным определить следующую операцию, тетрацию, так, чтобы с башней из трех «а». Аналогично, пентация (а, 3) будет тетрацией (а, тетрацией (а, а)) с тремя «а» в ней.${\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&=(a+(b-1))+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}}}$

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

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

Примеры [ править ]

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

п	Эксплуатация, H n ( a , b )	Определение	Имена	Домен
0	${\displaystyle 1+b}$ или же ${\displaystyle a[0]b}$	${\displaystyle 1+\underbrace {1+1+1+\cdots +1+1+1} _{\displaystyle b{\mbox{ copies of 1}}}}$	hyper0, приращение, преемник , зерация	Произвольный
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\cdot 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\cdot a\cdot a\cdot \;\cdots \;\cdot a\cdot a\cdot 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 2] (с некоторыми предлагаемыми расширениями)
5	${\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}}$	hyper5, пентация	a , b целые числа ≥ −1 [nb 2]
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}}$	hyper6, шестиугольник	a , b целые числа ≥ −1 [nb 2]

Особые случаи [ править ]

H _n (0, Ь ) =

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

b , когда 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 нечетно

H _n (1, б ) =

1, когда n ≥ 3

H _n ( a , 0) =

0, когда n = 2

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

a , когда n = 1

H _n ( a , 1) =

a, когда n ≥ 2

H _n ( a , a ) =

H _{n + 1} ( a , 2), когда n ≥ 1

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

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

a - 1, когда n = 1

- a , когда n = 2

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

H _n (2, 2) =

3, когда n = 0

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

История [ править ]

Одним из первых обсуждений гиперопераций было обсуждение Альберта Беннета ^[6] в 1914 г., который разработал некоторые из теорий коммутативных гиперопераций (см. Ниже ). Примерно 12 лет спустя Вильгельм Аккерман определил функцию ^[15], которая чем-то напоминает последовательность гиперопераций.${\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] [16] [17]} Значение b + 1 в предыдущем выражении таково, что = , где 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}}}}}}$подсчитывает количество операторов (возведения в степень), а не подсчитывает количество операндов («а»), как это делает b в , и так далее для операций более высокого уровня. (Подробности см. В статье о функциях Аккермана .)${\displaystyle a[4]b}$

Обозначения [ править ]

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

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

Вариант , начиная с с [ править ]

В 1928 году Вильгельм Аккерманн определил функцию с тремя аргументами, которая постепенно превратилась в функцию с двумя аргументами, известную как функция Аккермана . Оригинальная функция Аккермана менее похожа на современный гипероператор, потому что его начальные условия начинаются с для все п > 2. Кроме того, он назначал дополнение к п = 0, умножение на п = 1 и потенцированием к п = 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}$

Вариант начиная с 0 [ править ]

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

Нижние гипероперации [ править ]

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

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

Это было распространено на порядковые числа Доннером и Тарски, ^{[23] [Определение 1]} :

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

Но при этом происходит своего рода коллапс, неспособный сформировать «силовую башню», традиционно ожидаемую от гипероператоров: ^{[23] [Теорема 3 (iii)] [nb 5]}

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

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

${\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))}}}$	Не путать с тетрацией .

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

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

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

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

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

б [ к ] х _к ≤ п

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

Любой 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 также имеют этот вид;

и так далее.

В этом типе наследственного представления base- 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 и т.д .; например, приведенное выше представление уровня 3 по основанию 2 из 6 сокращений до 2 [3] 2 [1] 2.

Примеры: Уникальные представления числа 266 по основанию 2 на уровнях 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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]