Открыть главное меню

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

(перенаправлено с «Стрелки Кнута»)

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

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

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

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

ВведениеПравить

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

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

 

Например,

 

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

 

Например,

 

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

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

 

Например,

 

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

 
 
 
 
и так далее.

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

 

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

 

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

 

Например:

 
 

Форма обозначения   обычно используется для записи   с n стрелочками.

Система обозначенийПравить

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


Обозначение «↑»Править

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

 

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

 

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

 

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

 

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

 

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

 


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

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

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

 
 
 

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

 

ОбобщениеПравить

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

 

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

ОпределениеПравить

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

 

для всех целых   где  .

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

 , но не  ;
  равно  , но не  

Есть хорошая причина для подобного выбора направления вычисления справа налево. Если бы мы использовали способ вычисления слева направо, тогда   было бы равно  , и тогда   в действительности не являлся бы новым оператором.

Правая ассоциативность также естественна по следующей причине. Мы можем переписать повторяемые стрелочные выражения   которые появляются при расширении   в виде  , где всe a становятся левыми операндами стрелочных операторов. Это важно, так как стрелочные операторы не являются коммутативными.

Записывая   как функциональный показатель степени b функции   мы получим  .

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

Таблица значенийПравить

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

Значения   = hyper(2, m + 2, n) = 2 → n → m
m\n 1 2 3 4 5 6 Формула
1 2 4 8 16 32 64  
2 2 4 16 65536      
3 2 4 65536        
4 2 4          

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

Расчёт  

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

Значения   = hyper(3, m + 2, n) = 3 → n → m
m\n 1 2 3 4 5 Формула
1 3 9 27 81 243  
2 3 27 7,625,597,484,987      
3 3 7,625,597,484,987        
4 3          

Расчёт  

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

Значения   = hyper(10, m + 2, n) = 10 → n → m
m\n 1 2 3 4 5 Формула
1 10 100 1,000 10,000 100,000  
2 10 10,000,000,000        
3 10          
4 10          

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

ПримечанияПравить

  1. Knuth, Donald E. Mathematics and Computer Science: Coping with Finiteness (англ.) // Science : journal. — 1976. — Vol. 194. — P. 1235—1242. — DOI:10.1126/science.194.4271.1235.

СсылкиПравить