Обозначение стрелок Конвея, созданный математиком Джон Хортон Конвей, является средством выражения некоторых чрезвычайно большие числа.[1] Это просто конечная последовательность положительные целые числа разделены стрелками вправо, например
.
Как и большинство комбинаторный обозначений, определение рекурсивный. В этом случае нотация в конечном итоге превращается в крайнее левое число, возведенное в некоторую (обычно огромную) целую степень.
Определение и обзор
«Цепь Конвея» определяется следующим образом:
- Любое положительное целое число - это цепочка длины
. - Цепочка длины п, за которым следует стрелка вправо → и положительное целое число, вместе образуют цепочку длины
.
Любая цепочка представляет собой целое число в соответствии с пятью (технически четырьмя) правилами ниже. Две цепи называются эквивалентными, если они представляют одно и то же целое число.
Если
,
, и
положительные целые числа, и
является подсистемой, то:
- Пустая цепочка (или цепочка длины 0) равна
, а цепочка
представляет собой число
.
эквивалентно
.
эквивалентно
. (видеть Обозначение стрелки Кнута вверх )
эквивалентно
(с
копии
,
копии
, и
пары скобок; подает заявку на
> 0).- Потому что
эквивалентно
, (По правилу 2), а также
=
, (По правилу 3) можно определить
в равной ![p ^ {q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75ead10b72d59f44fbc277dbd66b6797dcbbf634)
Обратите внимание, что четвертое правило можно заменить повторным применением двух правил, чтобы избежать эллипсы:
- 4а.
эквивалентно ![Икс](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
- 4b.
эквивалентно ![{ Displaystyle Икс к (Икс к р к (q + 1)) к q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c817ff0cfbadb8f7d73364d65ef153699dc23b67)
Характеристики
- Цепь оценивает абсолютную степень своего первого числа
- Следовательно,
равно ![1](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
эквивалентно ![Икс](https://wikimedia.org/api/rest_v1/media/math/render/svg/68baa052181f707c662844a465bfeeb135e82bab)
равно ![4](https://wikimedia.org/api/rest_v1/media/math/render/svg/295b4bf1de7cd3500e740e0f4f0635db22d87b42)
эквивалентно
(не путать с
)
Интерпретация
Осторожно обращаться с цепочкой стрел в целом. Цепочки стрелок не описывают повторное применение бинарного оператора. В то время как цепочки других инфиксных символов (например, 3 + 4 + 5 + 6 + 7) часто можно рассматривать фрагментами (например, (3 + 4) + 5 + (6 + 7)) без изменения значения (см. ассоциативность ), или, по крайней мере, можно оценивать шаг за шагом в установленном порядке, например 34567 справа налево, это не так с цепями стрел Конвея.
Например:
![2 rightarrow3 rightarrow2 = 2 uparrow uparrow3 = 2 ^ {2 ^ 2} = 16](https://wikimedia.org/api/rest_v1/media/math/render/svg/3aa8384f1bb4f7fc9ca91f09ebc096769e6e7ed8)
![2 rightarrow left (3 rightarrow 2 right) = 2 ^ {{(3 ^ {2})}} = 2 ^ {{3 ^ {2}}} = 512](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ae9db644dcfcbbd4b2d75055af9074e97c06af4)
![left (2 rightarrow 3 right) rightarrow 2 = left (2 ^ {3} right) ^ {2} = 64](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c875876d5316a1ecfac4e18c28d5058dae4524f)
Четвертое правило - это ядро: цепочка из 4 или более элементов, оканчивающихся на 2 или больше, становится цепочкой такой же длины с (обычно значительно) увеличенным предпоследним элементом. Но это окончательный элемент уменьшается, что в конечном итоге позволяет второму правилу сократить цепочку. После, перефразируя Knuth, «подробнее», цепочка сокращается до трех элементов, а третье правило завершает рекурсию.
Примеры
Примеры быстро усложняются. Вот несколько небольших примеров:
![п](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
(По правилу 1)
![{ displaystyle p to q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fccb3827df1efe7930f9d1febd15d2359971b93)
(По правилу 5)- Таким образом,
![{ displaystyle 3 to 4 = 3 ^ {4} = 81}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fa08e81c568ef11592c24fcbf47b96dc125339b)
![{ displaystyle 4 to 3 to 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88618a1c84b39128f3822985c6806499bb6b6452)
(По правилу 3)![{ displaystyle = 4 uparrow (4 uparrow 4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8304e91f4eb7d9f1e6404c26f57f7b95e62b2c8d)
![{ displaystyle = 4 uparrow 256}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99bb3852d9cdaf296fb57ee687ae67656f43912b)
![{ displaystyle = 4 ^ {256}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96a9414c3f9c6114bb2431e458fdb10edb73ff3f)
![{ 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94716d4e7cbeeaa588f4e71f603fb4ad3c74a1a9)
![{ displaystyle приблизительно 1,34 * 10 ^ {154}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b3b0feb5ef130fb1cd17971a4294b8202147f0f)
![{ displaystyle 2 to 2 to a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c316bdf912fa665d2656211e0aeb6b8545849144)
(По правилу 3)
(видеть Обозначение стрелки Кнута вверх )
![{ displaystyle 2 to 4 to 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60e529d982d572b6514402bf47534cd59a47b035)
(По правилу 3)![{ displaystyle = 2 uparrow uparrow (2 uparrow uparrow (2 uparrow uparrow 2))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79f7b1eaf598090c4c021f74ad3d16b930517965)
![{ displaystyle = 2 uparrow uparrow (2 uparrow uparrow 4)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f51fc90e34868974a160967a88524a8969995cc3)
![{ displaystyle = 2 uparrow uparrow (2 uparrow (2 uparrow (2 uparrow 2)))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cd58c398f7064b011fa05da88aea74de47ada26)
![{ displaystyle = 2 uparrow uparrow (2 uparrow (2 uparrow 4))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9dc7535f38bd59ebece3c29e99fc4e20fd442421)
![{ displaystyle = 2 uparrow uparrow (2 uparrow 16)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4109f93b6eeab5cfeef14be92fda09e2ede4999a)
![{ displaystyle = 2 uparrow uparrow (65536)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a5d1b4af4007ef724a02e87afd101560677222e)
(видеть тетрация )
![{ Displaystyle 2 до 3 до 2 до 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d5069c4a054afdcc20e8dcd9e522b339f38b377)
(По правилу 4)
(По правилу 5)
(По правилу 2)
(По правилу 3)- = намного больше, чем предыдущий номер
![{ displaystyle 3 to 2 to 2 to 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb22674ce8d465ebdd0d3a0fee99a77b08c8e323)
(По правилу 4)
(По правилу 5)
(По правилу 2)
(По правилу 3)- = намного, намного больше, чем предыдущий номер
Систематические примеры
Самыми простыми случаями с четырьмя членами (не содержащими целых чисел меньше 2) являются:
![а к б к 2 к 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/503a9391fe1e16897b44d29a4b904d74d0704ea4)
![= а к b к 2 к (1 + 1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/468296bcf60aba1ed32ad5f29737789540cdf279)
![= a to b to (a to b) to 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/afa2d5a7191f2b9418c860b1346b6817d3d1ff67)
![= от a до b до a ^ {b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0094c520d14938b357886e55172363b94def2e8)
![= а [а ^ {b} +2] б](https://wikimedia.org/api/rest_v1/media/math/render/svg/5122c5c8b65604a751640ca32b6fa474637eaeec)
- (эквивалент последнего упомянутого свойства)
![а к б к 3 к 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/11156b7d320be94a196fc292b572034fe2067d12)
![= а к b к 3 к (1 + 1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bec29bc73e0eeed4b5249572e03cc8c8abcb19d)
![= a to b to (a to b to (a to b) to 1) to 1](https://wikimedia.org/api/rest_v1/media/math/render/svg/311e4bec4fa82d025ca429f4daa1a7e6824b320e)
![= от a до b to (от a до b до a ^ {b})](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebb34957cf5d0feba97bd727fd2888977e4f1f51)
![= a [a to b to 2 to 2 + 2] b](https://wikimedia.org/api/rest_v1/media/math/render/svg/53ae38786c37933b56883d852a17a2b8e4f1d222)
![а к б к 4 к 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/b562f60620783d8bfc61aad74cc5f7864fa5d247)
![= a to b to (a to b to (a to b to a ^ {b}))](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf02fe36909b537b3b67913c3d5eadb602a080d6)
![= a [a to b to 3 to 2 + 2] b](https://wikimedia.org/api/rest_v1/media/math/render/svg/41077be13272dbc2d9a89dd71889a505af53c6c1)
Здесь мы видим закономерность. Если для любой цепи
, мы позволяем
тогда
(видеть функциональные возможности ).
Применяя это с
, тогда
и ![a to b to p to 2 = a [a to b to (p-1) to 2 + 2] b = f ^ {p} (1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/8462b1d161e5a1235b8676f01d91a95614413f6c)
Так, например,
.
Двигаемся дальше:
![а к б к 2 к 3](https://wikimedia.org/api/rest_v1/media/math/render/svg/39bb65239fe28cc8f026f612900443e23b6d7680)
![= а к b к 2 к (2 + 1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/05dd09c3157020b08a8a68f93f82b94d54acfa0f)
![= a to b to (a to b) to 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/1fa10b0ad746a86e3d39fa8681f2b909ab94f1ff)
![= a to b to a ^ {b} to 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/2140e0b51ed47462875b53c1b789b813b679ca3f)
![= f ^ {{a ^ {b}}} (1)](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7705e04fc1f6878aef5642cc6ef908317f6280b)
Снова мы можем обобщить. Когда мы пишем
у нас есть
, то есть,
. В приведенном выше случае
и
, так ![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)](https://wikimedia.org/api/rest_v1/media/math/render/svg/cd22bef2cad35e8a4b260bc4c63c71f60c3e9acb)
Функция Аккермана
В Функция Аккермана может быть выражено с помощью обозначения стрелок Конвея:
за
(С
в гипероперация )
следовательно
за ![п> 2](https://wikimedia.org/api/rest_v1/media/math/render/svg/44e71ac55b9fbf1e9f341b946cda63d61d3ef2cd)
- (
и
будет соответствовать
и
, что логично было бы добавить).
Число Грэма
Число Грэма
сам по себе не может быть кратко выражен в обозначении цепной стрелки Конвея, но он ограничен следующим:
![{ Displaystyle 3 rightarrow 3 rightarrow 64 rightarrow 2 <G <3 rightarrow 3 rightarrow 65 rightarrow 2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a5cf29133e49988d93d0c5cb21fdbdba1913594)
Доказательство: Сначала определим промежуточную функцию
, который можно использовать для определения числа Грэма как
. (Верхний индекс 64 означает функциональная сила.)
Применяя правило 2 и правило 4 в обратном порядке, мы упрощаем:
![{ displaystyle f ^ {64} (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d9d62db12fe7163da673a8316a2718e2168029e)
(с 64
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8db08ceac0acb82912e2ba8eb714a40ec09d9bd)
![{ Displaystyle = 3 rightarrow 3 rightarrow 64 rightarrow 2;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85cf8da9c12e843c3a4451aea27f09a9b642c78b)
![{ displaystyle left. { begin {matrix} = & 3 underbrace { uparrow uparrow cdots cdots cdots cdot uparrow} 3 & 3 underbrace { uparrow uparrow cdots cdots cdots uparrow} 3 & underbrace { qquad ; ; vdots qquad ; ;} & 3 underbrace { uparrow uparrow cdots cdot uparrow} 3 & 3 uparrow 3 end {matrix}} right } { text {64 слоя}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/53d5c0fde631fcf017a7f5b2dd81cd712101110f)
![{ Displaystyle f ^ {64} (4) = G;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61f9d75494abb30ce3bfb756e17f49ba083e2814)
(с 64
s)
![{ displaystyle left. { begin {matrix} = & 3 underbrace { uparrow uparrow cdots cdots cdots cdot uparrow} 3 & 3 underbrace { uparrow uparrow cdots cdots cdots uparrow} 3 & underbrace { qquad ; ; vdots qquad ; ;} & 3 underbrace { uparrow uparrow cdots cdot uparrow} 3 & 3 uparrow uparrow uparrow uparrow 3 end {matrix}} right } { text {64 слоя}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93464984c9d1a5e5396dfe45509a9c7881cc32a8)
![{ displaystyle f ^ {64} (27)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e02319843b8d29e0265eddad8b4da66e873b8eb)
(с 64
s)
(с 65
s)
(вычисления, как указано выше).![{ displaystyle = f ^ {65} (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/711ec7cea52950fa60c83384287e676a2d6dac34)
![{ displaystyle left. { begin {matrix} = & 3 underbrace { uparrow uparrow cdots cdots cdots cdot uparrow} 3 & 3 underbrace { uparrow uparrow cdots cdots cdots uparrow} 3 & underbrace { qquad ; ; vdots qquad ; ;} & 3 underbrace { uparrow uparrow cdots cdot uparrow} 3 & 3 uparrow 3 end {matrix}} right } { text {65 слоев}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/21a08110ba35326f58896a78ca19660b1e37acc4)
С ж является строго возрастающий,
![{ displaystyle f ^ {64} (1) <f ^ {64} (4) <f ^ {64} (27)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/121b887e5c368d4cb5f9741906b9d3f3fd5a4113)
что и есть данное неравенство.
С помощью связанных стрелок очень легко указать число, намного большее, чем
, Например,
.
![{ Displaystyle 3 rightarrow 3 rightarrow 3 rightarrow 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba8017fe2262ac3de792e70e4e53a6f408b367de)
![{ Displaystyle = 3 rightarrow 3 rightarrow (3 rightarrow 3 rightarrow 27 rightarrow 2) rightarrow 2 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7fdda5bf60a2ca2f413d06917d0e8bd8638c1ded)
![{ Displaystyle = е ^ {3 rightarrow 3 rightarrow 27 rightarrow 2} (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/588576db19618f0e6bc04aa1a8e36a4ed815a0a1)
![{ Displaystyle = е ^ {е ^ {27} (1)} (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b0b485c557b9cdc4c4ff31399c76a0bd4c85c71)
![{ displaystyle left. { begin {matrix} = & 3 underbrace { uparrow uparrow cdots cdots cdots cdot cdot uparrow} 3 & 3 underbrace { uparrow uparrow cdots cdots cdots cdot uparrow} 3 & 3 underbrace { uparrow uparrow cdots cdots cdots uparrow} 3 & underbrace { qquad ; ; vdots qquad ; ;} & 3 underbrace { uparrow uparrow cdots cdot uparrow} 3 & 3 uparrow 3 end {matrix}} right } left. { Begin {matrix} 3 underbrace { uparrow uparrow cdots cdots cdots cdot uparrow} 3 3 underbrace { uparrow uparrow cdots cdots cdots uparrow} 3 underbrace { qquad ; ; vdots qquad ; ; } 3 underbrace { uparrow uparrow cdots cdot uparrow} 3 3 uparrow 3 end {matrix}} right } 3 uparrow 3 = { text {27 слоев}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9a73f48e8f8f8d3337799196d5d4f68727330a8)
что намного больше, чем число Грэма, потому что число
![{ displaystyle = f ^ {27} (1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80193becc07359c0ca9ba05f2622d017847a6bec)
намного больше, чем
![{ displaystyle 65}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b29381eecdc70c14924bb25cdd343405f146ff4b)
.
Функция CG
Конвей и Гай создали простую функцию с одним аргументом, которая диагонализируется по всей нотации, определенная как:
![{ displaystyle cg (n) = underbrace {n rightarrow n rightarrow n rightarrow dots rightarrow n rightarrow n rightarrow n} _ {n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b767c26467944754e2b1f89a3ab13bfac0c9bd3a)
это означает, что последовательность:
![{ displaystyle cg (1) = 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a74ab6fe3b328197885cf5e54ce936eb52fc3a1c)
![{ displaystyle cg (2) = 2 to 2 = 2 ^ {2} = 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5bb0846d24af538b363a5c11c5826edde126e63)
![{ displaystyle cg (3) = 3 to 3 to 3 = 3 uparrow uparrow uparrow 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8aad233ce6dfe9465866704b5b9e909120c1d160)
![{ Displaystyle cg (4) = от 4 до 4 до 4 до 4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf5d170ae87bb8d5414205cdc1c481febe2b1ce9)
![{ displaystyle cg (5) = 5 до 5 до 5 до 5 до 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ae179a88b85029538b952effc6886b549320818)
...
Эта функция, как и следовало ожидать, необычайно быстро растет.
Расширение Питера Херфорда
Питер Херфорд, веб-разработчик и статистик, определил расширение этой нотации:
![{ 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 {стрелки}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/da5a7075d93adc33b680f192ba1b6eec6a979a35)
![{ displaystyle a rightarrow _ {1} b = a rightarrow b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6b9a3fc2f414c6d87049accc4bdec8477f8a2cc1)
В остальном все обычные правила не меняются.
уже равна вышеупомянутому
, а функция
намного быстрее, чем у Конвея и Гая
.
Обратите внимание, что такие выражения, как
являются незаконными, если
и
бывают разные числа; одна цепочка должна иметь только один тип стрелки вправо.
Однако, если мы немного изменим это так, чтобы:
![{ 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 {стрелки}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042c21ad33a243f7cee75b9e0f88d07f1101d6ed)
тогда не только
становятся легальными, но обозначение в целом становится намного сильнее.[2]
Смотрите также
Рекомендации
внешняя ссылка
|
---|
Начальный | |
---|
Обратный для левого аргумента | |
---|
Обратный для правильного аргумента | |
---|
Статьи по Теме | |
---|
|
---|
Примеры в порядковый номер | |
---|
Выражение методы | |
---|
Связанный статьи (Алфавитный порядок)
| |
---|
|