Для большинства людей термин “занятой бобер” ассоциируется с неутомимым тружеником или (для биологов среди нас) инженером экосистем, играющим важную роль. Однако для математиков “занятой бобер” имеет схожее, но уникальное значение. В соответствии с первоначальным замыслом названия, идея требует большой работы, но эта работа направлена на решение вопроса. Как говорит специалист по информатике Кристофер Мур в видеоролике для журнала Quanta, “Что самое долгое и сложное [компьютер] может сделать, а затем остановиться?” Другими словами, какую самую длительную функцию может выполнять компьютер, которая не просто выполняется вечно, застряв в бесконечном цикле?
Решение этого вопроса называется числом занятого Бивера, или BB (n), где n представляет собой ряд инструкций, называемых "состояниями", которым должен следовать набор компьютеров — в частности, тип простого компьютера, называемый машиной Тьюринга. Каждое состояние генерирует определенное количество программ, и каждая программа получает свою собственную машину Тьюринга, поэтому все быстро усложняется. BB(1), который имеет только 1 состояние, требует использования 25 машин Тьюринга. На протяжении десятилетий многие математики полагали, что решение числа занятого Бивера для четырех состояний является верхним пределом, но группе экспертов удалось подтвердить решение BB (5) в 2024 году (именно на Discord). Согласно новому отчету New Scientist, теперь участники того же конкурса Busy Beaver Challenge узнают увлекательную правду о следующем шаге в развитии математики — BB (6) — и о том, что он может представлять собой самый передний край математики.
Сначала краткое объяснение. Вышеупомянутая задача BB(1), которая является простейшей версией задачи BB (n), использует только один набор правил и приводит только к двум результатам — бесконечному перемещению по ленте или остановке на первом числе. Поскольку 1 - это наибольшее количество шагов, которое выполнит любая из 25 машин Тьюринга из BB(1), прежде чем завершит свою программу (известную как остановка), ответом на BB(1) будет 1. По мере увеличения числа состояний увеличивается количество шагов и количество машин Тьюринга, необходимых для запуска программ, а это означает, что каждый последующий BB (n) становится экспоненциально более сложным для решения. Значения BB(2) и BB(3) равны 6 и 21 соответственно, но значение BB(4) равно 107, и для его решения требуется семь миллиардов различных машин Тьюринга. Конечно, многие из этих машин работают бесконечно и могут быть отброшены, но многие этого не делают.
Число занятого Бобра было впервые сформулировано венгерским математиком Тибером Радо в 1962 году, и прошло 12 лет, прежде чем ученый-компьютерщик Аллен Брэди определил, что BB (4) выполняется в течение 107 шагов, прежде чем остановиться. В течение десятилетий это казалось абсолютным пределом возможного, но затем в 2024 году математики решили задачу BB (5), проанализировав 17 триллионов (с учетом t) возможных машин Тьюринга. Ответ? Поразительные 47 176 870 шагов. В журнале Quanta есть превосходное объяснение того, как это было достигнуто.
Но, наконец, при решении задачи BB(5) возник следующий очевидный вопрос: а как же BB(6)? Конечно, добавление всего лишь еще одного правила усложняет задачу в геометрической прогрессии, поскольку для решения задачи BB(6), по оценкам, требуется 60 квадриллионов машин Тьюринга.
“Задача Busy Beaver дает вам очень конкретную шкалу для осмысления границ математических знаний”, - сказал New Scientist ученый-компьютерщик Тристан Стерин, который помогал запускать Busy Beaver Challenge в 2022 году.
В новом посте анонимный пользователь “mxdys”, который сыграл важную роль в окончательном подтверждении BB(5), написал, что ответ на BB(6), вероятно, настолько непостижимо велик, что само число, вероятно, нуждается в отдельном объяснении, поскольку оно, вероятно, слишком велико для описания с помощью возведения в степень. Вместо этого он основан на тетрации (записываемой, скажем, как yx, в отличие от возведения в степень xy), в которой экспонента также повторяется, создавая башню экспонент. Как отмечает в своем блоге Скотт Ааронсон, американский специалист по информатике, который помог определить значение BB(5), это означает, что 1510 можно представить как “10 к 10, 10 к 10 и так далее 15 раз”.
Как отмечает mxdys, значение BB(6) равно, по крайней мере, 2-тетратному отношению к 2-тетратному отношению к 2-тетратному отношению к 9. Один математик, беседовавший с New Scientist, сказал, что, вероятно, количество всех атомов во Вселенной будет выглядеть “ничтожным” по сравнению с этим. Хотя эти большие цифры поражают воображение, они также говорят математикам об ограничениях основы современной математики, известной как теория множеств Цермело—Френкеля (ZFC), а также о таких скользких математических концепциях, как гипотеза Коллатца.
Маловероятно, что математики когда-нибудь решат задачу BB (6), но если задача "Занятого бобра" является каким-то доказательством, то этот факт, скорее всего, не остановит их от попыток.
