Самая сложная задача математики? Математики ищут число, которое определит предел познания

В самых отдалённых уголках теоретической информатики, на границе между вычислимым и непознаваемым, разворачивается тихая, но яростная гонка. Её цель — не новый сверхмощный процессор или искусственный интеллект, а число. Число настолько колоссальное, что оно бросает вызов не просто нашему воображению, а самим основам логики и доказательства. Это история о «проблеме Усердного Бобра» — интеллектуальном марафоне, который может показать нам, где кончается математика.

Представьте себе, что вы не академик в престижном университете, а просто энтузиаст, вооружённый компьютером и страстью к головоломкам. Именно такие люди из онлайн-сообщества The Busy Beaver Challenge сегодня находятся на переднем крае фундаментальной науки. Их цель — найти значение BB(6), шестого числа в последовательности «Усердных Бобров». И недавний прорыв участника под ником mxdys показал, что это число имеет размеры, которые заставляют померкнуть астрономические величины.

Но чтобы понять масштаб этой погони, нужно вернуться к её истокам и разобраться, что это за странные «бобры».

Что такое «Усердный Бобёр» и почему он не даёт покоя учёным?

Всё началось с одного из самых фундаментальных вопросов в информатике, который задал ещё Алан Тьюринг: как понять, остановится ли когда-нибудь компьютерная программа или будет работать вечно? Это знаменитая «проблема остановки». Тьюринг доказал, что не существует универсального алгоритма, который мог бы решить эту задачу для любой программы.

Чтобы исследовать эту проблему, он придумал абстрактную модель — машину Тьюринга. Представьте себе предельно простой компьютер: бесконечная лента, разделённая на ячейки (с нулями и единицами), и считывающая головка, которая движется по ленте, стирает и записывает символы. Поведение головки определяется очень простым набором правил, или «состояний».

«Проблема Усердного Бобра» — это своего рода игра на этом поле. Правила таковы:

1. Возьмите машины Тьюринга с определённым количеством состояний (например, с двумя, тремя, четырьмя).
2. Отсейте все машины, которые работают бесконечно (зацикливаются).
3. Среди тех, что в итоге останавливаются, найдите ту, которая проработала дольше всех и оставила на ленте больше всего единиц.

Число «Усердного Бобра», или BB(n), — это максимальное количество шагов, которое может сделать машина с n состояниями перед остановкой.

Звучит как простая игра в числа, не так ли? Но дьявол, как всегда, в деталях. Эта последовательность растёт с немыслимой скоростью:

• BB(1) = 1
• BB(2) = 6
• BB(3) = 21
• BB(4) = 107
• BB(5) = 47 176 870 (это значение нашли только в 2024 году после 40 лет поисков!)

А что насчёт BB(6)? Его точное значение неизвестно. Но недавние расчёты показывают, что оно настолько велико, что для его описания пришлось выйти за рамки привычной арифметики.

Башня степеней: как описать неописуемое?

Мы привыкли, что возведение в степень (например, 10¹⁰⁰) порождает огромные числа. Но для описания нижней границы BB(6) этого языка уже недостаточно. Математикам пришлось обратиться к следующей операции — тетрации.

Если умножение — это многократное сложение, а возведение в степень — многократное умножение, то тетрация — это многократное возведение в степень. Она создаёт так называемые «степенные башни». Например, «2 тетрированное в 4» — это 2 в степени 2 в степени 2 в степени 2, что равно 65 536.

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

Но зачем вообще гоняться за этими монстрами? Неужели это просто интеллектуальный спорт? Нет. Здесь мы подходим к самому главному.

Заглянуть за край: где кончается математика?

Эта погоня — не просто соревнование. Это практический эксперимент по поиску границ познания. В основе всей современной математики лежит система аксиом, чаще всего ZFC (теория множеств Цермело — Френкеля с аксиомой выбора). Это как операционная система для математики — набор базовых правил, из которых выводятся все теоремы.

Ещё в 1930-х годах Курт Гёдель своей знаменитой теоремой о неполноте доказал, что любая достаточно сложная система правил (вроде ZFC) содержит утверждения, которые являются истинными, но их невозможно доказать внутри этой же системы. Это фундаментальный предел логики. Мы знаем, что такие «недоказуемые истины» существуют, но не знаем, как они выглядят.

И вот здесь «Усердные Бобры» выходят на сцену. Они служат своего рода измерительной линейкой для этого абстрактного предела. Тьюринг доказал, что поведение некоторых машин Тьюринга в принципе невозможно предсказать с помощью аксиом ZFC. Это значит, что значение BB(n) для некоторого n является недоказуемым в рамках нашей математики.

Вопрос, который мучает учёных: насколько велико это n? Когда мы столкнёмся с этой стеной? Учёные уже доказали, что BB(643) недоказуемо. Но может быть, предел гораздо ближе? Может, уже BB(6) окажется тем самым «числом Гёделя» — конкретным, но непознаваемым значением?

Как говорит Скотт Ааронсон, один из ведущих исследователей в этой области, изучение «бобров» делает философские открытия Гёделя и Тьюринга «количественными и конкретными». Мы больше не говорим абстрактно о «каких-то» пределах — мы пытаемся нащупать их руками. Найти машину Тьюринга, поведение которой непредсказуемо, — это всё равно что найти первую трещину в здании общепринятой математики.

Не просто игра в числа: гипотеза Коллатца и коллективный разум

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

Эта гипотеза утверждает, что если взять любое натуральное число и выполнять с ним две простые операции (если оно чётное — делить на 2, если нечётное — умножать на 3 и прибавлять 1), то в конце концов мы всегда получим 1. Гипотезу проверили для невообразимого количества чисел, но общего доказательства до сих пор нет. Если удастся доказать, что одна из таких «коллатцеподобных» машин Тьюринга останавливается, это может стать ключом к доказательству варианта гипотезы.

Экспедиция на край познания продолжается

История «Усердного Бобра» — это удивительный пример того, как современная наука может двигаться вперёд силами энтузиастов со всего мира. Это не мегапроект с миллиардными бюджетами, а кропотливая работа десятков людей, просеивающих триллионы вариантов в поисках истины.

Они подобны исследователям, которые с помощью простой линейки пытаются измерить бездну. Каждое новое найденное значение BB — это не просто рекорд, а очередной шажок к горизонту событий математики. За этим горизонтом лежат утверждения, которые мы никогда не сможем доказать или опровергнуть.

Будет ли BB(6) найдено? Или оно окажется первым числом, которое заставит человечество признать пределы своего логического аппарата? Никто не знает. Но, как и в любой великой экспедиции, важен не только пункт назначения, но и само путешествие. И эта экспедиция на край познания только начинается.