BB(6) — число, которое невозможно представить ни человеку ни современным компьютерам. Даже если людям и ИИ дать на это вечность.
Представьте себе последовательность чисел: 1, 6, 21, 107, 47 176 870. Какое число идет следующим?
Такой вопрос задал себе Алан Тьюринг, чтобы понять, могут ли компьютерные программы работать вечно. Он доказал, что любой алгоритм можно имитировать с помощью простой «машины Тьюринга». Эта машина читает и записывает 0 и 1 на бесконечной ленте, следуя инструкциям, называемым состояниями. Чем сложнее алгоритм, тем больше состояний нужно.
Для каждого количества состояний, будь то 5 или 100, существует конечное число машин Тьюринга. Но сколько времени каждая из них будет работать?
Наибольшее возможное время работы машины с n состояниями называется числом усердного бобра, или BB(n). Эта последовательность растет невероятно быстро: BB(1) = 1, BB(2) = 6, а уже пятый «усердный бобр» включает 47 176 870. Это похоже на то, как невозможно сложить лист бумаги больше семи раз, потому что стопка становится толще ширины листа.
Точное значение BB(6) до сих пор неизвестно. Математическое сообщество Busy Beaver Challenge пытается его найти. В 2024 году они нашли BB(5), завершив поиски, которые длились 40 лет. Теперь же участник под ником mxdys выяснил, что это число настолько велико, что даже если бы каждую цифру записать на атомах всей Вселенной, материала все равно бы не хватило!
Зачем это нужно?
Не только ради любопытства. BB(6) может показать нам, где заканчиваются возможности математики. Это ключ к пониманию того, что можно узнать и доказать в принципе.