Цепная нотация стрел

Цепная нотация стрел
Темпы роста	Оригинал: '"`UNIQ--postMath-00000001-QINU`"' (БРИ) Расширение Харфорда: '"`UNIQ--postMath-00000002-QINU`"' '"`UNIQ--postMath-00000003-QINU`"' Расширение Cookiefonster:'"`UNIQ--postMath-00000004-QINU`"' Расширение Выходника: '"`UNIQ--postMath-00000005-QINU`"'
Автор(ы)	Оригинал: Д. Х. Конвей и Р. К. Гай Расширения: Питер Харфорд; Cookiefonster; Выходник
Нотация	Оригинал: '"`UNIQ--postMath-00000006-QINU`"' Расширение Харфорда: '"`UNIQ--postMath-00000007-QINU`"' Расширение Cookiefonster: '"`UNIQ--postMath-00000008-QINU`"' Расширение Выходника: '"`UNIQ--postMath-00000009-QINU`"'
Год	1995 (Оригинал) 2005 (Расширение Харфорда) 2011 (Расширение Cookiefonster)

Цепная нотация стрел — обобщение стрелочной нотации Кнута, разработанное Д. Х. Конвеем и Р. К. Гаем.

Пользователи англоязычной гуголия вики Натан Хо и Воджову показали, что цепная нотация стрел завершается, то есть её выходные данные существуют для всех входных последовательностей.

Согласно доказательству Берда, цепная нотация стрел примерно сопоставима с массивами с 4 элементами в линейной нотации Джонатана Бауэрса, но намного уступает массивам с 5 элементами или более.

Определение

1. $a \rightarrow b = a^b$
2. $a \rightarrow b \rightarrow c = a \uparrow^{c} b = a\underbrace{\uparrow\ ... \uparrow}_c b$
3. $a \rightarrow ... \rightarrow b \rightarrow 1 = a \rightarrow ... \rightarrow b$ — Если последняя запись равна 1, она будет проигнорирована.
4. $a \rightarrow ... \rightarrow b \rightarrow 1 \rightarrow c = a \rightarrow ... \rightarrow b$
5. $a \rightarrow ... \rightarrow b \rightarrow (c + 1) \rightarrow (d + 1) = a \rightarrow ... \rightarrow b \rightarrow (a \rightarrow ... \rightarrow b \rightarrow c \rightarrow (d + 1) ) \rightarrow d$

Обратите внимание, что стрелка $\rightarrow$ не является оператором в общепринятом смысле; $a \rightarrow b \rightarrow c$ не равна ни $a \rightarrow (b \rightarrow c)$, ни $(a \rightarrow b) \rightarrow c$. Вся цепочка (которую можно было бы представить как массив) представляет собой единственную операцию.

Примеры

Вот несколько небольших примеров цепной стрелочной нотации в действии:

$2 \rightarrow 2 \rightarrow 2 \rightarrow 2$ = $2 \rightarrow 2 \rightarrow (2 \rightarrow 2 \rightarrow 1 \rightarrow 2) \rightarrow 1$ = $2 \rightarrow 2 \rightarrow 4 \rightarrow 1$ = $2\uparrow\uparrow\uparrow\uparrow 2$ = 4

$3 \rightarrow 3 \rightarrow 2 = 3\uparrow\uparrow3 = 7,625,597,484,987$

$3 \rightarrow 3 \rightarrow 2 \rightarrow 2$

$= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2) \rightarrow 1$

$= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1 \rightarrow 2)$

$= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3)$

$= 3 \rightarrow 3 \rightarrow (3^{3})$

$= 3 \rightarrow 3 \rightarrow 27$

$= 3 \uparrow^{27} 3$

Функция CG

Используя цепную нотацию стрел, Конвей и Гай написали "Первые три из нашей быстро увеличивающейся последовательности чисел: 1, $2 \rightarrow 2$, $3 \rightarrow 3 \rightarrow 3$, $4 \rightarrow 4 \rightarrow 4 \rightarrow 4$, ...", что подразумевает, что они определили функцию, подобную числу Аккермана; $cg(n) = \underbrace{n \rightarrow n \rightarrow ... \rightarrow n \rightarrow n}_n$. Хотя оно равно числам Аккермана для "n" от 1 до 3, $cg (4) = 4\rightarrow 4\rightarrow 4\rightarrow 4 > \{4,4,3,2\}$, используя доказательство Берда. Следовательно, cg (4) намного, намного больше, чем знаменитое число Грэма (фактически, то же самое можно сказать и о гораздо меньшем тетратри Конвея).

Скорость роста этой функции составляет около $f_{\omega^2}(n)$ в быстрорастущей иерархии. Это сравнимо с линейными массивами с 4 входами в BEAF или BAN. В нотации нотаций массива функция CG может быть записана как (n{3,n}n).

Расширение Питера Харфорда

Питер Харфорд расширяет цепную нотацию стрел, добавляя следующее правило:

$a \rightarrow_c b = \underbrace{a \rightarrow_{c-1} a \rightarrow_{c-1}\ldots\rightarrow_{c-1} a \rightarrow_{c-1}a}_{b \rightarrow_{c-1}}$

Все обычные правила остаются неизменными. Таким образом, они применяют игнорирование нижних индексов. Обратите внимание, что выражения типа $3 \rightarrow_{2} 3 \rightarrow 3$ не соответствует правилам; всё выражение должно иметь один тип стрелок вправо. Кроме того, Харфорд показывает, что $n \rightarrow_{n} n$ - это примерно $f_{\omega^{3}}(n)$ в быстрорастущей иерархии.

Кроме того, он определяет функцию C(n) следующим образом:

$C(a) = a \rightarrow_a a$
$C(a,1) = a \rightarrow_{C(a)} a$
$C(a,b) = a \rightarrow_{C(a,b-1)} a$
$C(a,1,1) = C(a,C(a,a))$
$C(a,b,1) = C(a,C(a,b-1,1))$
$C(a,1,c) = C(a,C(a,a,c-1),c-1)$
$C(a,b,c) = C(a,C(a,b-1,c),c-1)$

Функция $f(n) = C(n,n,n)$ растёт примерно так же быстро, как $f_{\omega^{3} + \omega}(n)$ в быстрорастущей иерархии.

Расширение Cookiefonster

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

• $a \rightarrow^1 b = a^{b}$
• $a \rightarrow^x b = a \rightarrow^{x-1} a \rightarrow^{x-1} a \cdots \rightarrow^{x-1} a \rightarrow^{x-1} a$, где a повторяется b раз
• #$\rightarrow^x 1 =$# (здесь # обозначает произвольно длинную часть цепочки перед соответствующими терминами)
• #$\rightarrow^x 1 \rightarrow^y a =$# (источник случайно использует две стрелки $\rightarrow^x$, подразумевая, что они должны быть одинаковыми, но это не обязательно)
• #$\rightarrow^n a \rightarrow^1 b =$#$\rightarrow^n ($#$\rightarrow^n (a-1) \rightarrow^1 b) \rightarrow^1 (b-1)$
• #$\rightarrow^n a\rightarrow^x b =$#$\rightarrow^n a \rightarrow^{x-1} a \rightarrow^{x-1} a \cdots \rightarrow^{x-1} a$, где a повторяется b раз

Функция $f(n) = n \rightarrow^n n$ растёт примерно так же быстро, как $f_{\omega^\omega}(n)$ в быстрорастущей иерархии.