Обозначение стрелок Конвея

Стрелочная нотация Конвея , созданная математиком Джоном Хортоном Конвеем , является средством выражения некоторых чрезвычайно больших чисел . ^[1] Это просто конечная последовательность натуральных чисел, разделенных стрелками вправо, например .${\ Displaystyle 2 \ до 3 \ до 4 \ до 5 \ до 6}$

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

Определение и обзор

«Цепь Конвея» определяется следующим образом:

• Любое положительное целое число - это цепочка длины .${\ displaystyle 1}$
• Цепочка длины n , за которой следует стрелка вправо → и положительное целое число, вместе образуют цепочку длины .${\ displaystyle n + 1}$

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

Если , и положительные целые числа, и является подцепь, то:${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle r}$${\ displaystyle X}$

1. Пустая цепочка (или цепочка длины 0) равна , а цепочка представляет собой число .${\ displaystyle 1}$${\ displaystyle p}$${\ displaystyle p}$
2. ${\ displaystyle X \ to 1}$эквивалентно .${\ displaystyle X}$
3. ${\ displaystyle p \ rightarrow q \ rightarrow r}$эквивалентно . (см . обозначение стрелки Кнута вверх )${\ displaystyle p [\ uparrow ^ {r}] q}$
4. ${\ Displaystyle Х \ к р \ к (д + 1)}$эквивалентно (с копиями , копиями и парами скобок; применяется для  > 0).${\ Displaystyle Икс \ к (Икс \ к (\ cdots (X \ к (X) \ к q) \ cdots) \ к q) \ к q}$
   ${\ displaystyle p}$${\ displaystyle X}$${\ displaystyle p-1}$${\ displaystyle q}$${\ displaystyle p-1}$${\ displaystyle q}$
5. Поскольку эквивалентно (По правилу 2), а также = , (По правилу 3) мы можем определить равным${\ displaystyle p \ rightarrow q \ rightarrow 1}$${\ displaystyle p \ to q}$${\ displaystyle p \ uparrow q}$${\ displaystyle p ^ {q}}$${\ displaystyle p \ to q}$${\ displaystyle p ^ {q}}$

Обратите внимание, что четвертое правило можно заменить, многократно применяя два правила, чтобы избежать эллипсов :

4а. эквивалентно${\displaystyle X\to 1\to (q+1)}$${\displaystyle X}$

4b. эквивалентно${\displaystyle X\to (p+1)\to (q+1)}$${\displaystyle X\to (X\to p\to (q+1))\to q}$

Характеристики

1. Цепь оценивает абсолютную степень своего первого числа.
2. Следовательно, равно${\displaystyle 1\to Y}$${\displaystyle 1}$
3. ${\displaystyle X\to 1\to Y}$ эквивалентно ${\displaystyle X}$
4. ${\displaystyle 2\to 2\to Y}$ равно ${\displaystyle 4}$
5. ${\displaystyle X\to 2\to 2}$ эквивалентно (не путать с )${\displaystyle X\to (X)}$${\displaystyle X\to X}$

Интерпретация

Следует внимательно относиться к цепочке стрел в целом . Цепочки стрелок не описывают повторное применение бинарного оператора. В то время как цепочки других инфиксных символов (например, 3 + 4 + 5 + 6 + 7) часто можно рассматривать фрагментами (например, (3 + 4) + 5 + (6 + 7)) без изменения значения (см. Ассоциативность ), или, по крайней мере, может оцениваться шаг за шагом в заданном порядке, например 3 ^{4 5 6 7} справа налево, что не так с цепочками стрелок Конвея.

Например:

• ${\displaystyle 2\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=16}$
• ${\displaystyle 2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^{3^{2}}=512}$
• ${\displaystyle \left(2\rightarrow 3\right)\rightarrow 2=\left(2^{3}\right)^{2}=64}$

Четвертое правило - это ядро: цепочка из 4 или более элементов, оканчивающихся на 2 или больше, становится цепочкой такой же длины с (обычно значительно) увеличенным предпоследним элементом. Но его конечный элемент уменьшается, что в конечном итоге позволяет второму правилу сократить цепочку. После, перефразируя Кнута , «много деталей», цепочка сокращается до трех элементов, а третье правило завершает рекурсию.

Примеры

Примеры быстро усложняются. Вот несколько небольших примеров:

${\displaystyle n}$

${\displaystyle =n}$ (По правилу 1)

${\displaystyle p\to q}$

${\displaystyle =p^{q}}$ (По правилу 5)

Таким образом, ${\displaystyle 3\to 4=3^{4}=81}$

${\displaystyle 4\to 3\to 2}$

${\displaystyle =4\uparrow \uparrow 3}$ (По правилу 3)

${\displaystyle =4\uparrow (4\uparrow 4)}$

${\displaystyle =4\uparrow 256}$

${\displaystyle =4^{256}}$

${\displaystyle =13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,030,073,}$ ${\displaystyle 546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096}$

${\displaystyle \approx 1.34*10^{154}}$

${\displaystyle 2\to 2\to a}$

${\displaystyle =2[\uparrow ^{a}]2}$ (По правилу 3)

${\displaystyle =4}$(см . обозначение стрелки Кнута вверх )

${\displaystyle 2\to 4\to 3}$

${\displaystyle =2\uparrow \uparrow \uparrow 4}$ (По правилу 3)

${\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow 4)}$

${\displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow (2\uparrow 2)))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow (2\uparrow 4))}$

${\displaystyle =2\uparrow \uparrow (2\uparrow 16)}$

${\displaystyle =2\uparrow \uparrow (65536)}$

${\displaystyle ={^{65536}2}}$(см. тетрацию )

${\displaystyle 2\to 3\to 2\to 2}$

${\displaystyle =2\to 3\to (2\to 3)\to 1}$ (По правилу 4)

${\displaystyle =2\to 3\to 8\to 1}$ (По правилу 5)

${\displaystyle =2\to 3\to 8}$ (По правилу 2)

${\displaystyle =2\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 3}$ (По правилу 3)

= намного больше, чем предыдущее число

${\displaystyle 3\to 2\to 2\to 2}$

${\displaystyle =3\to 2\to (3\to 2)\to 1}$ (По правилу 4)

${\displaystyle =3\to 2\to 9\to 1}$ (По правилу 5)

${\displaystyle =3\to 2\to 9}$ (По правилу 2)

${\displaystyle =3\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \uparrow 2}$ (По правилу 3)

= намного больше, чем предыдущее число

Систематические примеры

Самыми простыми случаями с четырьмя членами (не содержащими целых чисел меньше 2) являются:

• ${\displaystyle a\to b\to 2\to 2}$
  ${\displaystyle =a\to b\to 2\to (1+1)}$
  ${\displaystyle =a\to b\to (a\to b)\to 1}$
  ${\displaystyle =a\to b\to a^{b}}$
  ${\displaystyle =a[a^{b}+2]b}$

(эквивалент последнего упомянутого свойства)

• ${\displaystyle a\to b\to 3\to 2}$
  ${\displaystyle =a\to b\to 3\to (1+1)}$
  ${\displaystyle =a\to b\to (a\to b\to (a\to b)\to 1)\to 1}$
  ${\displaystyle =a\to b\to (a\to b\to a^{b})}$
  ${\displaystyle =a[a\to b\to 2\to 2+2]b}$
• ${\displaystyle a\to b\to 4\to 2}$
  ${\displaystyle =a\to b\to (a\to b\to (a\to b\to a^{b}))}$
  ${\displaystyle =a[a\to b\to 3\to 2+2]b}$

Здесь мы видим закономерность. Если для любой цепи мы позволим then (см. Функциональные возможности ).${\displaystyle X}$${\displaystyle f(p)=X\to p}$${\displaystyle X\to p\to 2=f^{p}(1)}$

Применяя это с помощью , затем и${\displaystyle X=a\to b}$${\displaystyle f(p)=a[p+2]b}$${\displaystyle a\to b\to p\to 2=a[a\to b\to (p-1)\to 2+2]b=f^{p}(1)}$

Так, например ,.${\displaystyle 10\to 6\to 3\to 2=10[10[1000002]6+2]6}$

Двигаемся дальше:

• ${\displaystyle a\to b\to 2\to 3}$
  ${\displaystyle =a\to b\to 2\to (2+1)}$
  ${\displaystyle =a\to b\to (a\to b)\to 2}$
  ${\displaystyle =a\to b\to a^{b}\to 2}$
  ${\displaystyle =f^{a^{b}}(1)}$

Снова мы можем обобщить. Когда мы пишем, у нас есть , то есть . В приведенном выше случае, и поэтому${\displaystyle g_{q}(p)=X\to p\to q}$${\displaystyle X\to p\to q+1=g_{q}^{p}(1)}$${\displaystyle g_{q+1}(p)=g_{q}^{p}(1)}$${\displaystyle g_{2}(p)=a\to b\to p\to 2=f^{p}(1)}$${\displaystyle g_{3}(p)=g_{2}^{p}(1)}$${\displaystyle a\to b\to 2\to 3=g_{3}(2)=g_{2}^{2}(1)=g_{2}(g_{2}(1))=f^{f(1)}(1)=f^{a^{b}}(1)}$

Функция Аккермана

Функция Аккермана может быть выражена с помощью обозначения стрелок Конвея:

${\displaystyle A(m,n)=2\to (m-2)\to (n+3)-3}$для (поскольку в гипероперации )${\displaystyle m>2}$${\displaystyle A(m,n)=2[m](n+3)-3}$

следовательно

${\displaystyle 2\to m\to n=A(m+2,n-3)+3}$ за ${\displaystyle n>2}$

( и будет соответствовать и , которые логически можно было бы добавить).${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle A(m,-2)=-1}$${\displaystyle A(m,-1)=1}$

Число Грэма

Само число Грэма не может быть кратко выражено в обозначении цепной стрелки Конвея, но оно ограничено следующим:${\displaystyle G}$

${\displaystyle 3\rightarrow 3\rightarrow 64\rightarrow 2<G<3\rightarrow 3\rightarrow 65\rightarrow 2}$

Доказательство: сначала мы определяем промежуточную функцию , которую можно использовать для определения числа Грэма как . (Верхний индекс 64 обозначает функциональную мощность .)${\displaystyle f(n)=3\rightarrow 3\rightarrow n={\begin{matrix}3\underbrace {\uparrow \uparrow \cdots \uparrow } 3\\{\text{n arrows}}\end{matrix}}}$${\displaystyle G=f^{64}(4)}$

Применяя правило 2 и правило 4 в обратном порядке, мы упрощаем:

${\displaystyle f^{64}(1)}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 1))\cdots ))}$(с 64 -х)${\displaystyle 3\rightarrow 3}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3)\rightarrow 1)\cdots )\rightarrow 1)\rightarrow 1}$

${\displaystyle =3\rightarrow 3\rightarrow 64\rightarrow 2;}$

${\displaystyle f^{64}(4)=G;}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 4))\cdots ))}$(с 64 -х)${\displaystyle 3\rightarrow 3}$

${\displaystyle f^{64}(27)}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27))\cdots ))}$(с 64 -х)${\displaystyle 3\rightarrow 3}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (\cdots (3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow (3\rightarrow 3)))\cdots ))}$(с 65 -х)${\displaystyle 3\rightarrow 3}$

${\displaystyle =3\rightarrow 3\rightarrow 65\rightarrow 2}$ (вычисления, как указано выше).

${\displaystyle =f^{65}(1)}$

Так как F является строго возрастает ,

${\displaystyle f^{64}(1)<f^{64}(4)<f^{64}(27)}$

что и есть данное неравенство.

С помощью связанных стрелок очень легко указать число, намного большее, чем , например ,.${\displaystyle G}$${\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3}$

${\displaystyle 3\rightarrow 3\rightarrow 3\rightarrow 3}$

${\displaystyle =3\rightarrow 3\rightarrow (3\rightarrow 3\rightarrow 27\rightarrow 2)\rightarrow 2\,}$

${\displaystyle =f^{3\rightarrow 3\rightarrow 27\rightarrow 2}(1)}$

${\displaystyle =f^{f^{27}(1)}(1)}$

что намного больше, чем число Грэма, потому что это число намного больше, чем .${\displaystyle 3\rightarrow 3\rightarrow 27\rightarrow 2}$ ${\displaystyle =f^{27}(1)}$${\displaystyle 65}$

Функция CG

Конвей и Гай создали простую функцию с одним аргументом, которая диагонализируется по всей нотации, определенная как:

${\displaystyle cg(n)=\underbrace {n\rightarrow n\rightarrow n\rightarrow \dots \rightarrow n\rightarrow n\rightarrow n} _{n}}$

это означает, что последовательность:

${\displaystyle cg(1)=1}$

${\displaystyle cg(2)=2\to 2=2^{2}=4}$

${\displaystyle cg(3)=3\to 3\to 3=3\uparrow \uparrow \uparrow 3}$

${\displaystyle cg(4)=4\to 4\to 4\to 4}$

${\displaystyle cg(5)=5\to 5\to 5\to 5\to 5}$

...

Эта функция, как и следовало ожидать, необычайно быстро растет.

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

Питер Херфорд, веб-разработчик и статистик, определил расширение этой нотации:

${\displaystyle a\rightarrow _{b}c=\underbrace {a\rightarrow _{b-1}a\rightarrow _{b-1}a\rightarrow _{b-1}\dots \rightarrow _{b-1}a\rightarrow _{b-1}a\rightarrow _{b-1}a} _{c{\text{ arrows}}}}$

${\displaystyle a\rightarrow _{1}b=a\rightarrow b}$

В остальном все обычные правила не меняются.

${\displaystyle a\rightarrow _{2}(a-1)}$уже равна вышеупомянутой , и функция растет намного быстрее, чем функция Конвея и Гая .${\displaystyle cg(a)}$${\displaystyle f(n)=n\rightarrow _{n}n}$${\displaystyle cg(n)}$

Обратите внимание, что выражения вроде недопустимы, если и являются разными числами; одна цепочка должна иметь только один тип стрелки вправо.${\displaystyle a\rightarrow _{b}c\rightarrow _{d}e}$${\displaystyle b}$${\displaystyle d}$

Однако, если мы немного изменим это так, чтобы:

${\displaystyle a\rightarrow _{b}c\rightarrow _{d}e=a\rightarrow _{b}\underbrace {c\rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}\dots \rightarrow _{d-1}c\rightarrow _{d-1}c\rightarrow _{d-1}c} _{e{\text{ arrows}}}}$

тогда не только становится законным, но и обозначение в целом становится намного сильнее. ^[2]${\displaystyle a\rightarrow _{b}c\rightarrow _{d}e}$

Смотрите также

• Обозначения Штейнгауза – Мозера
• Систематическое создание все быстрее увеличивающихся последовательностей

Рекомендации

внешняя ссылка

• Фактоиды> большие числа
• Большие числа Роберта Мунафо
• Книга чисел Дж. Х. Конвея и Р. К. Гая