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

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

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

[math]\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} }[/math]

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

[math]\displaystyle{ \begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\ & b \end{matrix} }[/math]

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

Введение

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

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

[math]\displaystyle{ \begin{matrix} a\times b & = & \underbrace{a+a+\dots+a} \\ & & b \end{matrix} }[/math]

Например,

[math]\displaystyle{ \begin{matrix} 4\times 3 & = & \underbrace{4+4+4} & = & 12\\ & & 3 \end{matrix} }[/math]

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

[math]\displaystyle{ \begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b \end{matrix} }[/math]

Например,

[math]\displaystyle{ \begin{matrix} 4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\ & 3 \end{matrix} }[/math]

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

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

[math]\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} }[/math]

Например,

[math]\displaystyle{ \begin{matrix} 4\uparrow\uparrow 3 & = {\ ^{3}4} = & \underbrace{4^{4^4}} & = & \underbrace{4\uparrow (4\uparrow 4)} & = & 4^{256} \approx 1{,}3\times 10^{154} \\ & & 3 & & 3 \end{matrix} }[/math]

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

[math]\displaystyle{ 3\uparrow\uparrow2=3^3=27 }[/math]

[math]\displaystyle{ 3\uparrow\uparrow3=3^{3^3}=3^{27}=7\,625\,597\,484\,987 }[/math]

[math]\displaystyle{ 3\uparrow\uparrow4=3^{3^{3^3}}=3^{7\,625\,597\,484\,987}\approx 1{,}3\times 10^{3\,638\,334\,640\,024} }[/math]

[math]\displaystyle{ 3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7\,625\,597\,484\,987}} }[/math]

и так далее.

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

[math]\displaystyle{ \begin{matrix} a\uparrow\uparrow\uparrow b= & \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\ & b \end{matrix} }[/math]

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

[math]\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} }[/math]

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

[math]\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} }[/math]

Например:

[math]\displaystyle{ 3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7\,625\,597\,484\,987 }[/math]

[math]\displaystyle{ \begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 3\uparrow3\uparrow3 \end{matrix} \begin{matrix} = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 7625597484987 \end{matrix} }[/math]

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

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

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

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

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

[math]\displaystyle{ a \uparrow \uparrow 4 = a \uparrow a \uparrow a \uparrow a = a^{a^{a^a}}. }[/math]

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

[math]\displaystyle{ a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}. }[/math]

Используя такую форму записи, выражение [math]\displaystyle{ a \uparrow \uparrow \uparrow b }[/math] может быть записано как набор (стек) таких степенных башен, каждая из которых показывает степень вышележащей

[math]\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} }}. }[/math]

И снова, если b является переменной величиной (или очень большое), набор таких степенных башен может быть записан, используя точки и с пометкой, показывающей их высоты

[math]\displaystyle{ a \uparrow \uparrow \uparrow b = \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b. }[/math]

Более того, выражение [math]\displaystyle{ a \uparrow \uparrow \uparrow \uparrow b }[/math] может быть записано, используя несколько колонок подобных степенных башен, где каждая колонна показывает число степенных башен в наборе слева

[math]\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. }[/math]

В более общем случае:

[math]\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}. }[/math]

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

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

Форма записи [math]\displaystyle{ ^{b}a }[/math] в виде тетрации позволяет упростить такие схемы, при этом продолжая использовать геометрическое представление (мы можем их назвать тетрационными башнями).

[math]\displaystyle{ a \uparrow \uparrow b = { }^{b}a, }[/math]

[math]\displaystyle{ a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}, }[/math]

[math]\displaystyle{ a \uparrow \uparrow \uparrow \uparrow b = \left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b. }[/math]

Наконец, в качестве примера, четвёртое число Аккермана [math]\displaystyle{ 4 \uparrow^4 4 }[/math] может быть записано в виде:

[math]\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 }}. }[/math]

Обобщение

Некоторые числа настолько большие, что даже запись стрелочками Кнута становится слишком громоздкой; в этом случае использование оператора n-стрелочка [math]\displaystyle{ \uparrow^n }[/math] предпочтительней (и также для описания с изменяемым числом стрелочек), или эквивалентно, гипероператорам. Но некоторые числа настолько огромны, что даже подобная запись недостаточна. Например, число Грэма. Для его записи может быть использована цепочка Конвея: цепочка из трёх элементов эквивалентна другой системе записи, но цепочка из четырёх и более элементов является более мощной формой записи.

[math]\displaystyle{ \begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knut)} & & & & \mbox{(Conway)} \end{matrix} }[/math]

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

Определение

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

[math]\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. }[/math]

для всех целых [math]\displaystyle{ a, b, n, }[/math] где [math]\displaystyle{ b \ge 0, n \ge 1 }[/math].

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

[math]\displaystyle{ a \uparrow b \uparrow c = a \uparrow (b \uparrow c) }[/math], но не [math]\displaystyle{ (a \uparrow b) \uparrow c }[/math];

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

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

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

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

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

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

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

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

m\n	1	2	3	4	5	6	Формула
1	2	4	8	16	32	64	[math]\displaystyle{ 2^n }[/math]
2	2	4	16	65536	[math]\displaystyle{ 2^{65536}\approx 2{,}0 \times 10^{19,729} }[/math]	[math]\displaystyle{ 2^{2^{65536}}\approx 10^{6{,}0 \times 10^{19,728}} }[/math]	[math]\displaystyle{ 2\uparrow\uparrow n }[/math]
3	2	4	65536	[math]\displaystyle{ \begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\ 65536\end{matrix} }[/math]			[math]\displaystyle{ 2\uparrow\uparrow\uparrow n }[/math]
4	2	4	[math]\displaystyle{ \begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\ 65536 \end{matrix} }[/math]				[math]\displaystyle{ 2\uparrow\uparrow\uparrow\uparrow n }[/math]

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

Расчёт [math]\displaystyle{ 3\uparrow^m n }[/math]

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

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

m\n	1	2	3	4	5	Формула
1	3	9	27	81	243	[math]\displaystyle{ 3^n }[/math]
2	3	27	7,625,597,484,987	[math]\displaystyle{ 3^{7,625,597,484,987} }[/math]		[math]\displaystyle{ 3\uparrow\uparrow n }[/math]
3	3	7,625,597,484,987	[math]\displaystyle{ \begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987 \end{matrix} }[/math]			[math]\displaystyle{ 3\uparrow\uparrow\uparrow n }[/math]
4	3	[math]\displaystyle{ \begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987 \end{matrix} }[/math]				[math]\displaystyle{ 3\uparrow\uparrow\uparrow\uparrow n }[/math]

Расчёт [math]\displaystyle{ 10\uparrow^m n }[/math]

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

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

m\n	1	2	3	4	5	Формула
1	10	100	1000	10,000	100,000	[math]\displaystyle{ 10^n }[/math]
2	10	10,000,000,000	[math]\displaystyle{ 10^{10,000,000,000} }[/math]	[math]\displaystyle{ 10^{10^{10,000,000,000}} }[/math]	[math]\displaystyle{ 10^{10^{10^{10,000,000,000}}} }[/math]	[math]\displaystyle{ 10\uparrow\uparrow n }[/math]
3	10	[math]\displaystyle{ \begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10 \end{matrix} }[/math]	[math]\displaystyle{ \begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10} \end{matrix} }[/math]	[math]\displaystyle{ \begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10^{10}} \end{matrix} }[/math]		[math]\displaystyle{ 10\uparrow\uparrow\uparrow n }[/math]
4	10	[math]\displaystyle{ \begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10 \end{matrix} }[/math]	[math]\displaystyle{ \begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10^{10} \end{matrix} }[/math]			[math]\displaystyle{ 10\uparrow\uparrow\uparrow\uparrow n }[/math]

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

Ссылки

• Weisstein, Eric W. Knuth Up-Arrow Notation (англ.) на сайте Wolfram MathWorld.