Едно търсене, продължило четири десетилетия е завършено... Емил Василев 16:41

Едно търсене, траяло четири десетилетия е приключено...

Емил Василев 16:41 | 26.07.2024 0 Сподели

Най-четени

IT НовиниДаниел Десподов - 16:25 | 25.07.2024

Изпреварил е времето с цели 180 години: в античната лаборатория на алхимик бе открит метал от бъдещето

ТелефониСветослав Димитров - 13:46 | 23.07.2024

Експерти обясниха за какво е неразрешено да държите смарт телефона върху мека мебел, до момента в който се зарежда

IT НовиниДаниел Маринов - 21:25 | 23.07.2024

Гигантската плаваща стена от вятърни турбини се доближава една стъпка по-близо до действителността

Емил Василевhttps://www.kaldata.com/

Много хора не се сещат за математика, когато чуят думата „ бобър “. Тези работливи същества обаче символизират една от най-изненадващите концепции в комплицираната област на науката: не всичко е изчислимо, колкото и да се стараем. Функцията на „ заетия бобър “ е първият образец за несметен математически израз. Тя се изяснява елементарно: това е оптималният брой стъпки, които една компютърна стратегия може да направи, преди да спре, в случай че има 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). Но кой знае: може би някой ще успее още веднъж да изненада специалистите.