Чем так занят усердный бобёр?

Продолжаю свою телегу про Busy Beaver(N). Напомню, что эта функция равна времени работы самой долгой машины Тьюринга из N состояний, исключая впадающие в бесконечный цикл, которую запускают на бесконечной ленте из нулей.

BB(4) равно 107 - на 4 состояниях особо не развернёшься, а вот BB(5) равна уже 47,176,870. Чтобы осознать её прикол, нам нужно сделать небольшое отступление и посмотреть на одну из простейших (на вид) открытых проблем в математике. Рассмотрим функцию такого вида:

f(x) = x/2, если x чётное
f(x) = 3n+1, если x нечётное

Что, если взять какое-нибудь N и начать применять к нему такую функцию много раз? 5->16->8->4->2->1. Так называемая гипотеза Коллатца заключается в том, что из любого числа мы в итоге придём к 1. Это было подтверждено для чисел <10^21, но так и не было доказано для любого N. У Veritasium есть очень любопытное видео на эту тему.

Итак, функции, которые применяют определённую арифметическую операцию к числу в зависимости от остатка на деления, так и называют - Collatz-like. Их траектории выглядят практически случайными и могут долго колебаться, прежде чем придут в какое-то "финальное" состояние.

Да, вы всё правильно поняли - оказалось, что усердный бобёр из 5 состояний генерирует последовательность для Collatz-like функции от нуля следующего вида:

f(x) = 5(x/3) + 6, если x mod 3 = 0
f(x) = 5(x-1)/3 + 9, если x mod 3 = 1
f(x) = finish state, если x mod 3 = 2

То есть, вместо единицы, как в оригинале, "конечных точек" у неё бесконечно много. Так выглядит генерируемая бобром последовательность:

0->6->16->34->64->114->196->334->564->946->1584->2646->4416->7366->12284->finish

Я окунулся ещё глубже, изучил доказательство и симуляцию, чтобы понять, как это реально выглядит на ленте машины Тьюринга. В итоге пронаблюдал следующее цирковое представление.

Итак, определим такое состояние ленты C(m, n) - сначала m единиц, потом n раз по 001 и ещё 1 единичка в конце. Указатель при этом смотрит на ноль по соседству слева перед всей этой конструкцией. Машина проделывает следующее упражнение, начиная из состояния C(m, 0).

1) m единиц она превращает в ~m/3 троек 001, т.е. общая длина почти не меняется. C(m, n) -> C(0, (m+4)/3) или C(3, (m+3)/3), в зависимости от остатка от деления. В третьем случае машина как раз проваливается в своё конечное состояние.

2) Далее машина наступает на каждую 001, закрашивает нули и отправляется в самое начало ленты, добавляя ещё 2 единицы слева, а затем переходит к следующей 001. То есть, C(m, n) -> C(m+5, n-1).

3) Когда 001 заканчиваются и n снова равно 0, мы получили C(m_next, 0) и далее повторяем процедуру, начиная со пункта 1. Последовательность значений m_1, m_2. m_3, ... как раз и ведёт себя как Collatz-like ряд, описанный выше.

Машина работает десятки миллионов шагов, потому что для каждого добавления пяти единиц за одну 001 указатель пробегает туда-сюда через все уже записанные ранее единицы.

Честно говоря, меня всё это повергает в восторг. Самая долгая машина Тьюринга из 5 состояний совершенно не обязана была делать что-то, имеющее короткую арифметическую интерпретацию. Более того, оказывается, теоретические границы вычислимого имеют связи с реальными математическими проблемами.

Busy Beaver для 6 состояний неизвестен. Такой "простор" позволяет создавать монстров, например, так называемого Экспоненциального Коллатца: вместо умножения становится возможным применять экспоненту на каждом шаге. Но это далеко не предел - только за этот июнь было получено 2 принципиально новых результата - числа, которые возможно записать только в стрелочной нотации. А вы жалуетесь, что GPT-5 долго релизят.

@knowledge_accumulator