Новая машина Тьюринга с десятью состояниями побила прежний рекорд в задаче Занятого бобра и резко подняла известную нижнюю границу для BB(10). Машина оставляет на ленте больше единиц, чем число Грэма, хотя состоит всего из десяти состояний. Точное значение BB(10) математики по-прежнему не знают.
Джефф Кетчерсид нашёл новую машину компьютерным перебором 8 октября. Затем Кетчерсид проверил её поведение в системе формальных доказательств Coq. Проверка подтверждает, что программа действительно останавливается, превосходит предыдущего чемпиона BB(10) и оставляет на ленте число единиц, превышающее число Грэма.
Занятый бобёр - математическая игра с очень простыми правилами и почти абсурдно сложными последствиями. Исследователи берут машину Тьюринга с фиксированным числом состояний, запускают её на пустой ленте и ищут вариант, который успеет сделать как можно больше работы перед остановкой. Чем больше состояний разрешено использовать, тем труднее доказать, какая машина действительно держит абсолютный рекорд.
Для десяти состояний задача ещё не решена. Поэтому найденная машина не раскрывает BB(10), а только поднимает планку, ниже которой ответ уже точно находиться не может. Предыдущий чемпион, найденный в 2024 году, достигал уровня fω(fω(25)) в иерархии быстрорастущих функций. Новая конструкция перескочила на уровень fω+1, где числа растут несравнимо быстрее.
Пытаться записать результат обычными цифрами бессмысленно. Даже число Грэма, которое стало знаменитым именно благодаря своему чудовищному размеру, оказывается меньше доказанного результата новой машины. Причём формальная проверка касается не приблизительной оценки: Coq подтверждает точное число единиц, которое машина оставляет перед остановкой, а затем доказывает, что результат превосходит число Грэма.
Точное число выполненных шагов Кетчерсид пока не вычислил. Однако машина не может оставить на ленте больше единиц, чем число Грэма, сделав меньше шагов, поэтому длительность работы тоже превосходит число Грэма. Сводка проекта Busy Beaver называет десятисостоянийную конструкцию самой маленькой известной двухсимвольной машиной Тьюринга, преодолевшей эту границу. Раньше для аналогичного результата требовалось не меньше 13 состояний.
Сам рекорд вырос из восьмисостоянийной машины. Кетчерсид сохранил её основную вычислительную часть и добавил два состояния, которые перехватывают момент прежней остановки и запускают дальнейшие циклы. Каждый следующий цикл получает уже гигантское число и раздувает его ещё сильнее. Небольшая добавка к программе поэтому переносит вычисление на новый уровень быстрорастущей иерархии.
Формальное доказательство собрано без дополнительных аксиом и отдельно проверяет остановку машины, конечный результат, нижние границы и превосходство над предыдущим BB(10)-чемпионом. При этом сообщество Busy Beaver пока помечает анализ как не проверенный независимо. Поэтому корректнее говорить о новом опубликованном чемпионе и более высокой известной границе BB(10), а не об окончательно найденном значении функции.
