BB(3, 3) — сложно | Слигоцки

Я рад поделиться с вами машиной Тьюринга с 3 состояниями и 3 символами, которую нельзя доказать, остановится она или нет (при запуске на пустой ленте), не решив проблему, подобную Коллатцу. Следовательно, решение проблемы \(BB(3, 3)\) по меньшей мере так же сложно, как и решение проблемы Коллатца, класса задач, о которых Пол Эрдеш сказал знаменитое высказывание: «Математика может быть не готова к таким задачам».

В прошлом году в Мать гигантовЯ описал семейство ТМ, которые требуют эффективного моделирования или полного решения проблемы, подобной Коллатцу, чтобы доказать, «квазиостанавливаются» они или нет. Они были найдены при поиске «Пищущие» занятые бобрывариант Busy Beavers, представленный Скоттом Ааронсоном в его книге 2020 года. Обзорная статья Busy Beaver. С тех пор ищу пример в обычной игре Busy Beaver.

За прошедшие годы было создано множество замечательных ТМ, изготовленных вручную, которые обеспечивают такие результаты для игры Busy Beaver. Например, доказывая:

• \(ББ(745)\) требует доказательство состоятельности ZFC
• \(ББ(27)\) требует доказательство гипотезы Гольдбаха
• \(BB(15)\) и \(BB(5, 4)\) требовать доказывая гипотезу Эрдеша (что для всех \(n > 8\) представление \(2^n\) по основанию 3 имеет хотя бы одну цифру 2).

Однако ни одна из этих ценностей Busy Beaver пока не доступна нам, простым смертным. За последние 60 лет нам удалось доказать только значения \(BB(2), BB(3), BB(4)\) и \(BB(2, 3)\), и известно, что \(BB(6) > 10 \uparrow\uparrow 15\). Пока я не проанализировал эту ТМ, я думал, что у нас есть шанс доказать \(BB(3, 3)\)!

Машина

Эту ТМ я назову «Снежный человек» (название поясню в конце статьи). Это определяется таблицей переходов:

1RB2RA1LC_2LC1RB2RB_---2LA1LA (на bbchallenge)

	0	1	2
А	1РБ	2РА	1LC
Б	2ЛЦ	1РБ	2РБ
С	—	2ЛА	1ЛА

Это один из оставшихся 160 неофициальных \(BB(3, 3)\) несогласных, которых Джастин Бланшар недавно общий на Discord-канале bbchallenge.org. Эта конкретная ТМ была первой поделились и проанализировали автор @savask, 14 октября 2023 г., на том же канале Discord.

Анализ

Рассмотрим общую конфигурацию:

\[A(a, b, c) = 0^\infty \; 12^a \; 11^b \; \text{

We can prove the following rules:

\[\begin{array}{l}
A(a, & 6k, & c) & \to & A(a, & 8k+c-1, & 2) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+1, & c) & \to & A(a+1, & 8k+c-1, & 3) & \text{if} & 8k+c \ge 1 \\
A(a, & 6k+2, & c) & \to & A(a-1, & 8k+c+3, & 2) & \text{if} & a \ge 1 \\
A(a, & 6k+3, & c) & \to & A(a, & 8k+c+1, & 5) \\
A(a, & 6k+4, & c) & \to & A(a+1, & 8k+c+3, & 2) \\
A(a, & 6k+5, & c) & \to & A(a, & 8k+c+5, & 3) \\
\end{array}\]

\[A(0, 6k+2, c) \to \text{Halt}(16k+2c+7)\]

На самом деле эти правила являются исчерпывающими. Как только снежный человек входит в такую ​​конфигурацию \(A(a, b, c)\) (с \(c \ge 1\)), эти правила описывают точное поведение, которому он будет следовать вечно (или до тех пор, пока не остановится).

Глядя на приведенные выше правила, мы видим, что они повторяют функцию, подобную Коллатцу, для параметров \(b\) и \(c\), в то время как \(a\) сохраняет своего рода промежуточный итог. Каждый раз, когда \(b \equiv 1 \pmod{6}\) или \(b \equiv 4 \pmod{6}\), \(a\) увеличивается, и каждый раз \(b \equiv 2 \pmod{6) }\), \(a\) уменьшается на единицу. Снежный человек останавливается только в том случае, если \(a\) уменьшается ниже 0.

Траектория с пустой ленты

Начиная с пустой ленты, снежный человек достигает конфигурации \(A(2, 1, 2)\) на шаге 69. При моделировании этого процесса \(a\), похоже, постоянно растет с течением времени. После 24 миллионов итераций имеем \(a = 3\,999\,888\).

Псевдослучайное блуждание

Рассмотрим последовательность остатков \(b\) mod 6. Если представить, что эта последовательность равномерно распределена случайным образом, то этот процесс моделирует смещенное случайное блуждание по числовой прямой, где (для каждого шага) вероятность шага вправо равен \(\frac{2}{3}\), а вероятность шага влево равна \(\frac{1}{3}\.

Это известная проблема теории Цепи Маркова и можно доказать, что если вы находитесь в позиции \(a = n\), существует \((\frac{1}{2})^{n+1}\) шанс, что вы когда-нибудь достигнете позиции \ (а = -1\) в будущем.

Конечно, последовательность остатков \(b\) не случайна, а полностью детерминирована. (На самом деле, они даже следуют последовательному шаблону: нечетное, нечетное, четное, четное…) Однако в широком масштабе они, похоже, следуют траектории, примерно похожей на случайную цепь Маркова. Мы видим, что на траектории, указанной выше, где после 24 миллионов шагов ожидается, что цепь Маркова переместится вправо 8 миллионов раз и влево 4 миллиона раз, что приведет к значению, очень близкому к фактическому значению \(a\) вокруг 4 миллиона.

Вероятно, не останавливаясь

Как упоминалось выше, случайная цепь Маркова будет иметь примерно \((\frac{1}{2})^{4\,000\,000}\) шанс когда-либо достичь \(a = -1\) в этой точке. Это число настолько мало, что любой ученый с радостью заявил бы, что это гарантированно не удастся. Точно так же здесь я скажу, что снежный человек «вероятно» никогда не останавливается (используя слова Джона Конвея). Это означает, что если он действует что-то близкое к цепи Маркова, он никогда не остановится.

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

Два мира

Мы живем в одном из двух миров: либо снежный человек останавливается, либо бежит вечно. Если она остановится, то это можно будет доказать, ускорив итерации этой функции, подобной Коллатцу, настолько, чтобы ее можно было смоделировать до завершения. Если она работает вечно, то для доказательства этого потребуется доказать, что эта функция, подобная Коллатцу, никогда не достигнет останавливающегося перехода \(a = 0\).

Основываясь на приведенном выше аргументе о цепях Маркова, я считаю, что мы живем во втором мире, и мне кажется, что доказать это гораздо труднее.

Криптиды

Как мы называем такие машины? Те, чье поведение было сведено к относительно простому математическому правилу, которое попадает в класс открытых математических задач. Эти машины кажутся своего рода легендарными существами, ходят слухи, что они либо останавливаются, либо нет, но никто не смог предоставить каких-либо конкретных доказательств в поддержку того или иного вывода. предлагаю позвонить им «Криптиды», проводя параллели с легендарными существами, такими как Лохнесское чудовище или Чупакабра. И что ж, поскольку этот ТМ, кажется, ходит случайным образом, я подумал, что «Бигфут» будет подходящим именем.

Действительно ли поведение Коллатца действительно сложно?

Я полагаю, что некоторые из вас могут задаться вопросом: действительно ли сложно анализировать поведение этой конкретной функции, подобной Коллатцу? Не переоцениваю ли я это поведение просто потому, что оно связано со знаменитой сложной задачей Коллатца? Думаю, можно с уверенностью сказать, что никто, кроме меня, никогда не изучал динамику этой конкретной проблемы. Так что, возможно, применив немного теории чисел и усердия, кто-то сможет найти умное математическое свойство, которое применимо к этой задаче (но не к более широкому набору задач, подобных Коллатцу). Это, безусловно, возможно, и я рад услышать, есть ли у кого-нибудь идеи относительно того, как решить эту проблему. Было бы здорово узнать, что доказательство \(BB(3, 3)\) остается в пределах досягаемости!

Однако, по моему (ограниченному) опыту анализа и чтения проблем типа Коллатца, кажется, что можно задавать только два типа вопросов: (1) те, которые относительно тривиально доказать, и (2) те, которые ни один математик не знает, как чтобы доказать. В первой категории мы имеем такие шаблоны, как тот факт, что \(b\) последовательно повторяется по шаблону (нечетный, нечетный, четный, четный, …) в итерациях Коллатца Бигфута или что каждый раз, когда вы применяете традиционный \(3n+1\ ) По правилу Коллатца вы всегда получаете четное число, которое на следующем шаге будет разделено на 2. Примеры второй категории включают в себя практически все остальные вопросы, которые мы можем задать о поведении этих систем Коллатца.