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

Стрелочная нотация
Темпы роста	'"`UNIQ--postMath-00000002-QINU`"' >* все примитивно-рекурсивные функции
Автор(ы)	Дональд Кнут
Нотация	'"`UNIQ--postMath-00000001-QINU`"'
Год	1976

Стрелочная нотация или нотация со стрелками вверх — широко используемая нотация для гипероператоров, разработанная Дональдом Кнутом в 1976 году для представления больших чисел. Кнут грубо представил $a\uparrow b$ как $a^b$ и $a\underbrace {\uparrow \cdots \uparrow } _{n{\text{ раз}}}b$ как $\underbrace {a\underbrace {\uparrow \cdots \uparrow } _{n-1}a\cdots a\underbrace {\uparrow \cdots \uparrow } _{n-1}a} _{b{\text{ копий }}a}$, которое решается справа налево.

Определение

Мы объясняем точный смысл первоначального определения Кнута. Для любых натуральных чисел $a$, $b$ и $n$, $a \uparrow^n b$ определяется следующим рекурсивным способом:

$a\uparrow ^{n}b={\begin{cases}a^{b}&(n=1)\\a&(n\geq 1,b=1)\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1))&(n>1,b>1)\end{cases}}$

Эта нотация даёт общую вычислимую функцию
$\uparrow :\mathbb {N} _{>0}^{3}\leftarrow \mathbb {N} _{>0}$
$(a,b,n)\mapsto a\uparrow ^{n}b,$ где $\mathbb{N}_{>0}$ обозначает набор целых положительных чисел. Читатели должны быть осторожны, что некоторые авторы неявно расширяют его так, что $a\uparrow ^{n}0=1$ выполняется для любых целых положительных чисел $a$ и $n$.

Он удовлетворяет следующим соотношениям, которые также характеризуют нотацию для любых целых положительных чисел $a$, $b$ и $n$:

$a\uparrow^{1}b=a^b$
$a\uparrow^{n}1=a$
$a\uparrow ^{n+1}(b+1)=a\uparrow ^{n}(a\uparrow ^{n+1}b)$

Здесь $a \uparrow^n b$ рассматривается как сокращение для $a \uparrow\uparrow\cdots\uparrow\uparrow b$ с $n$ стрелками. Итак, например, у нас есть $a \uparrow^2 b = a \uparrow\uparrow b$. Операторы обозначения стрелками являются правоассоциативными; $a\uparrow b\uparrow c$ всегда означает $a\uparrow (b\uparrow c)$.

В частности, $a\uparrow b$ - это возведение в степень, $a \uparrow\uparrow b$ - это тетрация, $a \uparrow\uparrow\uparrow b$ - это пентация, и в целом $a \uparrow^n b$ является (n+ 2)-й гипероператором. В ASCII они часто записываются a^b, a^^b, a^^^b, ... или a**b, a***b, a****b в соответствии с некоторыми языками программирования, которые используют a^b или a**b для возведения в степень.

Приложение к гугологии

Функция $f(n)=n \uparrow^n n$ является быстрорастущей функцией, которая в конечном итоге доминирует над всеми примитивными рекурсивными функциями и может быть аппроксимирована с использованием быстрорастущей иерархии как $f_{\omega}(n)$. Это предел нерасширенных гипероператоров и, соответственно, стрелочной нотации.

Стрелочная нотация может соотноситься с гипер E нотацией с помощью следующего правила:

$a\uparrow ^{c}b=E[a]\underbrace {1\#1\#1\cdots \#b} _{c}$

для целых положительных чисел a, b, c. Например,

• a↑b = E[a]b
• a↑↑b = E[a]1#b
• * а↑↑↑b = E[a]1#1#б

Стрелочная нотация была обобщена на другие нотации. Несколько примечательных из них - Цепная нотация стрел, BEAF и BAN. Она также была точно сравнена, среди прочего, с нотацией нотаций массива с использованием функции (a {2, количество стрелок}b).

Натан Хо и Wojowu показали, что стрелочная нотация заканчивается — то есть $a \uparrow^n b$ существует для всех $a, b, n$.

Примеры

Примеры серий 2 ↑ⁿ 3 с цветами для $n=1,2,3,4,5$. Эта фотография включает в себя pt оператора.

• $2 \uparrow 3=2^3=8$
• $5 \uparrow 6 = 5^6 = 15,625$
• $10\uparrow 100=10^{100}=$ гуголу
• $3\uparrow \uparrow 4=3\uparrow 3\uparrow 3\uparrow 3=3\uparrow 3\uparrow 27=3^{7,625,597,484,987}\approx 1.2580143\cdot 10^{3638334640024}$
• $5\uparrow \uparrow 3=5\uparrow 5\uparrow 5=5^{5^{5}}\approx 1.9110126\cdot 10^{2184}$
• $2 \uparrow\uparrow\uparrow 2 = 2 \uparrow\uparrow 2 = 2 \uparrow 2 = 2^2 = 4$
• $2\uparrow \uparrow \uparrow \uparrow 2=2\uparrow \uparrow \uparrow 2=2\uparrow \uparrow 2=2\uparrow 2=2^{2}=4$
• $3 \uparrow\uparrow\uparrow 2 = 3 \uparrow\uparrow 3 = 3 \uparrow 3 \uparrow 3 = 3^{3^3} = 3^{27} = 7,625,597,484,987$
• $2 \uparrow\uparrow\uparrow 3 = 2 \uparrow\uparrow 2 \uparrow\uparrow 2 = 2 \uparrow\uparrow 4 = 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow 2 \uparrow 4 = 2 \uparrow 16 = 65,536$
• $3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow 7,625,597,484,987=\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3\uparrow 3} _{7,625,597,484,987{\text{ раз}}}$ = тритри
• $a\uparrow ^{n+1}2=a\uparrow ^{n}a$

Код для машины Тьюринга

Форма ввода: чтобы представить $a\uparrow^c b$, поместите a 1, затем c + 2 ^, затем b 1. Например, 111^^^^^111 вычисляет тритри.

Код для машины Тьюринга

0 * * r 0
0 _ _ l 1
1 1 _ l 2
2 ^ _ l 3
2 1 1 l 4
3 ^ _ l 3
3 1 _ l 2
4 1 1 l 4
4 ^ 1 l 4'
4 _ 1 l halt
4' ^ ^ l 5
4' 1 1 r 0
5 ^ ^ l 5
5 1 1 r 6
6 ^ x r 7
6 1 y r 9
6 | ^ l 12
7 * * r 7
7 _ | r 8
7 | | r 8
8 * * r 8
8 _ ^ l 11
9 * * r 9
9 | | r 10
10 * * r 10
10 _ 1 l 11
11 * * l 11
11 x ^ r 6
11 y 1 r 6
12 * * l 12
12 ^ ^ l 12'
12' ^ ^ l 12'
12' * * l 13
12' 1 x r 14
13 * * l 13
13 ^ ^ r 20
13 _ _ r 20
13 1 x r 14
14 * * r 14
14 ^ ^ r 15
15 ^ ^ r 15
15 x x r 16
15 1 x l 12
16 x x r 16
16 1 x l 12
16 ^ x r 17
17 ^ ^ r 17
17 1 ^ r 18
18 ^ 1 r 17
18 1 1 r 18
18 _ 1 l 19
19 * * l 19
19 x x l 12
20 x 1 r 20
20 ^ ^ r 21
21 ^ ^ r 21
21 x x r 22
22 x x r 22
22 1 _ r 23
22 ^ ^ l 30
23 1 _ r 23
23 ^ ^ l 24
24 _ ^ r 25
25 ^ ^ r 25
25 1 1 l 26
26 ^ 1 r 27
27 1 1 r 27
27 _ _ l 28
28 1 _ l 29
29 * * l 29
29 _ ^ r 25
29 x 1 l 30
30 x 1 l 30
30 ^ ^ r 31
31 * * r 31
31 _ _ l 32
32 1 _ l 1