Какво е по-голямо от самата реалност? BB(6) — число, което е невъзможно дори да си представим

Представете си, че ви дават поредица от числа: 1, 6, 21, 107 и изведнъж 47 176 870. Кое ще е следващото? Почти невъзможно е да се отгатне. Това са така наречените „числа на заетия бобър“ — специална поредица, свързана с една от най-трудните задачи на теоретичната информатика. Нейното изследване в продължение на повече от шестдесет години привлича както професионални математици, така и любители, превръщайки се в отделна субкултура.

Първите четири стойности са изчислени още през 60-те и 70-те години на миналия век, а петата, BB(5) се оказа толкова огромна, че точната ѝ стойност беше установена едва миналата годин,а благодарение на усилията на общност от ентусиасти, които работиха заедно в рамките на проекта Busy Beaver Challenge.

Следващото число, BB(6) все още не е определено. Известни са само долните оценки, а те са зашеметяващи.

През 2022 година беше доказано, че това число е толкова голямо, че е принципно невъзможно да бъде записано в десетичната система: дори всяка цифра да бъде издълбана в атомите на цялата Вселена, пак няма да има достатъчно от тях. Две години по-късно границите отново бяха преместени: новите оценки направиха предишните резултати незначителни в сравнение с мащаба на последвалите открития.

Задачата се основава на известната задача за спиране, формулирана от Алън Тюринг през 1936 година. Той звучи по следния начин: можем ли да разберем от кода на една програма дали работата ѝ ще приключи, или ще се изпълнява безкрайно дълго? Тюринг доказва, че не съществува универсален алгоритъм за решаване на този проблем. За да го формализира, той предлага модел на изчисление, наречен машина на Тюринг, при който програмата се определя от прости правила. Колкото повече са правилата, толкова по-сложно е поведението на машината и толкова по-трудно е да се предвиди дали тя ще спре или не.

През 1962 година математикът Тибор Радо изобретява вид игра, наречена „зает бобър“. За даден брой правила n се изисква да се намери машина на Тюринг, която работи най-дълго при крайното спиране. Броят на нейните стъпки е броят на заетите бобри BB(n). Но практическото търсене на такива машини се превръща в предизвикателство: броят на възможните варианти нараства бързо, много от тях засядат в безкрайни цикли, а симулацията на дълготрайни екземпляри става невъзможна без нови математически идеи.

Повратният момент в търсенето на BB(6) настъпва в началото на 2000 гoдина, когато Шон Лигоцки заедно с баща си Тери използват изчислителната мощ на лабораторията „Бъркли“ и откриват машина с шест правила, която работи в продължение на почти три хиляди стъпки – число с 3000 цифри.

То изглеждало огромно, но се побирало на един лист хартия. По-късно словашкият студент Павел Кропиц стигнал по-далеч, като свързал мрежа от 30 компютъра и открил машина с работно време от десетки хиляди цифри. Неговият рекорд се задържа в продължение на 12 години, докато Лигоки не си намери нов „шампион“. Скоро двамата с Кропиц си разменяли рекорди буквално на всеки няколко дни, а след това преминали на съвсем друго ниво на числата – от кули от степени (тетрации), високи десетки етажи, до такива конструкции, при които обичайният рекорд става невъзможен дори в компактен вид.

Истинският пробив настъпи през 2022-2024 година, когато общността Busy Beaver Challenge, основана от Тристан Стерен най-накрая доказа BB(5) и веднага премина към BB(6). Сред участниците беше и студентката от Вирджиния Кейтлин Дусет, която откри машина, сравнима с рекорда на Кропиц, но основана на друг принцип – механизма на така наречените „преливници“. Това отвори нов клас кандидати и скоро анонимен участник под псевдонима mxdys обяви машина с рекорд от 10↑↑↑↑107 стъпки – кула от десетки милиони етажи. Невъзможно е да се запише това число дори в символична форма: низът би отнел десетки километри хартия.

Седмица по-късно mxdys отново надмина резултата, като представи машина с време за работа, което вече се изразява в пентация – още по-бърза операция на растеж от тетрацията. Полученото число е толкова голямо, че нито един компактен запис не се вписва дори в мащаба на Вселената.

Всички тези резултати обаче остават само долни оценки: реалната стойност на BB(6) може да е още по-голяма.

Освен това в хода на лова участниците се натъкнали на загадъчни машини, една от които била наречена „Антихидра“. Има сериозни основания да се смята, че тя никога няма да спре, но все още не е възможно да се докаже: поведението ѝ е свързано с друг известен нерешен проблем – хипотезата на Колац. Решаването на тази загадка ще изисква фундаментални пробиви в чистата математика.

Въпреки чудовищните мащаби на числата и нерешените въпроси интересът към проблема само нараства. Днес хиляди шестоъгълни машини остават неизследвани, като всяка от тях може да крие ново откритие. За участниците в предизвикателството Busy Beaver Challenge това не е просто състезание, а вид изкуство – търсене на красота и изненада в самите дълбини на теорията на изчисленията.