Стрелочные обозначения Кнута

В математике стрелочная нота́ция Кну́та — это метод для записи больших чисел. Её идея основывается на том, что умножение — множественное сложение, возведение в степень — множественное умножение. Была предложена Дональдом Кнутом в 1976 году^[1]. Тесно связана с функцией Аккермана и последовательностью гипероператоров.

Тетрация, записанная с помощью стрелочной нотации Кнута:

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

Пентация в обозначениях Кнута:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\end{matrix}}}$.

В указанных обозначениях присутствует b операндов, каждый из которых равен a, соответственно операции повторяются ${\displaystyle b-1}$ раз.

Введение

Обычные арифметические операции — сложение, умножение и возведение в степень — естественным образом могут быть расширены в последовательность гипероператоров следующим образом:

Умножение натуральных чисел может быть определено через повторно производимую операцию сложения («сложить b копий числа a»):

${\displaystyle {\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b\end{matrix}}}$,

например,

${\displaystyle {\begin{matrix}\pi \times 3=\underbrace {\pi +\pi +\pi } _{3}=9.4247779608...\end{matrix}}}$,

Возведение числа а в степень b может быть определено как повторно производимая операция умножения («перемножить b копий числа a»), и в обозначениях Кнута эта запись выглядит как одиночная стрелочка, указывающая вверх:

${\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b\end{matrix}}}$,

Например,

${\displaystyle {\begin{matrix}\pi \uparrow 3=\pi ^{3}=\underbrace {\pi \times \pi \times \pi } _{3}=31.0062766803...\end{matrix}}}$,

Такая одиночная стрелка вверх использовалась в качестве значка степени в языке программирования Алгол.

Продолжая далее последовательность операций за пределы возведения в степень, Дональд Кнут ввёл понятие оператора «двойная стрелочка» для записи тетрации (многократного возведения в степень):

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

Например,

${\displaystyle \pi \uparrow \uparrow 3={\ ^{3}\pi }=\underbrace {\pi ^{\pi ^{\pi }}} _{3}=\underbrace {\pi \uparrow (\pi \uparrow \pi )} _{3}=\pi ^{36}=1\,340\,164\,183\,006\,357\,435.2974491296...}$.

Здесь и далее вычисление выражения всегда идёт справа налево. Также и стрелочные операторы Кнута (как и операция возведение в степень) по определению обладают правой ассоциативностью (очерёдностью справа налево). Согласно данному определению,

${\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^{7\,625\,597\,484\,987}\approx 1.25801429\times 10^{3\,638\,334\,640\,024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7\,625\,597\,484\,987}}\approx 10^{6.0022536\times 10^{3\,638\,334\,640\,023}}}$

${\displaystyle 3\uparrow \uparrow 6=3^{3^{3^{3^{3^{3}}}}}=3^{3^{3^{3^{27}}}}=3^{3^{3^{7\,625\,597\,484\,987}}}\approx 10^{10^{6.0022536\times 10^{3\,638\,334\,640\,023}}}}$

...

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

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\end{matrix}}}$,

затем оператора «четверная стрелочка»:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b\end{matrix}}}$

и т. д. Общее правило оператор «n-я стрелочка», в соответствии с правой ассоциативностью, продолжается вправо в последовательную серию операторов «n-1 стрелочка». Символически это можно записать следующим образом:

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\ \dots \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\!-\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b\end{matrix}}}$.

Например:

${\displaystyle 4\uparrow \uparrow \uparrow 2=4\uparrow \uparrow 4=4^{4^{4^{4}}}=4^{4^{256}}\approx 10^{8.0723047\times 10^{153}}}$,

${\displaystyle {\begin{matrix}4\uparrow \uparrow \uparrow 3=4\uparrow \uparrow 4\uparrow \uparrow 4=4\uparrow \uparrow (4\uparrow 4\uparrow 4\uparrow 4)=&\underbrace {4_{}\uparrow 4\uparrow \dots \uparrow 4} \\&4\uparrow 4\uparrow 4\uparrow 4\end{matrix}}{\begin{matrix}=&\underbrace {4_{}\uparrow 4\uparrow \dots \uparrow 4} \\&10^{8.0723047\times 10^{153}}\end{matrix}}}$.

Форма обозначения ${\displaystyle a\uparrow ^{n}b}$ обычно используется для записи ${\displaystyle a\uparrow \uparrow \dots \uparrow b}$ с n стрелочками.

Система обозначений

В таких выражениях как ${\displaystyle a^{b}}$, обычно для обозначения возведения в степень пишут показатель степени ${\displaystyle b}$ как верхний индекс основания ${\displaystyle a}$. Но многие другие среды — такие как языки программирования и e-mail — не поддерживают подобную двумерную конфигурацию. Поэтому пользователи должны использовать линейную форму записи ${\displaystyle a\uparrow b}$ для таких сред; стрелочка наверх предлагает возвести в степень степени. Если среди доступных символов нет стрелочки вверх, тогда вместо неё используется циркумфлекс «^».Верхний индекс записи ${\displaystyle a^{b}}$ сам по себе не приспособлен к обобщению, что объясняет, почему Дональд Кнут вместо такой формы записи выбрал линейную форму записи ${\displaystyle a\uparrow b}$.

Обозначение «↑»

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

${\displaystyle a\uparrow \uparrow 4=a\uparrow a\uparrow a\uparrow a=a^{a^{a^{a}}}}$.

Если 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}}}}$.

И снова, если 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}$ как итерацию возведения в степень для любого a, n и 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&=&{\mbox{hyper}}(a,n+2,b)&=&a\to b\to n\\{\mbox{(Knuth)}}&&&&{\mbox{(Conway)}}\end{matrix}}}$

Общепринято использовать стрелочную форму записи Кнута для маленького размера чисел, а цепные стрелочки или гипероператоры для большого размера.

Определение

Обозначение стрелочка вверх формально определяется так

${\displaystyle a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{если }}n=1;\\1,&{\mbox{если }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{в ином случае}}\end{matrix}}\right.}$

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

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

${\displaystyle a\uparrow b\uparrow c=a\uparrow (b\uparrow c)}$, но не ${\displaystyle (a\uparrow b)\uparrow c}$;

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}}$ равно ${\displaystyle 3^{(3^{3})}=3^{27}=7625597484987}$, но не ${\displaystyle \left(3^{3}\right)^{3}=27^{3}=19683.}$

Есть хорошая причина для подобного выбора направления вычисления справа налево. Если бы мы использовали способ вычисления слева направо, тогда ${\displaystyle a\uparrow \uparrow b}$ было бы равно ${\displaystyle a\uparrow (a\uparrow (b-1))}$, и тогда ${\displaystyle \uparrow \uparrow }$ в действительности не являлся бы новым оператором.

Правая ассоциативность также естественна по следующей причине. Мы можем переписать повторяемые стрелочные выражения ${\displaystyle a\uparrow ^{n}\cdots \uparrow ^{n}a,}$ которые появляются при расширении ${\displaystyle a\uparrow ^{n+1}b}$ в виде ${\displaystyle a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1}$, где всe a становятся левыми операндами стрелочных операторов. Это важно, так как стрелочные операторы не являются коммутативными.

Записывая ${\displaystyle (a\uparrow ^{m})^{b}}$ как функциональный показатель степени b функции ${\displaystyle f(x)=a\uparrow ^{m}x,}$ мы получим ${\displaystyle a\uparrow ^{n}b=(a\uparrow ^{n-1})^{b}1}$.

Определение можно продолжить ещё на один шаг, начиная с ${\displaystyle a\uparrow ^{n}b=ab}$ для n = 0, так как возведение в степень есть повторяемое умножение, начиная с 1. Экстраполировать ещё на один шаг, записывая умножение как повторяемое сложение, не совсем верно так как умножение есть повторяемое сложение, начиная с 0 вместо 1. «Экстраполируя» снова на один шаг, записывая добавочный n как повторяемое добавление 1, требует начинать с числа a. Это отличие также подчёркивается в определении гипероператора, где начальные значения для сложения и умножения задаются раздельно.

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

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

Значения ${\displaystyle 2\uparrow ^{m}n}$ = hyper(2, m + 2, n) = 2 → n → m

m\n	1	2	3	4	5	6	Формула
1	2	4	8	16	32	64	${\displaystyle 2^{n}}$
2	2	4	16	65 536	${\displaystyle 2^{65\,536}\approx 2{,}00\times 10^{19\,729}}$	${\displaystyle 2^{2^{65\,536}}\approx 10^{6{,}03\times 10^{19\,728}}}$	${\displaystyle 2\uparrow \uparrow n}$
3	2	4	65 536	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65\,536}}$			${\displaystyle 2\uparrow \uparrow \uparrow n}$
4	2	4	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65\,536}}$				${\displaystyle 2\uparrow \uparrow \uparrow \uparrow n}$

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

Расчёт ${\displaystyle 3\uparrow ^{m}n}$

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

Значения ${\displaystyle 3\uparrow ^{m}n}$ = hyper(3, m + 2, n) = 3 → n → m

m\n	1	2	3	4	5	Формула
1	3	9	27	81	243	${\displaystyle 3^{n}}$
2	3	27	7 625 597 484 987	${\displaystyle 3^{7\,625\,597\,484\,987}}$	${\displaystyle 3^{3^{7\,625\,597\,484\,987}}}$	${\displaystyle 3\uparrow \uparrow n}$
3	3	7 625 597 484 987	${\displaystyle \underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{7\,625\,597\,484\,987}}$			${\displaystyle 3\uparrow \uparrow \uparrow n}$
4	3	${\displaystyle \underbrace {3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}} _{7\,625\,597\,484\,987}}$				${\displaystyle 3\uparrow \uparrow \uparrow \uparrow n}$

Расчёт ${\displaystyle 10\uparrow ^{m}n}$

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

Значения ${\displaystyle 10\uparrow ^{m}n}$ = hyper(10, m + 2, n) = 10 → n → m

m\n	1	2	3	4	5	Формула
1	10	100	1000	10 000	100 000	${\displaystyle 10^{n}}$
2	10	10 000 000 000	${\displaystyle 10^{10\,000\,000\,000}}$	${\displaystyle 10^{10^{10\,000\,000\,000}}}$	${\displaystyle 10^{10^{10^{10\,000\,000\,000}}}}$	${\displaystyle 10\uparrow \uparrow n}$
3	10	${\displaystyle \underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{10}}$	${\displaystyle \underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{\underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{10}}}$	${\displaystyle \underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{\underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{\underbrace {10^{10^{\cdot ^{\cdot ^{\cdot ^{10}}}}}} _{10}}}}$		${\displaystyle 10\uparrow \uparrow \uparrow n}$
4	10	${\displaystyle \underbrace {^{^{^{^{^{10}.}.}.}10}10} _{10}}$	${\displaystyle \underbrace {^{^{^{^{^{10}.}.}.}10}10} _{\underbrace {^{^{^{^{^{10}.}.}.}10}10} _{10}}}$			${\displaystyle 10\uparrow \uparrow \uparrow \uparrow n}$

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