Число, которое нельзя посчитать: почему в 2025 году математики снова упёрлись в пределы логики
Границы математики в 2025 году: как исследователи продвигаются к числу Busy Beaver
Generated by DALL·E
В 2025 году математическое сообщество и энтузиасты продолжили работу над одной из самых необычных задач в теории вычислений. Речь идёт о последовательности «Занятой бобёр» (Busy Beaver) — серии чисел, которые появляются из очень простого вопроса: как понять, остановится ли программа или будет работать бесконечно.
На первый взгляд это похоже на интеллектуальную игру. Но в реальности эта тема связана с тем, где заканчиваются возможности вычислений и где математика сталкивается с ограничениями логики.
Что такое «Занятой бобёр»
Чтобы объяснить последовательность Busy Beaver, учёные опираются на идеи Алана Тьюринга. Он предложил модель «машины Тьюринга» — это упрощённый компьютер с лентой и набором правил. Несмотря на простоту, такая машина может воспроизвести логику любого алгоритма.
Дальше появляется задача: если мы ограничим машину Тьюринга небольшим числом «состояний» (условно — инструкций), то:
- какие-то машины остановятся;
- какие-то будут работать бесконечно;
- а некоторые остановятся, но перед этим выполнят огромное число шагов.
Busy Beaver-число для заданного количества состояний — это максимальное число шагов среди всех машин, которые всё-таки останавливаются.
И вот здесь начинается самое важное: в общем случае невозможно написать универсальный алгоритм, который всегда точно скажет, остановится ли произвольная программа. Это известный результат Тьюринга — «задача остановки» считается неразрешимой. Поэтому и Busy Beaver-функция относится к числам, которые нельзя вычислить стандартным способом.
Почему это называют «границей математики»
Busy Beaver-числа растут очень быстро. И дело не только в масштабе. Чем больше состояний у машины, тем труднее доказать, что машина действительно остановится. Иногда для этого нужно проводить сложный анализ или строить новые доказательства. А иногда невозможно заранее сказать, получится ли в принципе доказать нужное утверждение.
Из-за этого Busy Beaver часто используют как наглядный пример того, что существуют математические объекты, которые можно определить словами, но которые почти невозможно «достать руками» — то есть вычислить или доказать точно.
Что удалось сделать: решение для 5 состояний
Один из заметных итогов последних лет связан с числом BB(5) — Busy Beaver для машин Тьюринга с 5 состояниями.
Онлайн-сообщество Busy Beaver Challenge, которое появилось в 2022 году, поставило себе задачу закрыть этот вопрос полностью. В 2024 году исследователи сообщили, что им удалось найти и доказать точное значение:
BB(5) = 47 176 870 шагов.
Это означает, что среди всех машин с 5 состояниями, которые всё же останавливаются, самая «долгоиграющая» делает почти 47,2 миллиона шагов перед остановкой — и при этом доказано, что больше не получится.
Для этого команде пришлось проанализировать огромный массив вариантов. По опубликованным материалам, речь шла о сотнях миллионов машин, для которых нужно было установить, останавливаются они или нет.
Что происходит в 2025 году: попытка продвинуться к BB(6)
После решения BB(5) внимание переключилось на следующий шаг — BB(6). И именно он чаще всего появляется в публикациях 2025 года.
На этом уровне сложность резко растёт. Главная проблема в том, что для машин с 6 состояниями:
- неизвестно точное Busy Beaver-число;
- неизвестно, какая из машин является «самой долгой»;
- некоторые случаи очень трудно классифицировать: непонятно, остановятся они когда-нибудь или нет.
Поэтому в 2025 году работа в основном идёт в двух направлениях:
- Поиск новых “чемпионов” — машин, которые гарантированно останавливаются, но делают больше шагов, чем все известные раньше. Это даёт новую нижнюю границу для BB(6): число точно не меньше найденного значения.
- Сокращение числа “непонятных” машин — тех, по которым пока нет доказательства ни остановки, ни бесконечной работы. В обсуждениях Busy Beaver Challenge и связанных групп регулярно появляются отчёты о статусе таких случаев.
То есть «продвижение к числу BB(6)» означает не то, что кто-то нашёл его целиком. Это скорее постепенное сужение неизвестной зоны: какие-то машины удаётся доказательно «закрыть», какие-то дают новые рекорды по длине работы.
Почему эта задача важна не только как головоломка
Busy Beaver-числа интересны потому, что они показывают границу между:
- тем, что можно вычислить и доказать;
- и тем, что можно сформулировать, но нельзя решить универсальным методом.
С одной стороны, это чистая математика и теория алгоритмов. С другой — это практический урок о том, что даже у очень строгих формальных систем есть пределы. Иногда проблема выглядит простой, но за ней скрывается нерешаемость, связанная с фундаментальными свойствами вычислений.
Что дальше
В 2025 году Busy Beaver Challenge продолжает работу с BB(6) и более сложными вариантами задач. Скорее всего, прогресс будет идти так же: через поиск новых рекордных машин и через доказательства для отдельных «неопределённых» случаев.
Это не похоже на типичную научную гонку за быстрым результатом. Скорее это долгий процесс, где важны терпение, строгие доказательства и совместная работа. И именно поэтому Busy Beaver остаётся одной из тем, которую называют «краем математики» — не из-за мистики, а из-за того, как она показывает пределы вычислений и логики.