Математики уточнили Busy Beaver для 5 состояний и двигаются к BB(6)
В 2025 году математическое сообщество и энтузиасты продолжают обсуждение и проверку одной из самых необычных задач теории вычислений — последовательности Busy Beaver, которая на русском чаще известна как «Занятой бобёр». В основе этой темы лежит простой вопрос: может ли программа работать бесконечно, и существует ли универсальный способ заранее понять, остановится ли она.
Исследователи напоминают, что основой для таких рассуждений служит модель Алана Тьюринга — «машина Тьюринга». Её можно представить как очень упрощённый компьютер, который действует по набору правил и работает с лентой символов. Несмотря на простоту, такая модель описывает логику любых алгоритмов.
Далее возникает задача: если ограничить машину небольшим числом состояний (условно — инструкций), то часть машин остановится, часть будет работать бесконечно, а некоторые завершат работу лишь после огромного числа шагов. Busy Beaver-число для заданного количества состояний определяется как максимальное число шагов среди всех машин, которые в итоге всё же останавливаются.
Здесь проявляется важное ограничение теории вычислений. Тьюринг показал, что «задача остановки» неразрешима: универсального алгоритма, который для любой программы всегда точно скажет, остановится ли она, не существует. Из-за этого Busy Beaver-функция относится к таким объектам, которые можно определить, но нельзя вычислить «общим методом».
Одним из заметных результатов последних лет стало завершение работы над значением BB(5) — Busy Beaver для машин Тьюринга с пятью состояниями. Онлайн-сообщество Busy Beaver Challenge, запущенное в 2022 году, поставило целью закрыть этот вопрос строго и окончательно. В 2024 году участники проекта сообщили, что нашли и доказали точное значение: BB(5) равняется 47 176 870 шагам. То есть среди всех останавливающихся машин с пятью состояниями самая «долго работающая» совершает почти 47,2 млн шагов перед остановкой, и доказано, что более длинного варианта в этом классе нет.
Для этого потребовалось перебрать и проанализировать огромный массив вариантов. По опубликованным материалам, речь шла о сотнях миллионов машин, для которых нужно было установить, останавливаются они или нет.
В 2025 году внимание сместилось к следующему уровню — BB(6). Сложность резко возрастает: точное значение Busy Beaver для шести состояний неизвестно, неизвестен и абсолютный «чемпион», а часть машин по-прежнему трудно классифицировать. Поэтому текущая работа идёт в двух направлениях. Первое — поиск новых рекордных машин, которые гарантированно останавливаются, но работают дольше всех ранее известных, что повышает нижнюю границу BB(6). Второе — сокращение числа «неопределённых» случаев, по которым пока нет доказательства ни остановки, ни бесконечной работы.
Эксперты портала «boda» отмечают, что интерес к Busy Beaver связан не только с любопытством. Эта последовательность показывает границу между тем, что можно вычислить и доказать, и тем, что можно сформулировать, но нельзя решить универсальным способом. Поэтому для теории алгоритмов это наглядная демонстрация пределов вычислений и логики.