Представьте, что вам показывают ряд чисел: 1, 6, 21, 107 и — внимание! — 47 176 870. Кажется естественным спросить: какое число идёт дальше? Угадать его невозможно. Эти значения — первые пять членов так называемой последовательности «занятого бобра». Она связана с одной из самых глубоких и трудных проблем теоретической информатики. Вычисление её членов оказывается настолько сложным, что уже более шестидесяти лет этой задачей занимаются и профессиональные математики, и энтузиасты. Первые четыре числа были установлены ещё в 1960–1970-х годах. Пятое же, BB(5), оказалось во много раз больше предыдущих и лишь недавно — в прошлом году — было окончательно определено благодаря совместной работе группы любителей-исследователей в онлайн-сообществе Busy Beaver Challenge. А вот значение шестого числа, BB(6), остаётся неизвестным. Известны лишь нижние границы, и они колоссальны. В 2022 году удалось доказать, что BB(6) настолько велико, что его невозможно даже записать привычным способом: если бы ка
Публикация доступна с подпиской
Поддержать автораПоддержать автора