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

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

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

$\begin{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b& & b\end{array}$.

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

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

В указанных обозначениях присутствует Шаблон:Mvar операндов, каждый из которых равен Шаблон:Mvar, соответственно операции повторяются $b-1$ раз.

Введение

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

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

$\begin{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\end{array}$,

например,

$\begin{array}{ccccc}4\times 3& =& \underbrace{4+4+4}& =& 12\\ & & 3\end{array}$.

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

$\begin{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\end{array}$

Например,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\end{array}$

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

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

$\begin{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b& & b\end{array}$.

Например,

$\begin{array}{ccccccc}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{array}$.

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

$3\uparrow \uparrow 2=3^3=27$,

$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987$,

$3\uparrow \uparrow 4=3^{3^{3^3}}=3^{7625597484987}\approx 1,3\times 10^{3638334640024}$,

$3\uparrow \uparrow 5=3^{3^{3^{3^3}}}=3^{3^{7625597484987}}$,

и так далее.

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

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

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

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

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

$\begin{array}{c}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\\ n\underbrace{n_{}-1n-1n-1}\\ b\end{array}$.

Например:

$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987$,

$\begin{array}{cc}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\end{array}\begin{array}{cc}=& \underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}\\ & 7625597484987\end{array}$.

Форма обозначения $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=\underset{b}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$.

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

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

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

$a\uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}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=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}a$.

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

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b}{\underbrace{\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\cdots \}a}}$.

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

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

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

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

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

$a\uparrow \uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}\}b$.

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

$\underset{\underset{\underset{4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}=\underset{\underset{{}^{{}^{{}^{4}4}4}4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}$.

Обобщение

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

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

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

Определение

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

$a{\uparrow }^{n}b=\{\begin{array}{cc}{a}^b,& \text{если }n=1;\\ 1,& \text{если }b=0;\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{в ином случае}\end{array}$

для всех целых $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 }^{n}a,$ которые появляются при расширении $a{\uparrow }^{n+1}b$ в виде $a{\uparrow }^n\cdots {\uparrow }^{n}a{\uparrow }^{n}1$, где вс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=ab$ для 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{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\end{array}$			$2\uparrow \uparrow \uparrow n$
4	2	4	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\end{array}$				$2\uparrow \uparrow \uparrow \uparrow n$

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

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

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

Значения $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{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\end{array}$			$3\uparrow \uparrow \uparrow n$
4	3	$\begin{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7,625,597,484,987\end{array}$				$3\uparrow \uparrow \uparrow \uparrow n$

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

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

Значения $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	$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{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10^{10}\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10^{10^{10}}\end{array}$		$10\uparrow \uparrow \uparrow n$
4	10	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\end{array}$	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10^{10}\end{array}$			$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.

Ссылки

• Шаблон:MathWorld3