Для представления гиперопераций использовались различные обозначения . Одно из таких обозначений. Другое обозначение, инфиксная запись, удобная для ASCII . Обозначение известна как «обозначение квадратных скобок».
Обозначение Кнута со стрелкой вверх альтернативное обозначение. Получается заменой в квадратных скобках обозначением стрелки.
Возведение в степень для естественной силы определяется как повторное умножение, которое Кнут обозначил одной стрелкой вверх:
Например,
Тетрация определяется как повторное возведение в степень, которое Кнут обозначил «двойной стрелкой»:
Например,
Выражения оцениваются справа налево, поскольку операторы определены как правоассоциативные .
Согласно этому определению,
и т.п.
Это уже приводит к некоторым довольно большим числам, но последовательность гипероператоров на этом не заканчивается.
Пентация , определяемая как повторная тетрация, представлена «тройной стрелкой»:
Гексация , определяемая как повторная пентация, представлена «четверной стрелкой»:
и так далее. Общее правило состоит в том, чтоОператор -стрелка раскладывается в правоассоциативный ряд () -стрелочные операторы. Символично,
Примеры:
Обозначение
В таких выражениях, как , в обозначении возведения в степень обычно пишут показатель степени как надстрочный индекс к основному числу . Но многие среды, такие как языки программирования и электронная почта с обычным текстом , не поддерживают надстрочный набор. Люди приняли линейное обозначениедля таких сред; стрелка вверх предлагает «возвести в степень». Если набор символов не содержит стрелки вверх, вместо нее используется каретка (^).
Обозначение надстрочного индекса не поддается обобщению, что объясняет, почему Кнут решил работать с встроенной нотацией вместо.
это более короткое альтернативное обозначение n вверх. Таким образом.
Стрелы Кнута стали довольно популярными, может быть, потому, что это более сильный логотип, чем например. [ оригинальное исследование? ]
Написание нотации со стрелкой вверх в терминах степеней
Попытка написать использование знакомых надстрочных обозначений дает башню мощности.
Например:
Если b - переменная (или слишком большая), башня мощности может быть написана точками и примечанием, указывающим высоту башни.
Продолжая эти обозначения, можно было бы написать со стопкой таких мощных башен, каждая из которых описывает размер вышестоящей.
Опять же, если b - переменная или слишком большая, стек может быть записан с использованием точек и примечания, указывающего его высоту.
Более того, может быть записан с использованием нескольких столбцов таких стеков башен власти, каждый столбец описывает количество башен власти в стеке слева от него:
И вообще:
Это может выполняться бесконечно, чтобы представлять как повторное возведение в степень повторного возведения в степень для любых a , n и b (хотя это явно становится довольно громоздким).
Использование тетрации
Тетрация обозначенияпозволяет нам немного упростить эти диаграммы, но при этом использовать геометрическое представление (мы могли бы назвать эти диаграммы тетрационными башнями ).
Наконец, в качестве примера, четвертое число Аккермана можно представить как:
Обобщения
Некоторые числа настолько велики, что несколько стрелок в нотации Кнута, направленной вверх, становятся слишком громоздкими; затем оператор n- стрелкиполезен (а также для описаний с переменным количеством стрелок) или, что эквивалентно, гипероператоров .
Некоторые числа настолько велики, что даже этих обозначений недостаточно. Обозначения конвея затем могут быть использованы: цепочка из трех элементов эквивалентна с другими обозначениями, но цепь из четырех или более является еще более мощным.
знак равно , С знак равно знак равно , Таким образом, получается результат с
знак равно или же (Териллион)
Примечание: Gartrialogue = знак равно знак равно знак равно знак равно знак равно
Определение
Без ссылки на гипероперацию операторы стрелки вверх могут быть формально определены следующим образом:
для всех целых чисел с участием .
В этом определении используется возведение в степенькак базовый случай, и тетрация как повторное возведение в степень. Это эквивалентно последовательности гиперопераций, за исключением того, что в ней пропущены еще три основные операции: последовательность , сложение и умножение .
В качестве альтернативы можно выбрать умножение в качестве базового случая и итерации оттуда. Тогда возведение в степень становится повторным умножением. Формальное определение будет
для всех целых чисел с участием .
Обратите внимание, однако, что Кнут не определил «стрелку на ноль» (). Можно было бы расширить обозначение на отрицательные индексы (n ≥ -2) таким образом, чтобы согласовать со всей последовательностью гиперопераций, за исключением запаздывания в индексации:
Операция со стрелкой вверх является правоассоциативной операцией , то есть понимается как , вместо . Если двусмысленность не является проблемой, скобки иногда опускаются.
Таблицы значений
Вычисление 0 ↑ n b
Вычисление приводит к
0, когда n = 0 [nb 1]
1, когда n = 1 и b = 0 [nb 2] [nb 3]
0, когда n = 1 и b > 0 [nb 2] [nb 3]
1, когда n > 1 и b четно (включая 0)
0, когда n > 1 и b нечетно
Вычисление 2 ↑ n b
Вычисление можно переформулировать в виде бесконечной таблицы. Ставим числа в верхней строке и заполните левый столбец значениями 2. Чтобы определить число в таблице, возьмите число сразу влево, затем найдите необходимое число в предыдущей строке в позиции, заданной только что взятым числом. .
Ценности знак равно ЧАС п + 2 ( 2 , б ) {\ displaystyle H_ {n + 2} (2, b)} знак равно 2 [ п + 2 ] б {\ Displaystyle 2 [п + 2] б}
= 2 → b → 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 ↑ n b
Ставим числа в верхней строке и заполните левый столбец значениями 3. Чтобы определить число в таблице, возьмите число сразу влево, затем найдите требуемое число в предыдущей строке в позиции, заданной только что взятым числом. .
Ценности знак равно ЧАС п + 2 ( 3 , б ) {\ displaystyle H_ {n + 2} (3, b)} знак равно 3 [ п + 2 ] б {\ Displaystyle 3 [п + 2] Ь}
= 3 → b → 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
Вычисление 4 ↑ n b
Ставим числа в верхней строке и заполните левый столбец значениями 4. Чтобы определить число в таблице, возьмите число сразу влево, затем найдите требуемое число в предыдущей строке в позиции, заданной только что взятым числом. .
Ценности знак равно ЧАС п + 2 ( 4 , б ) {\ displaystyle H_ {n + 2} (4, b)} знак равно 4 [ п + 2 ] б {\ Displaystyle 4 [п + 2] Ь}
= 4 → b → n
б
ⁿ
1
2
3
4
5
формула
1
4
16
64
256
1024
2
4
256
3
4
4
4
Вычисление 10 ↑ n b
Ставим числа в верхней строке и заполните левый столбец значениями 10. Чтобы определить число в таблице, возьмите число сразу влево, затем найдите требуемое число в предыдущей строке в позиции, заданной только что взятым числом. .
Ценности знак равно ЧАС п + 2 ( 10 , б ) {\ displaystyle H_ {n + 2} (10, b)} знак равно 10 [ п + 2 ] б {\ displaystyle 10 [n + 2] b}
= 10 → b → 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 ≤ b ≤ 9 порядковый номер чисел- это лексикографический порядок, где n - самое старшее число, поэтому для номеров этих 8 столбцов числовой порядок просто построчный. То же самое относится к числам в 97 столбцах с 3 ≤ b ≤ 99, и если мы начнем с n = 1, даже для 3 ≤ b ≤ 9,999,999,999.
Смотрите также
Примитивная рекурсия
Гипероперация
Занятый бобер
Обозначение бара Катлера
Тетрация
Пентация
Функция Аккермана
Число Грэма
Обозначения Штейнгауза – Мозера
Заметки
^ Имейте в виду, что Кнут не определил оператор.
^ a b Подробнее см. Степень нуля .
^ a b Подробнее см. Ноль в степени нуля .
Рекомендации
^ Кнут, Дональд Э. (1976). «Математика и информатика: справляемся с конечностью». Наука . 194 (4271): 1235–1242. Bibcode : 1976Sci ... 194.1235K . DOI : 10.1126 / science.194.4271.1235 . PMID 17797067 .
^Р.Л. Гудштейн (декабрь 1947 г.). "Трансфинитные порядковые числа в рекурсивной теории чисел". Журнал символической логики . 12 (4): 123–129. DOI : 10.2307 / 2266486 . JSTOR 2266486 .
Внешние ссылки
Вайсштейн, Эрик В. "Нотация Кнута, направленная вверх" . MathWorld .
Роберт Мунафо, Большие числа: высшие гипероператоры