Русская Википедия:Стрелочные обозначения Кнута
В математике стрелочная нота́ция Кну́та — это метод для записи больших чисел. Её идея основывается на том, что умножение — множественное сложение, возведение в степень — множественное умножение. Была предложена Дональдом Кнутом в 1976 году[1]. Тесно связана с функцией Аккермана и последовательностью гипероператоров.
Тетрация, записанная с помощью стрелочной нотации Кнута:
- <math>
\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>
\begin{matrix}
a\uparrow\uparrow\uparrow b= &
\underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\
& b
\end{matrix}
</math>.
В указанных обозначениях присутствует Шаблон:Mvar операндов, каждый из которых равен Шаблон:Mvar, соответственно операции повторяются <math>b-1</math> раз.
Введение
Обычные арифметические операции — сложение, умножение и возведение в степень — естественным образом могут быть расширены в последовательность гипероператоров следующим образом:
Умножение натуральных чисел может быть определено через повторно производимую операцию сложения («сложить Шаблон:Mvar копий числа Шаблон:Mvar»):
- <math>
\begin{matrix}
a\times b & = & \underbrace{a+a+\dots+a} \\
& & b
\end{matrix}
</math>,
например,
- <math>
\begin{matrix} 4\times 3 & = & \underbrace{4+4+4} & = & 12\\
& & 3
\end{matrix}
</math>.
Возведение числа Шаблон:Mvar в степень Шаблон:Mvar может быть определено как повторно производимая операция умножения («перемножить Шаблон:Mvar копий числа Шаблон:Mvar»), и в обозначениях Кнута эта запись выглядит как одиночная стрелочка, указывающая вверх:
- <math>
\begin{matrix}
a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\
& b
\end{matrix}
</math>
Например,
- <math>
\begin{matrix}
4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\
& 3
\end{matrix}
</math>
Такая одиночная стрелка вверх использовалась в качестве значка степени в языке программирования Алгол.
Продолжая далее последовательность операций за пределы возведения в степень, Дональд Кнут ввёл понятие оператора «двойная стрелочка» для записи тетрации (многократного возведения в степень):
- <math>
\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>
\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>3\uparrow\uparrow2=3^3=27 </math>,
- <math>3\uparrow\uparrow3=3^{3^3}=3^{27}=7\,625\,597\,484\,987 </math>,
- <math>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>3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7\,625\,597\,484\,987}} </math>,
- и так далее.
Уже это приводит к довольно большим числам, но система обозначений на этом не заканчивается. Оператор «тройная стрелочка» используется для записи повторного возведения в степень оператора «двойная стрелочка» (также известного как «пентация»):
- <math>
\begin{matrix}
a\uparrow\uparrow\uparrow b= &
\underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\
& b
\end{matrix}
</math>,
затем оператора «четверная стрелочка»:
- <math>
\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>
Шаблон:Итд Общее правило оператор «Шаблон:Mvar-я стрелочка», в соответствии с правой ассоциативностью, продолжается вправо в последовательную серию операторов «Шаблон:Mvar-1 стрелочка». Символически это можно записать следующим образом:
- <math>
\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>3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7\,625\,597\,484\,987</math>,
- <math>
\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>a \uparrow^n b</math> обычно используется для записи <math>a \uparrow\uparrow \dots \uparrow b</math> с n стрелочками.
Система обозначений
В таких выражениях как <math>a^b</math>, обычно для обозначения возведения в степень пишут показатель степени <math>b</math> как верхний индекс основания <math>a</math>. Но многие другие среды — такие как языки программирования и e-mail — не поддерживают подобную двумерную конфигурацию. Поэтому пользователи должны использовать линейную форму записи <math>a \uparrow b</math> для таких сред; стрелочка наверх предлагает возвести в степень степени. Если среди доступных символов нет стрелочки вверх, тогда вместо неё используется корректурный знак вставки «^».Верхний индекс записи <math>a^b</math> сам по себе не приспособлен к обобщению, что объясняет, почему Дональд Кнут вместо такой формы записи выбрал линейную форму записи <math>a \uparrow b</math>.
Обозначение «↑»
Попытка написать выражение <math>a \uparrow \uparrow b</math>, используя знакомую форму записи с показателями степени, порождает башню степеней. Например:
- <math>a \uparrow \uparrow 4 = a \uparrow a \uparrow a \uparrow a = a^{a^{a^a}}</math>.
Если b является переменной величиной (или очень большое), башня степеней может быть записана, используя точки и с пометкой, показывающей высоту башни
- <math>a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}</math>.
Используя такую форму записи, выражение <math>a \uparrow \uparrow \uparrow b</math> может быть записано как набор (стек) таких степенных башен, каждая из которых показывает степень вышележащей
- <math>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>a \uparrow \uparrow \uparrow b =
\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b</math>.
Более того, выражение <math>a \uparrow \uparrow \uparrow \uparrow b</math> может быть записано, используя несколько колонок подобных степенных башен, где каждая колонна показывает число степенных башен в наборе слева
- <math>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>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>a \uparrow^n b</math> как итерацию возведения в степень для любого a, n и b (хотя понятно, что и это становится достаточно громоздким).
Использование тетрации
Форма записи <math>^{b}a</math> в виде тетрации позволяет упростить такие схемы, при этом продолжая использовать геометрическое представление (мы можем их назвать тетрационными башнями).
- <math> a \uparrow \uparrow b = { }^{b}a</math>,
- <math> a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}</math>,
- <math> a \uparrow \uparrow \uparrow \uparrow b =
\left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b</math>.
Наконец, в качестве примера, четвёртое число Аккермана <math>4 \uparrow^4 4</math> может быть записано в виде:
- <math>\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>\uparrow^n</math> предпочтительней (и также для описания с изменяемым числом стрелочек), или эквивалентно, гипероператорам. Но некоторые числа настолько огромны, что даже подобная запись недостаточна. Например, число Грэма. Для его записи может быть использована цепочка Конвея: цепочка из трёх элементов эквивалентна другой системе записи, но цепочка из четырёх и более элементов является более мощной формой записи.
- <math>
\begin{matrix}
a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\
\mbox{(Knuth)} & & & & \mbox{(Conway)}
\end{matrix}
</math>
Общепринято использовать стрелочную форму записи Кнута для маленького размера чисел, а цепные стрелочки или гипероператоры для большого размера.
Определение
Обозначение стрелочка вверх формально определяется так
- <math>
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>a, b, n,</math> где <math>b \ge 0, n \ge 1</math>.
Все стрелочные операторы (включая обычное возведение в степень, <math>a \uparrow b</math>) обладают правой ассоциативностью, то есть, их вычисление осуществляется справа налево, если выражение содержит два и более подобных оператора. Например,
- <math>a \uparrow b \uparrow c = a \uparrow (b \uparrow c)</math>, но не <math>(a \uparrow b) \uparrow c</math>;
- <math>3\uparrow\uparrow 3=3^{3^3}</math> равно <math>3^{(3^3)}=3^{27}=7625597484987</math>, но не <math>\left(3^3\right)^3=27^3=19683.</math>
Есть хорошая причина для подобного выбора направления вычисления справа налево. Если бы мы использовали способ вычисления слева направо, тогда <math>a \uparrow\uparrow b</math> было бы равно <math>a \uparrow (a \uparrow (b - 1))</math>, и тогда <math>\uparrow\uparrow</math> в действительности не являлся бы новым оператором.
Правая ассоциативность также естественна по следующей причине. Мы можем переписать повторяемые стрелочные выражения <math>a\uparrow^n\cdots\uparrow^na,</math> которые появляются при расширении <math>a \uparrow^{n + 1}b</math> в виде <math>a\uparrow^n\cdots\uparrow^na\uparrow^n1</math>, где всe a становятся левыми операндами стрелочных операторов. Это важно, так как стрелочные операторы не являются коммутативными.
Записывая <math>(a\uparrow ^m)^b</math> как функциональный показатель степени b функции <math>f(x)=a\uparrow ^m x,</math> мы получим <math>a\uparrow ^n b = (a\uparrow ^{n-1})^b 1</math>.
Определение можно продолжить ещё на один шаг, начиная с <math>a\uparrow^n b = a b</math> для n = 0, так как возведение в степень есть повторяемое умножение, начиная с 1. Экстраполировать ещё на один шаг, записывая умножение как повторяемое сложение, не совсем верно так как умножение есть повторяемое сложение, начиная с 0 вместо 1. «Экстраполируя» снова на один шаг, записывая добавочный n как повторяемое добавление 1, требует начинать с числа a. Это отличие также подчёркивается в определении гипероператора, где начальные значения для сложения и умножения задаются раздельно.
Таблица значений
Расчёт <math>2\uparrow^m n</math> может быть переформулирован в терминах бесконечной таблицы. Мы размещаем числа <math>2^n</math> в верхнем ряду и заполняем колонку слева числом 2. Для определения числа в таблице следует взять число, ближайшее слева, затем найти сверху требуемое число в предыдущем ряду, в позиции, заданной только что полученным значением.
| m\n | 1 | 2 | 3 | 4 | 5 | 6 | Формула |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 4 | 8 | 16 | 32 | 64 | <math>2^n</math> |
| 2 | 2 | 4 | 16 | 65536 | <math>2^{65536}\approx 2{,}0 \times 10^{19,729}</math> | <math>2^{2^{65536}}\approx 10^{6{,}0 \times 10^{19,728}}</math> | <math>2\uparrow\uparrow n</math> |
| 3 | 2 | 4 | 65536 | <math>
\begin{matrix}
\underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\
65536\end{matrix}
</math>|| || || <math>2\uparrow\uparrow\uparrow n</math> | |||
| 4 | 2 | 4 | <math>
\begin{matrix}
\underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\
65536
\end{matrix}</math>|| || ||
|
<math>2\uparrow\uparrow\uparrow\uparrow n</math> |
Таблица такая же, как в статье функция Аккермана, за исключением сдвига в значениях <math>m</math> и <math>n</math>, и в добавке в размере 3 ко всем значениям.
Расчёт <math>3\uparrow^m n</math>
Мы размещаем числа <math>3^n</math> в верхнем ряду и заполняем колонку слева числом 3. Для определения числа в таблице следует взять число, ближайшее слева, затем найти сверху требуемое число в предыдущем ряду, в позиции, заданной только что полученным значением.
| m\n | 1 | 2 | 3 | 4 | 5 | Формула |
|---|---|---|---|---|---|---|
| 1 | 3 | 9 | 27 | 81 | 243 | <math>3^n</math> |
| 2 | 3 | 27 | 7,625,597,484,987 | <math>3^{7,625,597,484,987}</math> | <math>3\uparrow\uparrow n</math> | |
| 3 | 3 | 7,625,597,484,987 | <math>
\begin{matrix}
\underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
7,625,597,484,987
\end{matrix}</math>|| || || <math>3\uparrow\uparrow\uparrow n</math>
| |||
| 4 | 3 | <math>\begin{matrix}
\underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
7,625,597,484,987
\end{matrix}</math>|| || ||
|
<math>3\uparrow\uparrow\uparrow\uparrow n</math> |
Расчёт <math>10\uparrow^m n</math>
Мы размещаем числа <math>10^n</math> в верхнем ряду и заполняем колонку слева числом 10. Для определения числа в таблице следует взять число, ближайшее слева, затем найти сверху требуемое число в предыдущем ряду, в позиции, заданной только что полученным значением.
| m\n | 1 | 2 | 3 | 4 | 5 | Формула |
|---|---|---|---|---|---|---|
| 1 | 10 | 100 | 1000 | 10,000 | 100,000 | <math>10^n</math> |
| 2 | 10 | 10,000,000,000 | <math>10^{10,000,000,000}</math> | <math>10^{10^{10,000,000,000}}</math> | <math>10^{10^{10^{10,000,000,000}}}</math> | <math>10\uparrow\uparrow n</math> |
| 3 | 10 | <math>
\begin{matrix}
\underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
10
\end{matrix}</math>||<math>
\begin{matrix}
\underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
10^{10}
\end{matrix}</math>||<math>
\begin{matrix}
\underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
10^{10^{10}}
\end{matrix}</math>|| || <math>10\uparrow\uparrow\uparrow n</math>
| ||||
| 4 | 10 | <math>
\begin{matrix}
\underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
10
\end{matrix}</math>||<math>
\begin{matrix}
\underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
10^{10}
\end{matrix}</math>|| ||
|
<math>10\uparrow\uparrow\uparrow\uparrow n</math> |
Для 2 ≤ n ≤ 9 численное расположение <math>10\uparrow^m n</math> является лексикографическим порядком с m как наиболее значимым числом, так что порядок чисел этих 8 колонок есть просто линия-за-линией. То же самое применимо и для чисел в 97 колонках с 3 ≤ n ≤ 99, и мы начинаем с m = 1 даже для 3 ≤ n ≤ 9,999,999,999.
Примечания
Ссылки
