Стрелочная нотация Кнута

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

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

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

Пентация  (англ.) в обозначениях Кнута:

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

В указанных обозначениях операции повторяются b раз, соответственно присутствует b+1 операндов.

Введение

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

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

$\begin{matrix} a\times b & = & \underbrace{a+a+\dots+a} \\ & & b\mbox{ copies of }a \end{matrix}$

Например,

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

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

$\begin{matrix} a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\ & b\mbox{ copies of }a \end{matrix}$

Например,

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

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

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

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

Например,

$\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\mbox{ copies of }4 & & 3\mbox{ copies of }4 \end{matrix}$

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

$3\uparrow\uparrow2=3^3=27$

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

$3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}$

$3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7625597484987}}$

и так далее.

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

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

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

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

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

$\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\mbox{ copies of }a \end{matrix}$

Например:

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

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

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

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

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

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

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

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

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

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

Используя такую форму записи, выражение $a \uparrow \uparrow \uparrow b$ может быть записано как набор (стек) таких степенных башен, каждая из которых показывает степень вышележащей:

$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 является переменной величиной (или очень большое), набор таких степенных башен может быть записан, используя точки и с пометкой показывающей их высоты.

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

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

$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.$

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

$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}.$

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

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

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

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

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

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

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

$\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-стрелочка $\uparrow^n$ предпочтительней (и также для описания с изменяемым числом стрелочек), или эквивалентно, гипероператорам. Но некоторые числа настолько огромны, что даже подобная запись не достаточна. Например число Грэма. Для его записи может быть использована цепочка Конвея: цепочка из трех элементов эквивалентна другой системе записи, но цепочка из четырех и более элементов является более мощной формой записи.

$\begin{matrix} a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\ \mbox{(Knuth)} & & & & \mbox{(Conway)} \end{matrix}$

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

Определение

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

$a\uparrow^n b= \left\{ \begin{matrix} a^b, & \mbox{if }n=1; \\ 1, & \mbox{if }b=0; \\ a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{otherwise} \end{matrix} \right.$

для всех целых $a, b, n,$ где $b \ge 0, n \ge 1$.

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

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

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

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

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

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

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

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

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

Значения $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	$2^n$
2	2	4	16	65536	$2^{65536}\approx 2.0 \times 10^{19,729}$	$2^{2^{65536}}\approx 10^{6.0 \times 10^{19,728}}$	$2\uparrow\uparrow n$
3	2	4	65536	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\ 65536\mbox{ copies of }2 \end{matrix}$			$2\uparrow\uparrow\uparrow n$
4	2	4	$\begin{matrix} \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\ 65536\mbox{ copies of }2 \end{matrix}$				$2\uparrow\uparrow\uparrow\uparrow n$

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

Расчет $3\uparrow^m n$

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

Values of $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	$3^n$
2	3	27	7,625,597,484,987	$3^{7,625,597,484,987}$		$3\uparrow\uparrow n$
3	3	7,625,597,484,987	$\begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987\mbox{ copies of }3 \end{matrix}$			$3\uparrow\uparrow\uparrow n$
4	3	$\begin{matrix} \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\ 7,625,597,484,987\mbox{ copies of }3 \end{matrix}$				$3\uparrow\uparrow\uparrow\uparrow n$

Расчет $10\uparrow^m n$

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

Values of $10\uparrow^m n$ = hyper(10, m + 2, n) = 10 → n → m

m\n	1	2	3	4	5	Формула
1	10	100	1,000	10,000	100,000	$10^n$
2	10	10,000,000,000	$10^{10,000,000,000}$	$10^{10^{10,000,000,000}}$	$10^{10^{10^{10,000,000,000}}}$	$10\uparrow\uparrow n$
3	10	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10}\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\ 10^{10^{10}}\mbox{ copies of }10 \end{matrix}$		$10\uparrow\uparrow\uparrow n$
4	10	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10\mbox{ copies of }10 \end{matrix}$	$\begin{matrix} \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\ 10^{10}\mbox{ copies of }10 \end{matrix}$			$10\uparrow\uparrow\uparrow\uparrow n$

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

См. также

• Тетрация
• Гипероператор
• Обозначения Конвея
• Обозначения Штейнгауза — Мозера

Примечания

1. ↑ Knuth, Donald E. (1976). «Mathematics and Computer Science: Coping with Finiteness». Science 194: 1235–1242. DOI:10.1126/science.194.4271.1235.

Ссылки

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