Усердный бобёр: математики вычислили BB(5)

Многие люди, слыша слово «бобры», не задумываются о математике. Однако эти трудолюбивые создания символизируют одну из самых удивительных концепций в сложной области науки: не всё поддаётся вычислению, как бы мы ни старались. Функция «busy beaver» (усердный бобёр) является первым примером невычислимого математического выражения. Она легко объясняется: это максимальное количество шагов, которое компьютерная программа может сделать перед остановкой, если у неё есть n состояний, где состояния означают сложность задачи. Но её значения, называемые BB(n), никогда не будут известны для всех величин n. Математики и теоретики компьютерных наук долго задавались вопросом, на каком n инструменты математики перестают работать: где именно находится предел того, что можно вычислить?

Более 40 лет многие эксперты предполагали, что BB(5) лежит за пределами вычислимости и, следовательно, недоступна. Однако международный проект «Busy Beaver Challenge» определил значение BB(5), и его расчёт был формально подтверждён компьютерным помощником доказательств. Новое исследование показывает, что магическое число для BB(5) составляет 47,176,870. Это значит, что программа с пятью состояниями может выполнить максимум 47,176,870 шагов перед остановкой — или никогда не остановится. Последнее значительное достижение в этой области было в 1983 году, когда компьютерный учёный Аллен Брэди доказал, что BB(4) равно 107.

«Усердные бобры» глубоко укоренены в основах математики. В 20 веке многие эксперты мечтали найти основу, на которой можно доказать все математические истины. Но в 1931 году логик Курт Гёдель, которому тогда было всего 25 лет, разрушил их надежды. Он доказал, что существуют неизбежно недоказуемые утверждения в математике — утверждения, которые невозможно ни доказать, ни опровергнуть. Изначально эксперты надеялись, что это абстрактный результат без значимых приложений, но они ошибались.

Математики теперь знают о многих недоказуемых задачах. Один из первых примеров — проблема остановки, связанная с выполнением алгоритмов. В 1930-х годах Алан Тьюринг выяснил, что нет алгоритма, который мог бы предсказать, остановится ли компьютерная программа с определёнными входными данными или будет работать вечно. Тогда Тьюринг работал над теоретической моделью такого компьютера, ныне известной как машина Тьюринга. Эта теоретическая машина состоит из бесконечной ленты, размеченной 1 и 0, и головки, которая читает ленту, описывает её и перемещает вправо или влево. Такая машина теоретически может выполнить любой вид вычислений — как и компьютер.

Допустим, вы хотите запрограммировать машину Тьюринга на умножение двух чисел. 1 и 0 на ленте соответствуют этим двум числам. Перед вычислением вы определяете определённое количество состояний или правил для машины, таких как A, B, C и D, а также HALT (остановка). Эти состояния определяют, как машина Тьюринга действует с каждым вводом. Например: если машина с пятью состояниями читает 1 на ленте в состоянии A, она заменяет это на 0, перемещает ленту влево и переключается в состояние C. Две инструкции требуются для каждого из состояний A до D, в зависимости от того, что машина находит на ленте — 1 или 0. В определённых условиях (например, состояние B при чтении 1) машина может переключиться в состояние HALT. В этом случае машина Тьюринга останавливается, и вычисление завершено. Результат будет представлен числами на ленте в этот момент.

Как доказал Тьюринг, не существует машины Тьюринга, которая могла бы определить для всех возможных конфигураций машин Тьюринга, остановятся ли они в какой-то момент. И здесь вступают в игру трудолюбивые бобры.

В 1962 году венгерский математик Тибор Радо разработал «игру усердных бобров», в которой искал самую трудолюбивую машину Тьюринга определённого размера: какое максимальное количество шагов вычисления может выполнить машина Тьюринга с n состояниями, которая в какой-то момент останавливается? Чтобы ответить на этот вопрос в общем случае, нужно решить проблему остановки. Чтобы найти самого усердного бобра, нужно знать, какие машины Тьюринга останавливаются (и, следовательно, прекращают работу на определённом шаге), а какие — нет. Но Тьюринг показал, что узнать это невозможно, что означает, что функция «busy beaver» BB(n) не может быть рассчитана для всех возможных чисел состояний.

Тем не менее, Радо определил первые три значения функции BB, хотя это потребовало значительных усилий. Трудность возникает, отчасти, из-за того, что количество возможных машин Тьюринга (компьютерных алгоритмов) быстро увеличивается с увеличением числа состояний (n). Для каждого из двух входных значений, 0 или 1, машина Тьюринга выполняет три разных шага в определённом состоянии:

Она заменяет ввод на вывод (0 или 1). Этот шаг имеет две возможные операции. Она перемещает ленту вправо или влево. Это также влечёт за собой две возможные операции.

Она меняет состояние на одно из n или на состояние остановки. Этот шаг требует n + 1 возможных операций.

Таким образом, для каждого входного значения и каждого из n состояний существует 2 x 2 x (n + 1) возможных операций. Объединение обоих вводов даст в общей сложности (4n + 4)2n различных возможных наборов конкретных шагов, где каждый набор шагов представляет собой другой алгоритм или другую машину Тьюринга. Если разрешено только одно состояние, уже существует 64 различных машины Тьюринга. Из них только те, которые переключаются в состояние остановки после первого шага вычисления, остановятся. Поскольку существует только одно другое правило, кроме HALT, если машина не останавливается, она будет продолжать выполнять это одно правило вечно. Поэтому ни одна из останавливающихся машин Тьюринга не будет выполнять более одного шага вычисления, что объясняет, почему BB(1) = 1. Ситуация усложняется, если разрешить два состояния. В этом случае уже существует (4 x 2 + 4) в четвёртой степени, или 20,736, машины Тьюринга, которые нужно изучить. Нет общего метода для исследования, какие машины Тьюринга останавливаются. Как выяснил Радо, самая долго работающая программа с двумя состояниями — самый усердный бобёр — может выполнить шесть арифметических шагов, поэтому BB(2) = 6.

Радо и его тогдашний аспирант Шень Лин смогли также уточнить случай с тремя состояниями в 1965 году: среди 16,777,216 машин Тьюринга те, которые останавливаются в какой-то момент, могут выполнить максимум BB(3) = 21 вычислительный шаг. В 1963 году Радо описал попытку вычислить BB(4) как безнадёжную. Но 20 лет спустя Брэди удалось определить BB(4): наибольшее количество шагов вычислений для машины Тьюринга с четырьмя состояниями (или четырьмя правилами) составляет 107. Это оставалось последним значением функции «busy beaver», которое можно было точно определить в течение четырёх десятилетий.

После публикации результата Брэди математическое сообщество переключилось на точное вычисление BB(5). Эксперты организовали конкурс в немецком городе Дортмунд в 1984 году, где они пытались найти пятое значение функции. Победителем конкурса стал компьютерный учёный Уве Шульц, который нашёл программу с 134,467 шагами вычислений. Пять лет спустя компьютерные учёные Хайнер Марксен и Юрген Бунтрок нашли одну из пяти состояний машин, которая не останавливалась до достижения 47,176,870 шагов, представив таким образом новое минимальное значение для BB(5). Однако доказать, что среди пяти состояний машин нет более усердной программы, не удалось. Охотникам на «busy beaver» нужно было доказать, что все остальные машины либо работали бесконечно, либо останавливались раньше, чем на 47,176,870-м шаге.

Поэтому многие эксперты подозревали, что BB(5) = 47,176,870. Но без твёрдого доказательства это было лишь гипотетическим.

В 2022 году Тристан Стерин, тогда аспирант по компьютерным наукам, запустил проект «Busy Beaver Challenge». Целью проекта было собрать и проверить все результаты, связанные с «busy beavers». Например, если кто-то доказал, что программа с пятью состояниями может работать бесконечно, он мог опубликовать доказательство и проверить его с помощью компьютерного помощника. Это позволило многим заинтересованным лицам работать вместе и представлять действительные результаты. Проект был завершён в этом месяце, с окончательным доказательством, что BB(5) действительно составляет 47,176,870. Программа соответствует рекурсивной функции, аналогичной функции из гипотезы Коллатца, одной из крупнейших нерешённых проблем теории чисел.

Поиск «усердных бобров» продолжается. Машина Тьюринга с шестью состояниями уже выполняет настолько много арифметических шагов, что для записи числа требуется новая арифметическая операция (10↑↑15). Есть всё больше свидетельств, что BB(6) вероятно невычислима. В 2024 году была найдена шестистейная машина Тьюринга, почти соответствующая проблеме Коллатца. Если бы кто-то хотел доказать, что эта машина останавливается (или продолжает работать вечно), это было бы равносильно решению проблемы Коллатца.

Попытки вычислить BB(6) вероятно обречены на провал. Компьютерный учёный Скотт Ааронсон не слишком надеется, как он написал в блоге: «Если и когда искусственные суперинтеллекты захватят мир, они могут беспокоиться о значении BB(6). А затем Бог может беспокоиться о значении BB(7).» Возможно, математики действительно достигли предела вычислимого с BB(5). Но кто знает: возможно, кто-то сможет снова удивить экспертов.