Много хора не се сещат за математика, когато чуят думата „бобър“. Тези трудолюбиви същества обаче символизират една от най-изненадващите концепции в сложната област на науката: не всичко е изчислимо, колкото и да се стараем. Функцията на „заетия бобър“ е първият пример за неизчислим математически израз. Тя се обяснява лесно: това е максималният брой стъпки, които една компютърна програма може да направи, преди да спре, ако има 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 години) разбива надеждите им. Той доказва, че в математиката съществуват непременно недоказуеми твърдения – твърдения, които не могат нито да бъдат доказани, нито опровергани. Първоначално експертите се надявали, че това е абстрактен резултат без значими приложения, но грешали.
Математиците вече са наясно с много недоказуеми проблеми. Един от първите примери е проблемът за спирането, свързан с изпълнението на алгоритми.
През 30-те години на миналия век Алън Тюринг разбрал, че не съществува алгоритъм, който може да предскаже дали компютърна програма с определени входни данни ще спре или ще работи вечно. След това Тюринг работи върху теоретичен модел на такъв компютър, известен днес като машина на Тюринг. Тази теоретична машина се състои от безкрайна лента, обозначена с 1 и 0, и глава, която чете лентата, описва я и я премества наляво или надясно. Теоретично такава машина може да извършва всякакви изчисления – точно като компютър.
Да предположим, че искате да програмирате машината на Тюринг да умножи две числа. На тези две числа съответстват 1 и 0 на лентата. Преди изчислението определяте определен брой състояния или правила за машината, като например A, B, C и D, както и HALT (спиране). Тези състояния определят как машината да действа при всеки вход. Например: ако машина с пет състояния прочете 1 на лента в състояние А, тя го заменя с 0, премества лентата наляво и преминава в състояние С. За всяко от състоянията от А до D са необходими по две инструкции в зависимост от това дали машината намира на лентата 1 или 0. При определени условия (например, когато в състояние В се чете 1) машината може да премине в състояние HALT. В този случай машината на Тюринг спира и изчислението е завършено. Резултатът ще бъде представен от числата на лентата в този момент.
Както е доказал Тюринг, няма машина на Тюринг, която да може да определи за всички възможни конфигурации на машините на Тюринг дали те ще спрат в някакъв момент и точно тук се появяват „заетите бобри“.
През 1962 година унгарският математик Тибор Радо разработва „игра на заетите бобри“, в която търси най-трудолюбивата машина на Тюринг с определен размер: какъв е максималният брой изчислителни стъпки, които може да извърши машина на Тюринг с n състояния, която спира в някакъв момент? За да отговорим на този въпрос в общия случай, трябва да решим задачата за спиране. За да намерим най-трудно работещия бобър, трябва да знаем кои машини на Тюринг спират (и следователно се прекратяват на определена стъпка) и кои не спират. Но Тюринг показа, че е невъзможно това да се знае, което означава, че функцията на заетия бобър 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. Това остава последната стойност на функцията на „заетия бобър“, която може да бъде точно определена в продължение на четири десетилетия.
След като резултатът на Брейди е публикуван, математическата общност насочва вниманието си към точното изчисляване на BB(5).
През 1984 година в германския град Дортмунд специалисти организират състезание, на което се опитват да намерят петата стойност на функцията. Победител в състезанието е компютърният учен Уве Шулц, който намира програма със 134 467 стъпки за изчисление. 5 години по-късно компютърните учени Хайнер Марксен и Юрген Бунтрок откриват едно от петте състояния на машините, което не спира, докато не достигне 47 176 870 стъпки, като по този начин представят нова минимална стойност за BB(5). Въпреки това не е било възможно да се докаже, че сред петте състояния на машината не е имало по-натоварена програма. Ловците на „заети бобри“ трябваше да докажат, че всички останали машини или са работили безкрайно, или са спрели преди 47 176 870-та стъпка.
Толкова много експерти подозираха, че BB(5) = 47 176 870, но без категорични доказателства това беше само хипотеза.
През 2022 година Тристан Стерин, тогава дипломант по компютърни науки стартира проекта Busy Beaver Challenge. Целта на проекта беше да се съберат и проверят всички резултати, свързани със „заетите бобри“. Например, ако някой докаже, че програма с пет състояния може да работи безкрайно дълго, той би могъл да публикува доказателството и да го провери с помощта на компютърен асистент. Това позволи на много заинтересовани хора да работят заедно и да представят валидни резултати. Проектът беше завършен този месец с окончателно доказателство, че BB(5) наистина е 47 176 870. Програмата съответства на рекурсивна функция, подобна на функцията от предположението на Колац – един от най-големите нерешени проблеми в теорията на числата.
Търсенето на „заети бобри“ продължава. Машината на Тюринг с шест състояния вече извършва толкова много аритметични стъпки, че за записването на едно число е необходима нова аритметична операция (10↑↑15).
Има все повече доказателства, че BB(6) вероятно е неизчислима. През 2024 година е установено, че шестстепенна машина на Тюринг почти отговаря на задачата на Колац. Ако някой иска да докаже, че тази машина спира (или продължава да работи вечно), това би било равносилно на решаване на проблема на Колац.
Опитите да се изчисли BB(6) вероятно са обречени на неуспех. Компютърният учен Скот Ааронсън не е много обнадежден, тъй като пише в блога си:
„Ако и когато изкуствените свръхинтелигентности завладеят света, те могат да се тревожат за стойността на BB(6) и тогава Бог може да се тревожи за значението на BB(7).“
Може би математиците наистина са достигнали границата на изчислимото с BB(5). Но кой знае: може би някой ще успее отново да изненада експертите.
Всичко важно от света на технологиите, директно в пощата ти.
С абонирането приемате нашите Условия и Политика за поверителност. Може да се отпишете с един клик по всяко време.
Коментирайте статията в нашите Форуми. За да научите първи най-важното, харесайте страницата ни във Facebook, и ни последвайте в Google Новини, TikTok, Telegram и Viber или изтеглете приложението на Kaldata.com за Android, iPhone, Huawei, Google Chrome, Microsoft Edge и Opera!