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

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

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

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

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

• Любое положительное целое число - это цепочка длины ${ displaystyle 1}$.
• Цепочка длины п, за которым следует стрелка вправо → и положительное целое число, вместе образуют цепочку длины ${ 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)}$ эквивалентно ${ Displaystyle Икс к (Икс к ( cdots (X к (X) к q) cdots) к q) к q}$
   (с ${ displaystyle p}$ копии ${ displaystyle X}$, ${ displaystyle p-1}$ копии ${ displaystyle q}$, и ${ displaystyle p-1}$ пары скобок; подает заявку на ${ displaystyle q}$ > 0).
5. Потому что ${ displaystyle p rightarrow q rightarrow 1}$ эквивалентно ${ displaystyle p to q}$, (По правилу 2), а также ${ displaystyle p uparrow q}$ = ${ displaystyle p ^ {q}}$, (По правилу 3) можно определить ${ displaystyle p to q}$ в равной ${ displaystyle p ^ {q}}$

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

4а. ${ Displaystyle Х к 1 к (д + 1)}$ эквивалентно ${ displaystyle X}$

4b. ${ Displaystyle X к (п + 1) к (д + 1)}$ эквивалентно ${ Displaystyle Икс к (Икс к р к (q + 1)) к 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⁴⁵⁶⁷ справа налево, это не так с цепями стрел Конвея.

Например:

• ${ 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 или больше, становится цепочкой такой же длины с (обычно значительно) увеличенным предпоследним элементом. Но это окончательный элемент уменьшается, что в конечном итоге позволяет второму правилу сократить цепочку. После, перефразируя Knuth, «подробнее», цепочка сокращается до трех элементов, а третье правило завершает рекурсию.

Примеры

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

${ 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 приблизительно 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 до 3 до 2 до 2}$

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

${ Displaystyle = 2 до 3 до 8 до 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 до 2 до 9 до 1}$ (По правилу 5)

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

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

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

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

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

• ${ Displaystyle от а до б до 2 до 2}$
  ${ Displaystyle = а к б к 2 к (1 + 1)}$
  ${ Displaystyle = а к b к (от а к b) к 1}$
  ${ Displaystyle = от а к b к а ^ {b}}$
  ${ displaystyle = a [a ^ {b} +2] b}$

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

• ${ Displaystyle от а до б до 3 до 2}$
  ${ Displaystyle = а к б к 3 к (1 + 1)}$
  ${ Displaystyle = а к б к (а к б к (а к b) к 1) к 1}$
  ${ Displaystyle = а к б к (а к б к а ^ {b})}$
  ${ Displaystyle = а [а к b к 2 к 2 + 2] b}$
• ${ Displaystyle от а до б до 4 до 2}$
  ${ displaystyle = a to b to (a to b to (a to b to a ^ {b}))}$
  ${ Displaystyle = а [от до b до 3 до 2 + 2] b}$

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

Применяя это с ${ Displaystyle X = от до b}$, тогда ${ displaystyle f (p) = a [p + 2] b}$ и ${ Displaystyle а к б к р к 2 = а [а к б к (р-1) к 2 + 2] б = е ^ {р} (1)}$

Так, например, ${ Displaystyle 10 до 6 до 3 до 2 = 10 [10 [1000002] 6 + 2] 6}$.

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

• ${ Displaystyle от а до б до 2 до 3}$
  ${ Displaystyle = а к б к 2 к (2 + 1)}$
  ${ Displaystyle = а к b к (от а к b) к 2}$
  ${ Displaystyle = от а к b к а ^ {b} к 2}$
  ${ displaystyle = f ^ {a ^ {b}} (1)}$

Снова мы можем обобщить. Когда мы пишем ${ displaystyle g_ {q} (p) = X to p to q}$ у нас есть ${ Displaystyle X к p к 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 А (м, п) = 2 к (м-2) к (п + 3) -3}$ за ${ displaystyle m> 2}$ (С ${ Displaystyle А (м, п) = 2 [м] (п + 3) -3}$ в гипероперация)

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

${ Displaystyle 2 к м к п = А (м + 2, п-3) +3}$ за ${ displaystyle n> 2}$

(${ displaystyle n = 1}$ и ${ displaystyle n = 2}$ будет соответствовать ${ Displaystyle А (м, -2) = - 1}$ и ${ Displaystyle А (м, -1) = 1}$, что логично было бы добавить).

Число Грэма

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

${ Displaystyle 3 rightarrow 3 rightarrow 64 rightarrow 2$

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

Применяя правило 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}$s)

${ 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}$s)

${ 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}$s)

${ 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}$s)

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

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

С ж является строго возрастающий,

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

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

С помощью связанных стрелок очень легко указать число, намного большее, чем ${ 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 = е ^ {3 rightarrow 3 rightarrow 27 rightarrow 2} (1)}$

${ Displaystyle = е ^ {е ^ {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 до 4 до 4 до 4}$

${ displaystyle cg (5) = 5 до 5 до 5 до 5 до 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 {стрелки}}}}$

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

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

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

Обратите внимание, что такие выражения, как ${ 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 {стрелки}}}}$

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

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

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

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

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

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