Обозначение Кнута со стрелкой вверх

Метод записи очень больших целых чисел

В математике восходящая нотация Кнута — это метод записи очень больших целых чисел , введенный Дональдом Кнутом в 1976 году . ^[1]

В своей статье 1947 года ^[2] Р. Л. Гудстейн представил конкретную последовательность операций, которые теперь называются гипероперациями . Гудстейн также предложил греческие названия тетрация , пентация и т. д. для расширенных операций за пределами возведения в степень . Последовательность начинается с унарной операции ( функция-последователь с n = 0) и продолжается бинарными операциями сложения ( n = 1), умножения ( n = 2), возведения в степень ( n = 3), тетрации ( n = 4), пентации ( n = 5) и т. д. Для представления гиперопераций использовались различные обозначения . Одно из таких обозначений — обозначение со стрелкой вверх Кнута. Другое — обозначение со стрелкой вверх. Например: ${\displaystyle H_{n}(a,b)}$ ${\displaystyle \uparrow }$

• одиночная стрелка представляет собой возведение в степень (повторное умножение) ${\displaystyle \uparrow }$ $${\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times (2\times (2\times 2))=2^{4}=16}$$
• двойная стрелка представляет тетрацию (повторное возведение в степень) ${\displaystyle \uparrow \uparrow }$ $${\displaystyle 2\uparrow \uparrow 4=H_{4}(2,4)=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}$$
• тройная стрелка представляет пентацию (повторяющуюся тетрацию) ${\displaystyle \uparrow \uparrow \uparrow }$ $${\displaystyle {\begin{aligned}2\uparrow \uparrow \uparrow 4=H_{5}(2,4)=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow 4)\\&=\underbrace {2\uparrow (2\uparrow (2\uparrow \dots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\mbox{ copies of }}2\;\;\;\;\;{\mbox{65,536 2s}}\\\end{aligned}}}$$

Общее определение обозначения со стрелкой вверх выглядит следующим образом (для ): Здесь обозначает n стрелок, например Квадратные скобки — это еще одно обозначение для гиперопераций. ${\displaystyle a\geq 0,n\geq 1,b\geq 0}$ $${\displaystyle a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b.}$$ ${\displaystyle \uparrow ^{n}}$ $${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3.}$$

Введение

Гипероперации естественным образом расширяют арифметические операции сложения и умножения следующим образом. Сложение с натуральным числом определяется как итеративное приращение :

${\displaystyle {\begin{matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}$

Умножение на натуральное число определяется как повторное сложение :

${\displaystyle {\begin{matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

Например,

${\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ copies of }}4\end{matrix}}}$

Возведение в степень натурального числа определяется как итеративное умножение, которое Кнут обозначал одной стрелкой, направленной вверх: ${\displaystyle b}$

${\displaystyle {\begin{matrix}a\uparrow b=H_{3}(a,b)=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

Например,

${\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ copies of }}4\end{matrix}}}$

Тетрация определяется как итеративное возведение в степень, которое Кнут обозначил «двойной стрелкой»:

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}}$

Например,

${\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&\approx &1.34078079\times 10^{154}&\\&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}}$

Выражения вычисляются справа налево, поскольку операторы определены как правоассоциативные .

Согласно этому определению,

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580143\times 10^{3638334640024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}}$

и т. д.

Это уже приводит к некоторым довольно большим числам, но последовательность гипероператоров на этом не заканчивается.

Пентация , определяемая как итерированная тетрация, представлена ​​«тройной стрелкой»:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

Гексация , определяемая как итерированная пентация, представлена ​​«четверной стрелкой»:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

и так далее. Общее правило заключается в том, что оператор -стрелка расширяется в правоассоциативный ряд операторов ( )-стрелка. Символически, ${\displaystyle n}$ ${\displaystyle n-1}$

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ (\dots \ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}$

Примеры:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

${\displaystyle {\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ copies of }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}{\begin{matrix}=&\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\&{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}}$

Обозначение

В выражениях, таких как , запись возведения в степень обычно заключается в записи показателя степени в виде надстрочного индекса к основанию числа . Но многие среды — такие как языки программирования и электронная почта с обычным текстом — не поддерживают набор надстрочных индексов . Люди приняли линейную запись для таких сред; стрелка вверх означает «возведение в степень». Если набор символов не содержит стрелку вверх, вместо нее используется каретка (^). ${\displaystyle a^{b}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\uparrow b}$

Надстрочная нотация плохо поддается обобщению, что объясняет, почему Кнут решил работать с внутристрочной нотацией . ${\displaystyle a^{b}}$ ${\displaystyle a\uparrow b}$

${\displaystyle a\uparrow ^{n}b}$является более короткой альтернативной записью для n стрелок вверх. Таким образом . ${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$

Запись восходящей стрелочной нотации в терминах степеней

Попытка записать с использованием привычной надстрочной записи дает степенную башню . ${\displaystyle a\uparrow \uparrow b}$

Например: ${\displaystyle a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^{a}}}}$

Если является переменной величиной (или слишком большой), то башня мощности может быть записана с использованием точек и примечания, указывающего высоту башни. ${\displaystyle b}$

${\displaystyle a\uparrow \uparrow b=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}}$

Продолжая эту запись, можно записать ее с помощью стопки таких башен мощности, каждая из которых описывает размер той, что находится выше. ${\displaystyle a\uparrow \uparrow \uparrow b}$

${\displaystyle a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow a))=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{a}}}}$

Опять же, если является переменной или слишком велик, стек может быть записан с использованием точек и примечания, указывающего его высоту. ${\displaystyle b}$

${\displaystyle a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}b}$

Кроме того, можно записать, используя несколько столбцов таких стопок энергетических башен, причем каждый столбец описывает количество энергетических башен в стопке слева от него: ${\displaystyle a\uparrow \uparrow \uparrow \uparrow b}$

${\displaystyle a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow a))=\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}a}$

И в более общем плане:

${\displaystyle a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\cdots \right\}a} _{b}}$

Это можно было бы выполнять бесконечно, чтобы представить как итеративное возведение в степень итеративного возведения в степень для любых , и (хотя это, очевидно, становится довольно громоздким). ${\displaystyle a\uparrow ^{n}b}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle b}$

Использование тетрации

Обозначение Руди Ракера для тетрации позволяет нам сделать эти диаграммы немного проще, по-прежнему используя геометрическое представление (мы могли бы назвать их башнями тетрации ). ${\displaystyle ^{b}a}$

${\displaystyle a\uparrow \uparrow b={}^{b}a}$

${\displaystyle a\uparrow \uparrow \uparrow b=\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{b}}$

${\displaystyle a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {\vdots } _{a}}}\right\}b}$

Наконец, в качестве примера, четвертое число Аккермана можно представить как: ${\displaystyle 4\uparrow ^{4}4}$

${\displaystyle \underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{4}}}=\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{^{^{^{4}4}4}4}}}$

Обобщения

Некоторые числа настолько велики, что множественные стрелки в обозначении Кнута со стрелкой вверх становятся слишком громоздкими; тогда полезен оператор n -стрелки (а также для описаний с переменным числом стрелок) или, что эквивалентно, гипероператоры . ${\displaystyle \uparrow ^{n}}$

Некоторые числа настолько велики, что даже эта нотация недостаточна. Тогда можно использовать нотацию цепочечных стрелок Конвея : цепочка из трех элементов эквивалентна другим нотациям, но цепочка из четырех или более элементов еще более мощна.

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\mbox{(Knuth)}}&&{\mbox{(hyperoperation)}}&&{\mbox{(Conway)}}\end{matrix}}}$

${\displaystyle 6\uparrow \uparrow 4}$= , Так как = = , Таким образом, результат получается следующим: ${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$ ${\displaystyle 6\uparrow \uparrow 4}$ ${\displaystyle 6^{6^{6^{6}}}}$ ${\displaystyle 6^{6^{46,656}}}$ ${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$

${\displaystyle 10\uparrow (3\times 10\uparrow (3\times 10\uparrow 15)+3)}$= или (Петильон) ${\displaystyle \underbrace {100000...000} _{\underbrace {300000...003} _{\underbrace {300000...000} _{15}}}}$ ${\displaystyle 10^{3\times 10^{3\times 10^{15}}+3}}$

Даже быстрорастущие функции можно классифицировать с помощью порядкового анализа, называемого быстрорастущей иерархией . Быстрорастущая иерархия использует последовательную итерацию функции и диагонализацию для систематического создания быстрорастущих функций из некоторой базовой функции . Для стандартной быстрорастущей иерархии с использованием , уже демонстрирует экспоненциальный рост, сравним с тетрациональным ростом и ограничен сверху функцией, включающей первые четыре гипероператора;. Тогда, сравнима с функцией Аккермана , уже находится за пределами досягаемости индексированных стрелок, но может использоваться для аппроксимации числа Грэма и сравнима с произвольной длинной цепочкой стрелок Конвея. ${\displaystyle f(x)}$ ${\displaystyle f_{0}(x)=x+1}$ ${\displaystyle f_{2}(x)}$ ${\displaystyle f_{3}(x)}$ ${\displaystyle f_{\omega }(x)}$ ${\displaystyle f_{\omega +1}(x)}$ ${\displaystyle f_{\omega ^{2}}(x)}$

Все эти функции вычислимы. Даже более быстрые вычислимые функции, такие как последовательность Гудстейна и последовательность TREE , требуют использования больших порядковых чисел и могут встречаться в определенных комбинаторных и теоретико-доказательных контекстах. Существуют функции, которые растут невычислимо быстро, такие как Busy Beaver , сама природа которых будет полностью вне досягаемости любой восходящей стрелки или даже любого порядкового анализа.

Определение

Без ссылки на гипероперацию операторы со стрелкой вверх можно формально определить следующим образом:

${\displaystyle a\uparrow ^{n}b={\begin{cases}a^{b},&{\text{if }}n=1;\\1,&{\text{if }}n>1{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

для всех целых чисел с ^{[nb 1]} . ${\displaystyle a,b,n}$ ${\displaystyle a\geq 0,n\geq 1,b\geq 0}$

Это определение использует возведение в степень как базовый случай, а тетрацию как повторное возведение в степень. Это эквивалентно последовательности гиперопераций, за исключением того, что оно опускает три более базовые операции: последовательность , сложение и умножение . ${\displaystyle (a\uparrow ^{1}b=a\uparrow b=a^{b})}$ ${\displaystyle (a\uparrow ^{2}b=a\uparrow \uparrow b)}$

В качестве альтернативы можно выбрать умножение в качестве базового случая и итерировать оттуда. Тогда возведение в степень становится повторным умножением. Формальное определение будет таким: ${\displaystyle (a\uparrow ^{0}b=a\times b)}$

${\displaystyle a\uparrow ^{n}b={\begin{cases}a\times b,&{\text{if }}n=0;\\1,&{\text{if }}n>0{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

для всех целых чисел с . ${\displaystyle a,b,n}$ ${\displaystyle a\geq 0,n\geq 0,b\geq 0}$

Однако следует отметить, что Кнут не определил «нулевую стрелку» ( ). Можно было бы расширить обозначение до отрицательных индексов (n ≥ -2) таким образом, чтобы согласовать всю последовательность гиперопераций, за исключением задержки в индексации: ${\displaystyle \uparrow ^{0}}$

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

Операция «стрелка вверх» является правоассоциативной операцией , то есть понимается как , а не . Если неоднозначность не является проблемой, скобки иногда опускаются. ${\displaystyle a\uparrow b\uparrow c}$ ${\displaystyle a\uparrow (b\uparrow c)}$ ${\displaystyle (a\uparrow b)\uparrow c}$

Таблицы значений

Вычисление 0↑н б

Вычисление результатов в ${\displaystyle 0\uparrow ^{n}b=H_{n+2}(0,b)=0[n+2]b}$

0, когда n = 0  ^{[nb 2]}

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

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

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

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

Вычисления 2↑н б

Вычисления можно переформулировать в терминах бесконечной таблицы. Мы размещаем числа в верхней строке и заполняем левый столбец значениями 2. Чтобы определить число в таблице, возьмите число сразу слева, затем найдите требуемое число в предыдущей строке, в позиции, заданной только что взятым числом. ${\displaystyle 2\uparrow ^{n}b}$ ${\displaystyle 2^{b}}$

Таблица такая же, как и у функции Аккермана , за исключением сдвига в и , а также прибавления 3 ко всем значениям. ${\displaystyle n}$ ${\displaystyle b}$

Вычисления 3↑н б

Размещаем числа в верхней строке и заполняем левый столбец значениями 3. Чтобы определить число в таблице, берем число, стоящее слева, затем ищем требуемое число в предыдущей строке, на позиции, заданной только что взятым числом. ${\displaystyle 3^{b}}$

Вычисления 4↑н б

Размещаем числа в верхней строке и заполняем левый столбец значениями 4. Чтобы определить число в таблице, берем число, расположенное непосредственно слева, затем ищем требуемое число в предыдущей строке, на позиции, заданной только что взятым числом. ${\displaystyle 4^{b}}$

Вычисления 10↑н б

Размещаем числа в верхней строке и заполняем левый столбец значениями 10. Чтобы определить число в таблице, берем число, стоящее сразу слева, затем ищем требуемое число в предыдущей строке, на позиции, заданной только что взятым числом. ${\displaystyle 10^{b}}$

Для 2 ≤ b ≤ 9 числовой порядок чисел является лексикографическим порядком с n в качестве самого значимого числа, поэтому для чисел этих 8 столбцов числовой порядок просто строка за строкой. То же самое применимо к числам в 97 столбцах с 3 ≤ b ≤ 99, и если мы начнем с n = 1 даже для 3 ≤ b ≤ 9 999 999 999. ${\displaystyle 10\uparrow ^{n}b}$

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

• Примитивная рекурсия
• Гипероперация
• Занятой бобер
• тактовая нотация Катлера
• Тетрация
• Пентацион
• Функция Аккермана
• Число Грэма
• Обозначение Штейнхауза–Мозера

Примечания

1. Более подробную информацию см. в разделе Степени нуля .
2. Имейте в виду, что Кнут не определил оператор . ${\displaystyle \uparrow ^{0}}$
3. Для получения более подробной информации см. Ноль в степени ноль .

Ссылки

1. Кнут, Дональд Э. (1976). «Математика и информатика: преодоление конечности». Science . 194 (4271): 1235–1242. Bibcode :1976Sci...194.1235K. doi :10.1126/science.194.4271.1235. PMID  17797067. S2CID  1690489.
2. RL Goodstein (декабрь 1947 г.). «Трансфинитные ординалы в рекурсивной теории чисел». Journal of Symbolic Logic . 12 (4): 123–129. doi :10.2307/2266486. JSTOR  2266486. S2CID  1318943.

Внешние ссылки

• Вайсштейн, Эрик В. «Нотация Кнута со стрелкой вверх». MathWorld .
• Роберт Мунафо, Большие числа: Высшие гипероператоры