Что больше самой реальности? BB(6) — число, которое невозможно даже представить

Представьте, что вам дают последовательность чисел: 1, 6, 21, 107 и внезапно 47 176 870. Какое будет следующим? Угадать почти невозможно. Это так называемые «числа занятого бобра» — особая последовательность, связанная с одной из самых трудных задач теоретической информатики. Её исследование на протяжении более шестидесяти лет притягивает как профессиональных математиков, так и любителей, превратившись в отдельную субкультуру.

Первые четыре значения удалось вычислить ещё в 1960–70-е годы, а пятое, BB(5), оказалось настолько огромным, что его точное значение было установлено только в прошлом году благодаря усилиям сообщества энтузиастов, работавших вместе в рамках проекта Busy Beaver Challenge.

Следующее число, BB(6), до сих пор не определено. Известны лишь нижние оценки, и они поражают воображение. В 2022 году удалось доказать, что это число настолько велико, что записать его в десятичной системе принципиально невозможно: даже если бы каждую цифру вырезать на атомах всей Вселенной, их всё равно не хватило бы. Спустя два года границы были снова передвинуты: новые оценки сделали прежние результаты ничтожными по сравнению с масштабом последующих находок.

В основе задачи лежит знаменитая проблема остановки, сформулированная Аланом Тьюрингом в 1936 году. Она звучит так: можно ли по коду программы понять, завершится ли её работа или она будет выполняться бесконечно? Тьюринг доказал, что универсального алгоритма для решения этой задачи не существует. Для её формализации он предложил модель вычислений, получившую название машина Тьюринга, где программа задаётся простыми правилами. Чем больше правил, тем сложнее поведение машины и тем труднее предсказать, остановится она или нет.

В 1962 году математик Тибор Радо придумал своеобразную игру — «занятый бобр». Для заданного числа правил n требуется найти такую машину Тьюринга, которая при конечной остановке работает дольше всех. Количество её шагов и есть число занятого бобра BB(n). Но практический поиск таких машин превращается в испытание: число возможных вариантов растёт стремительно, многие застревают в бесконечных циклах, а симуляция долгоживущих экземпляров становится невозможной без новых математических идей.

Перелом в охоте за BB(6) наступил в начале 2000-х, когда Шон Лигоки вместе с отцом Терри использовал вычислительные мощности Лаборатории Беркли и нашёл шестиправильную машину, работавшую почти три тысячи шагов — число с тремя тысячами цифр. Казалось огромным, но оно уместилось на одном листе бумаги. Позднее словацкий студент Павел Кропиц пошёл дальше, подключив сеть из 30 компьютеров и отыскав машину с временем работы уже в десятки тысяч цифр. Его рекорд держался 12 лет, пока Лигоки не нашёл новый «чемпион». Вскоре они с Кропицем обменивались рекордами буквально каждые несколько дней, а затем перешли на совершенно иной уровень чисел — от башен степеней (тетрации) высотой в десятки этажей до таких конструкций, где обычная запись становится невозможной даже в компактной форме.

Настоящий прорыв произошёл в 2022–2024 годах, когда сообщество Busy Beaver Challenge , основанное Тристаном Стереном, окончательно доказало значение BB(5) и сразу переключилось на BB(6). Среди участников оказалась студентка из Виргинии Кэйтлин Дусетт, которая нашла машину, сопоставимую с рекордом Кропица, но основанную на ином принципе — механизме так называемых «счётчиков с переполнением». Это открыло новый класс кандидатов, и вскоре анонимный участник под псевдонимом mxdys объявил о машине с рекордом в 10↑↑107 шагов — башня десяток высотой десять миллионов этажей. Записать это число невозможно даже в символической форме: строка из десяток заняла бы десятки километров бумаги.

Через неделю mxdys снова превзошёл результат , представив машину с временем работы, которое уже выражается через пентацию — ещё более быструю операцию роста, чем тетрация. Получившееся число так велико, что никакая компактная запись не помещается даже в масштабы Вселенной.

Однако все эти находки остаются лишь нижними оценками: реальное значение BB(6) может быть ещё больше. Более того, в процессе охоты участники столкнулись с загадочными машинами, одна из которых получила название «Антигидра». Есть веские основания полагать, что она никогда не остановится, но доказать это пока не удаётся: её поведение связано с другой знаменитой нерешённой задачей — гипотезой Коллатца. Решение этой загадки потребует фундаментальных прорывов уже в чистой математике.

Несмотря на чудовищные масштабы чисел и нерешённые вопросы, интерес к задаче только растёт. Сегодня тысячи шестиправильных машин остаются неисследованными, каждая из которых может скрывать новое открытие. Для участников Busy Beaver Challenge это не просто соревнование, а своего рода искусство — поиск красоты и неожиданности в самой глубине вычислительной теории .