Представьте: вам предъявляют последовательность 1, 6, 21, 107 и внезапно — 47 176 870. Сможете ли вы предсказать, что последует далее?
Если нет — не переживайте: практически никто не догадывается. Это первые пять значений «усердного бобра» — величайшей загадки теории вычислений, связанной с тем, сколько шагов выполнит машина Тьюринга перед остановкой.
Первые четыре числа BB(n) вычислили в 1960–1970-х годах; пятое значение, BB(5), оказалось столь огромным, что было установлено лишь в прошлом году энтузиастами из сообщества Busy Beaver Challenge.
О размере BB(6) известно лишь нижнее ограничение — величину, которую нельзя записать десятичной записью даже на каждый атом Вселенной по одной цифре: цифр просто не хватит.
«Это превосходит всё, что мы можем себе представить», — говорит Скотт Ааронсон из Техасского университета в Остине.
Недавно охотники на бобров повысили это нижнее ограничение ещё сильнее. Один из самых плодовитых участников проекта в июне установил новый рекорд, затем через девять дней превзошёл и сам себя, обнулив границы, обозначенные в 2022 году.
«BB(6) ушёл в стратосферу огромных чисел», — отмечает Уильям Гасарч из Мэрилендского университета.
Суть «усердного бобра»
В основе игры «усердный бобр» лежит важнейшая проблема информатики: по коду программы определить, остановится она когда-нибудь или будет работать бесконечно. В 1936 году Алан Тьюринг доказал непреодолимость этой задачи, введя model вычислений, известную как машина Тьюринга.
В 1962 году Тибор Радо предложил сопроводить теорию «игрой»: из всех машин с n правилами найти ту, которая выполняет наибольшее число шагов и всё же останавливается. Это число назвали BB(n).
Теоретически нужно сгенерировать все такие машины, отсеять бесконечно работающие, смоделировать оставшиеся и зафиксировать максимальное число шагов. Но число возможных машин растёт взрывным образом, и многие из них уводят эмуляцию в гигантские циклы, требуя изощрённых приёмов анализа.
«Улучшения железа помогают, но лишь до определённого момента», — говорит Шон Лигоцки, разработчик и охотник на «усердных бобров».
Эра рекордов
В 1990–2000-х годах Шон и его отец Терри Лигоцки в Лоуренсской национальной лаборатории в Беркли нашли машину с шестью правилами, которая останавливается после почти 3000 цифр в десятичной записи числа шагов — уже внушительный, но ещё умещающийся на листе бумаги.
Спустя несколько лет студент Павел Кропиц в дипломной работе запустил сетку из 30 компьютеров и нашёл машину, работающую ещё дольше, снова побил собственный рекорд, выйдя на 30 000 цифр — этого хватило бы на около десяти страниц.
В мае 2022-го Лигоцки с новым кластером вычислил ещё более «упорного» чемпиона, Кропиц отреагировал рекордным результатом уже через три дня, и так длилась бесконечная гонка.
Конец цифр
Когда числа стали такими большими, что о десятичной записи и речи нет, для описания рекордов включили тетрацию — операцию двойного возведения в степень (↑↑). Лигоцки остановился на 10↑↑5 шагов, Кропиц ответил 10↑↑15, и привычные числа остались позади.
В 2022 году стартовал проект Busy Beaver Challenge, объединивший охотников на бобров: в 2024-м они доказали значение BB(5), затем переключились на BB(6), достигнув сначала 10↑↑10⁷ шагов, а в июне 2025-го — 2↑↑↑5 при помощи пентации (↑↑↑).
За гранью воображения
Новейший рекорд: машина mxdys преодолела отметку 2↑↑(2↑↑(2↑↑(2↑↑2))), что выводит BB(6) за пределы любого описания во Вселенной. Это лишь нижняя граница — истинное значение, возможно, ещё выше.
Исследование «Антигидры» и её «родственниц» требует новых прорывов в чистой математике, ведь вопрос об их остановке связан с нерешённой гипотезой Коллатца. Но тысячи шестиправилных машин ждут анализа, и охотники не собираются останавливаться.
«Математика — это искусство, и в ней всегда найдётся место удивлению», — пишут участники сообщества в своём Discord.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа «Прогрев») — HABRFIRSTVDS.
