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