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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике стрелочная нота́ция Кну́та — это метод для записи больших чисел, предложенный Дональдом Кнутом в 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{7625597484987 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.

Ссылки[править | править исходный текст]