игра Гидра

В математике, особенно в теории графов и теории чисел , игра гидры для одного игрока — это итеративная математическая игра , в которую играют на математическом дереве, называемом гидрой , где обычно цель состоит в том, чтобы отрезать гидре «головы», в то время как гидра одновременно расширяется. сам. Игры «Гидра» можно использовать для генерации больших чисел или бесконечных порядковых номеров или для доказательства силы определенных математических теорий. ^[1]

В отличие от их комбинаторных аналогов, таких как TREE и SCG , для вычисления этих быстрорастущих значений функций не требуется никакого поиска — нужно просто продолжать применять правило преобразования к дереву до тех пор, пока игра не скажет остановиться.

Введение

Простую игру гидры можно определить следующим образом:

Гидра — это конечное корневое дерево, которое представляет собой связный граф без циклов и с определенным узлом, обозначенным как корень. $R$ дерева. В корневом дереве каждый узел имеет одного родителя (за исключением корня, у которого нет родителя) и набора дочерних элементов, в отличие от некорневого дерева, где нет отношений родитель-потомок, и мы просто ссылаемся на ребра. между узлами.
Игрок выбирает листовой узел $x$ из дерева и натурального числа $n$ во время каждого хода. Листовой узел может быть определен как узел без дочерних элементов или узел степени 1, который не является $R$ .
Удалить листовой узел $x$ . Позволять $a$ быть $x$ родитель. Если $a=R$ , вернитесь к этапу 2. В противном случае, если $a\neq R$ , позволять $b$ быть родителем $a$ . Затем создайте $n$ листовые узлы как дочерние элементы $b$ так, чтобы новые узлы появлялись после любых существующих дочерних узлов $b$ во время обхода после заказа (визуально эти новые узлы появятся справа от любых существующих дочерних узлов). Затем вернитесь к этапу 2.

Хотя гидра может вырасти в неограниченном количестве $n$ листьев на каждом ходу, игра в конечном итоге завершится за конечное число шагов: если $d$ - наибольшее расстояние между корнем и листом, а $w$ количество листьев на этом расстоянии, индукция по $d$ можно использовать, чтобы продемонстрировать, что игрок всегда убьет гидру. Если $d=1$ , удаление листьев никогда не приведет к росту гидры, поэтому игрок выигрывает после $w$ поворачивается. Для общего $d$ , мы рассматриваем два вида ходов: те, которые задействуют лист на расстоянии меньшем $d$ от корня, и те, которые затрагивают лист на расстоянии ровно $d$ . Поскольку ходы первого рода также идентичны ходам в игре с глубиной $d-1$ , гипотеза индукции говорит нам, что после конечного числа таких ходов у игрока не будет другого выбора, кроме как выбрать лист на глубине $d$ . Никакое перемещение не приводит к появлению новых узлов на этой глубине, поэтому весь этот процесс может повторяться только до $w$ раз, после чего листьев на глубине уже нет $d$ и игра теперь имеет глубину (максимум) $d-1$ . Снова прибегая к гипотезе индукции, мы обнаруживаем, что игрок в конечном итоге должен выиграть в целом.

Хотя это показывает, что игрок в конечном итоге выиграет, это может занять очень много времени. В качестве примера рассмотрим следующий алгоритм. Выберите самый правый лист (т. е. самый новый лист, который будет находиться на уровне, ближайшем к корню) и установите $n=1$ первый раз, $2$ второй раз и так далее, всегда увеличивая $n$ по одному. Если у гидры есть один $y$ -длина ветви, то для $y=1$ , гидру убивают за один прием, а за три приема, если $y=2$ . Для этого необходимо сделать 11 шагов. $y=3$ . Для этого необходимо 1114111 шагов. $y=4$ . ^[2] $y=5$ было рассчитано точно. ^[3] Позволять $F(x)=2^{x}\cdot (x+2)-1$ и $F^{n}(x)$ быть $F$ вложено n раз. Затем $HYDRA(5)=2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=2\cdot F^{22539988369408}(22539988369408)+1$ .

Общее решение

Общее решение игры с гидрой следующее: ^[4]

Позволять $F_{i}(x)$ обозначают количество шагов, необходимых для уменьшения головки глубины n, когда все головки, расположенные ближе к корням, являются единственными (нет дальнейших «правильных» ветвей).

Затем $F_{i+1}(x)=F_{i}^{x}(x+1)$ и $F_{1}(x)=2\cdot (x+1)-1=2x+1$ .

Ответ на $hydra(n)$ является: $F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))$

Скорость роста этой функции выше, чем у стандартной быстрорастущей иерархии , так как $F_{i}(x)$ растет со скоростью быстрорастущей иерархии , и решением является n-е вложение $F_{i}(x)$ .

Гидры Кирби – Пэрис и Бухгольца

Гидра Кирби-Пэрис определяется путем изменения четвертого правила гидры, определенного выше.

4 _КП : Предположим $b$ является родителем $a$ если $a\neq R$ . Прикреплять $n$ копии поддерева с корнем $a$ к $b$ справа от всех остальных узлов, подключенных к $b$ . Вернитесь к этапу 2. ^[5]

Вместо добавления только новых листьев это правило добавляет дубликаты всего поддерева. На этот раз все остальное останется прежним. $y=1$ требует $1$ повернуть, $y=2$ требует $3$ шаги, $y=3$ требует $37$ шаги и $y=4$ требует больше шагов, чем число Грэма . Скорость роста этой функции огромна и равна $f_{\varepsilon _{0}}(n)$ в быстрорастущей иерархии.

Это не самая мощная гидра. Гидра Бухгольца — более сильная гидра. ^[6] Это влечет за собой помеченное дерево. Корень имеет уникальную метку (назовем ее $R$ ), и каждый другой узел имеет метку, которая является либо неотрицательным целым числом, либо $\omega$ . ^[7]

Гидра — это меченое дерево с конечными корнями. Корень должен быть помечен $R$ . Пометьте все узлы, прилегающие к корню $0$ (важно, чтобы он всегда заканчивался) и любой другой узел с неотрицательным целым числом или $\omega$ .
Выберите листовой узел $x$ и натуральное число $n$ на каждом этапе.
Удалить лист $x$ . Позволять $a$ быть $x$ родитель. Больше ничего не произойдет, если $a=R$ . Вернитесь к этапу 2.
Если этикетка $x$ является $0$ , Предполагать $b$ является родителем $a$ . Прикреплять $n$ копии поддерева с корнем $a$ к $b$ справа от всех остальных узлов, подключенных к $b$ . Вернитесь к этапу 2.
Если метка x $\omega$ , замените его на $n+1$ . Вернитесь к этапу 2.
Если этикетка $x$ является положительным целым числом $u$ . спуститься по дереву в поисках узла $c$ с этикеткой $<u$ . Такой узел существует, потому что все узлы, соседние с корнем, помечены $0$ . Скопируйте поддерево с корнем $c$ . Заменять $x$ с этим поддеревом. Однако переименуйте $x$ (корень копии поддерева) с $u-1$ . Вызовите эквивалент $x$ в скопированном поддереве $x'$ (так $x$ это $x'$ как $c$ это $x$ ) и переименуйте $x'$ это 0. Вернитесь на этап 2. ^[8]

Удивительно, но, хотя гидра может вырасти чрезвычайно выше, эта последовательность всегда заканчивается. ^[9]

Подробнее о КП Гидрас

Для гидр Кирби-Пэрис правила просты: начните с гидры, которая представляет собой неупорядоченное немаркированное корневое дерево. $T$ . На каждом этапе игрок выбирает листовой узел. $c$ нарезать и неотрицательное целое число $n$ . Если $c$ является дочерним элементом корня $r$ , он удаляется из дерева, и в этот ход больше ничего не происходит. В противном случае, пусть $p$ быть $c$ родитель, и $g$ быть $p$ родитель. Удалять $c$ из дерева, затем добавьте $n$ копии модифицированных $p$ как дети, чтобы $g$ . Игра заканчивается, когда гидра сокращается до одного узла.

Чтобы получить быстрорастущую функцию, можно зафиксировать $n$ , сказать, $n=1$ на первом этапе, затем $n=2$ , $n=3$ и так далее, а также определите простое правило, где разрезать, скажем, всегда выбирая самый правый лист. Затем, $\operatorname {Hydra} (k)$ — это количество шагов, необходимое для завершения игры, начиная с пути длиной $k$ , то есть линейный стек $k+1$ узлы. $\operatorname {Hydra} (k)$ в конечном итоге доминирует над всеми рекурсивными функциями, которые доказуемо полны в арифметике Пеано, и сами являются доказуемо полными в $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ . ^[10]

Альтернативно это можно выразить с помощью строк скобок:

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

Например, с $n=3$ , $(()(()\mathbf {()} ))\implies (()(())(())(())(()))$ . Далее идет список значений $\operatorname {Hydra} (k)$ :

$\operatorname {Hydra} (0)=0$
$\operatorname {Hydra} (1)=1$
$\operatorname {Hydra} (2)=3$
$\operatorname {Hydra} (3)=37$
$\operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}$
$\operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)$
$\operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)$

Подробнее о гидрах Бухгольца

Игра «Гидра Бухгольца» — это игра «Гидра» в математической логике, однопользовательская игра, основанная на идее отрубания частей математического дерева. Игру «Гидра» можно использовать для создания быстро растущей функции. $BH(n)$ , которая в конечном итоге доминирует над всеми доказуемо тотально рекурсивными функциями. Это расширение гидры Кирби-Пэрис. Для получения быстрорастущей функции мы используем то же самое, что и гидры Кирби-Пэрис, но поскольку гидры Бухгольца растут не только в ширину, но и в высоту, $BH(n)$ имеет гораздо больший темп роста $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)$ :

$BH(1)=0$
$BH(2)=1$
$BH(3)<f_{\varepsilon _{0}}(3)$

Эту систему также можно использовать для создания порядковой записи для бесконечных порядковых чисел, например $\psi _{0}(\Omega _{\omega })=+0(\omega )$ .

См. также

Теорема Гудштейна

Ссылки

^ Кирби, Лори; Пэрис, Джефф. «Доступные результаты независимости для арифметики Пеано» (PDF) . Кафедра прикладной логики . Проверено 4 сентября 2021 г.
^ https://www.reddit.com/r/BradyHaran/comments/1c6z1t4/the_hydra_game_numberphile/
^ https://cal.vin/p/hydra5
^ https://li.cal.vin/p/the-hydra-game-solved
^ «Гидры» . agnijomaths.com . Проверено 05 сентября 2021 г.
^ Хамано, Масахиро; Окада, Мицухиро (1995). «Связь между редукцией доказательств Генцена, игрой Кирби-Пэрис) с гидрой и игрой с гидрой Бухгольца (предварительный отчет) *» (PDF) . Научно-исследовательский институт математических наук Киотского университета . Проверено 4 сентября 2021 г.
^ Кетонен, Юсси; Соловей, Роберт (1981). «Быстрорастущие функции Рамсея» . Анналы математики . 113 (2): 267–314. дои : 10.2307/2006985 . ISSN 0003-486X . JSTOR 2006985 .
^ Бухгольц, Вильфрид (27 ноября 1984 г.). «Результат независимости для Π11 - CA + BI» (PDF) . Мюнхенский университет Людвига-Максимилиана . Проверено 4 сентября 2021 г.
^ Хамано, Масахиро; Окада, Мицухиро (1 марта 1998 г.). «Прямое доказательство независимости игры Бухгольца «Гидра» на конечных помеченных деревьях» . Архив математической логики . 37 (2): 67–89. дои : 10.1007/s001530050084 . ISSN 1432-0665 . S2CID 40113368 .
^ Карлуччи, Лоренцо (7 мая 2003 г.). «Новое теоретико-доказательное доказательство независимости теоремы Кирби – Пэрис о гидре». Теоретическая информатика . 300 (1–3): 365–378. дои : 10.1016/S0304-3975(02)00332-8 . ISSN 0304-3975 .

В эту статью включен текст Коми Амико, доступный по лицензии CC BY 4.0 .

Внешние ссылки

[1] Кирби, Лори; Пэрис, Джефф. «Доступные результаты независимости для арифметики Пеано» (PDF) . Кафедра прикладной логики . Проверено 4 сентября 2021 г.

[2] ttps://www.reddit.com/r/BradyHaran/comments/1c6z1t4/the_hydra_game_numberphile/

[3] ttps://cal.vin/p/hydra5

[4] ttps://li.cal.vin/p/the-hydra-game-solved

[5] «Гидры» . agnijomaths.com . Проверено 05 сентября 2021 г.

[6] Хамано, Масахиро; Окада, Мицухиро (1995). «Связь между редукцией доказательств Генцена, игрой Кирби-Пэрис) с гидрой и игрой с гидрой Бухгольца (предварительный отчет) *» (PDF) . Научно-исследовательский институт математических наук Киотского университета . Проверено 4 сентября 2021 г.

[7] Кетонен, Юсси; Соловей, Роберт (1981). «Быстрорастущие функции Рамсея» . Анналы математики . 113 (2): 267–314. дои : 10.2307/2006985 . ISSN 0003-486X . JSTOR 2006985 .

[8] Бухгольц, Вильфрид (27 ноября 1984 г.). «Результат независимости для Π11 - CA + BI» (PDF) . Мюнхенский университет Людвига-Максимилиана . Проверено 4 сентября 2021 г.

[9] Хамано, Масахиро; Окада, Мицухиро (1 марта 1998 г.). «Прямое доказательство независимости игры Бухгольца «Гидра» на конечных помеченных деревьях» . Архив математической логики . 37 (2): 67–89. дои : 10.1007/s001530050084 . ISSN 1432-0665 . S2CID 40113368 .

[10] Карлуччи, Лоренцо (7 мая 2003 г.). «Новое теоретико-доказательное доказательство независимости теоремы Кирби – Пэрис о гидре». Теоретическая информатика . 300 (1–3): 365–378. дои : 10.1016/S0304-3975(02)00332-8 . ISSN 0304-3975 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]