Любители математики приближаются к невообразимо огромному числу — настолько большому, что оно находится на грани осязаемого в рамках современной математики.
Начинается все с простого, вроде бы, вопроса: как узнать, будет ли компьютерная программа работать вечно? Ответ на него еще в 1930-х искал математик Алан Тьюринг. Он показал, что любой компьютерный алгоритм можно имитировать с помощью простой «машины Тьюринга», которая читает и записывает 0 и 1 на бесконечной ленте, следуя набору инструкций, называемых состояниями. Чем сложнее алгоритм, тем больше состояний требуется.
Для каждого количества состояний, например 5 или 100, существует конечное число соответствующих машин Тьюринга, но неясно, как долго каждая из них должна работать. Наибольшее возможное время работы для каждого числа состояний называется числом усердного бобра или BB(n), и эта последовательность растет невероятно быстро: BB(1) = 1, BB(2) = 6, но уже пятый «усердный бобр» насчитывает 47 176 870.
Точное значение следующего числа, BB(6), неизвестно, но онлайн-сообщество под названием Busy Beaver Challenge пытается его найти. В 2024 году они обнаружили BB(5), завершив 40-летние поиски. Теперь участник под ником mxdys выяснил, что BB(6) должно быть не меньше числа, настолько огромного, что даже его описание требует объяснения.
«Это число настолько превосходит все физические масштабы, что даже не смешно», — говорит инженер-программист Шон Лигоцки из Busy Beaver Challenge.
Он сравнивает поиск среди всех возможных машин Тьюринга с рыбалкой в глубоком математическом море, где в темноте плавают лишь странные и экзотические фрагменты кода.
Новая оценка для BB(6) настолько велика, что требует математического языка, выходящего за рамки возведения в степень, такого как 2³ = 8. Сначала идет тетрация, иногда записываемая как x↑↑n, которая представляет собой множественное возведение в степень. Например, 3↑↑2 — это 2 в степени 2 в степени 2, что равно 16.
По оценке mxdys, BB(6) не меньше, чем 2↑↑(2↑↑(2↑↑9)) — башни множественной тетрации, где каждая тетрация, в свою очередь, представляет собой башню многократного возведения в степень. По сравнению с этим числом количество всех частиц во Вселенной кажется ничтожным, говорит Лигоцки.
Но числа усердного бобра интересны не только из-за своего абсурдного размера. Тьюринг доказал, что существуют машины Тьюринга, поведение которых невозможно предсказать в рамках теории ZFC — основы всей современной математики. Его вдохновила теорема о неполноте Курта Гёделя, которая показала, что правила самой ZFC нельзя использовать для доказательства абсолютной непротиворечивости этой теории.
«Изучение чисел усердного бобра делает открытия Гёделя и Тьюринга почти столетней давности количественными и конкретными, — объясняет Скотт Ааронсон из Техасского университета в Остине. — Вместо того чтобы просто сказать, что машины Тьюринга ускользают от возможностей ZFC в определении их поведения после некоторой точки, мы теперь можем спросить: происходит ли это уже с машинами с шестью состояниями или уже с 600?»
Исследователи уже доказали, что BB(643) выходит за пределы теории ZFC, но многие меньшие числа еще не изучены.
«Проблема "усердного бобра" дает очень полную шкалу для размышлений о границе математического знания», — говорит специалист по информатике Тристан Стэрин, запустивший Busy Beaver Challenge в 2022 году.
Функция усердного бобра, вероятно, «кодирует огромную часть всей интересной математической истины в своих первых ста значениях», и BB(6) не исключение, полагает Аронсон. Оно, похоже, связано с гипотезой Коллатца — знаменитой нерешенной математической проблемой, которая предполагает вырождение любых чисел в единицу в результате множественных арифметических операций. Поиск BB(6) связан с машиной Тьюринга, которая должна имитировать некоторые шаги этой проблемы, чтобы остановиться: если она остановится — это укажет на вычислительное доказательство версии гипотезы.
Числа, с которыми работают исследователи, невероятны по своей величине, но структура усердного бобра дает измеримую шкалу для того, что иначе казалось бы непостижимой областью математики. По мнению Стэрина, именно это захватило многих участников, хотя большинство из них не ученые. Прямо сейчас над поиском BB(6) постоянно работают несколько десятков человек.
Остаются тысячи «непокоренных» машин Тьюринга, чье поведение еще не проверено, говорит Стэрин.
«За углом может оказаться машина, которая непознаваема», — согласен Лигоцки, имея в виду, что машина эта независима от ZFC и находится за пределами современной математики.
Может, точное значение BB(6) уже не за горами? Лигоцки и Стэрин остерегаются давать прогнозы, но уже полученная приблизительная оценка дает «интуитивное ощущение, что нас ждет что-то большее».
Найдено самое большое простое число
Ундециллион и дуодециллион: что означают эти числа
Подписывайтесь и читайте «Науку» в Telegram