В математике стрелочная нота́ция Кну́та — это метод для записи больших чисел. Её идея основывается на том, что умножение — множественное сложение, возведение в степень — множественное умножение. Была предложена Дональдом Кнутом в 1976 году. Тесно связана с функцией Аккермана и последовательностью гипероператоров.
Тетрация, записанная с помощью стрелочной нотации Кнута: .
Пентация в обозначениях Кнута:
.
В указанных обозначениях присутствует операндов, каждый из которых равен , соответственно операции повторяются раз.
Введение Обычные арифметические операции — сложение, умножение и возведение в степень — естественным образом могут быть расширены в последовательность гипероператоров следующим образом:
Умножение натуральных чисел может быть определено через повторно производимую операцию сложения («сложить копий числа »):
Например,
Возведение числа в степень может быть определено как повторно производимая операция умножения («перемножить копий числа »), и в обозначениях Кнута эта запись выглядит как одиночная стрелочка, указывающая вверх:
Например,
Такая одиночная стрелка вверх использовалась в качестве значка степени в языке программирования Алгол.
Продолжая далее последовательность операций за пределы возведения в степень, Дональд Кнут ввёл понятие оператора «двойная стрелочка» для записи тетрации (многократного возведения в степень):
Например,
Здесь и далее вычисление выражения всегда идёт справа налево. Также и стрелочные операторы Кнута (как и операция возведение в степень) по определению обладают правой ассоциативностью (очерёдностью справа налево). Согласно данному определению,
...
Уже это приводит к довольно большим числам, но система обозначений на этом не заканчивается. Оператор «тройная стрелочка» используется для записи повторного тетрирования (также известного как «пентация»):
затем через повторение тройной стрелочки определяется оператор «четверная стрелочка»:
Общее правило оператор «-я стрелочка», в соответствии с правой ассоциативностью, продолжается вправо в последовательную серию операторов «-1 стрелочка». Символически это можно записать следующим образом:
Например:
Форма обозначения обычно используется для записи с n стрелочками.
Система обозначений
В таких выражениях как , обычно для обозначения возведения в степень пишут показатель степени как верхний индекс основания . Но многие другие среды — такие как языки программирования и e-mail — не поддерживают подобную двумерную конфигурацию. Поэтому пользователи должны использовать линейную форму записи для таких сред; стрелочка наверх предлагает возвести в степень степени. Если среди доступных символов нет стрелочки вверх, тогда вместо неё используется циркумфлекс «^».Верхний индекс записи сам по себе не приспособлен к обобщению, что объясняет, почему Дональд Кнут вместо такой формы записи выбрал линейную форму записи .
Обозначение «↑»
Попытка написать выражение , используя знакомую форму записи с показателями степени, порождает башню степеней. Например: .
Если b является переменной величиной (или очень большое), башня степеней может быть записана, используя точки и с пометкой, показывающей высоту башни .
Используя такую форму записи, выражение может быть записано как набор (стек) таких степенных башен, каждая из которых показывает степень вышележащей .
И снова, если b является переменной величиной (или очень большое), набор таких степенных башен может быть записан, используя точки и с пометкой, показывающей их высоты
.
Более того, выражение может быть записано, используя несколько колонок подобных степенных башен, где каждая колонна показывает число степенных башен в наборе слева
.
В более общем случае:
.
Так можно писать неограниченно долго, чтобы представить как итерацию возведения в степень для любого a, n и b (хотя понятно, что и это становится достаточно громоздким).
Использование тетрации
Форма записи в виде тетрации позволяет упростить такие схемы, при этом продолжая использовать геометрическое представление (мы можем их назвать тетрационными башнями).
,
,
.
Наконец, в качестве примера, четвёртое число Аккермана может быть записано в виде: .
Обобщение Некоторые числа настолько большие, что даже запись стрелочками Кнута становится слишком громоздкой; в этом случае использование оператора n-стрелочка предпочтительней (и также для описания с изменяемым числом стрелочек), или эквивалентно, гипероператорам. Но некоторые числа настолько огромны, что даже подобная запись недостаточна. Например, число Грэма. Для его записи может быть использована цепочка Конвея: цепочка из трёх элементов эквивалентна другой системе записи, но цепочка из четырёх и более элементов является более мощной формой записи.
Общепринято использовать стрелочную форму записи Кнута для маленького размера чисел, а цепные стрелочки или гипероператоры для большого размера.
Определение
Обозначение стрелочка вверх формально определяется так
для всех целых где .
Все стрелочные операторы (включая обычное возведение в степень, ) обладают правой ассоциативностью, то есть, их вычисление осуществляется справа налево, если выражение содержит два и более подобных оператора. Например, , но не ; равно , но не Есть хорошая причина для подобного выбора направления вычисления справа налево. Если бы мы использовали способ вычисления слева направо, тогда было бы равно , и тогда в действительности не являлся бы новым оператором.
Правая ассоциативность также естественна по следующей причине. Мы можем переписать повторяемые стрелочные выражения которые появляются при расширении в виде , где все 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 3 2 4 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 3 3 4 3
Расчёт
Мы размещаем числа в верхнем ряду и заполняем колонку слева числом 10. Для определения числа в таблице следует взять число, ближайшее слева, затем найти сверху требуемое число в предыдущем ряду, в позиции, заданной только что полученным значением.
+Значения = hyper(10, m + 2, n) = 10 → n → m m\n 1 2 3 4 5 Формула 1 10 100 2 10 3 10 4 10
Для 2 ≤ n ≤ 9 численное расположение является лексикографическим порядком с m как наиболее значимым числом, так что порядок чисел этих 8 колонок есть просто линия-за-линией. То же самое применимо и для чисел в 97 колонках с 3 ≤ n ≤ 99, и мы начинаем с m = 1 даже для 3 ≤ n ≤ 9,999,999,999.
Примечания
Ссылки
Категория:Дональд Кнут Категория:Математические операции Категория:Большие числа