Неодлучив задатак

У теорији усклађености и теорији комплексности, неодлучив задатак је проблем одлучивања за који се зна да је немогућ конструисати у једном алгоритму који увек доводи до тачно да-или-не одговора.

Проблем одлуке је било које произвољно да-или-не питање над бесконачним скупом уноса. Због тога, традиционајлно је дефинисати проблем једнакости као скуп уноса којима проблем враћа да. Ови уноси могу бити природни пројеви, али такође и друге вредности неке друге врсте, као што су стрингови формалног језика. Коритећи неко кодирање, као што је Геделово нумерисање, стрингови могу бити кодирани као природни бројеви. Зато, проблем одлуке неформално је формулисан у смислу формалног језика који је једнак скупу природних бројева. Да би се задржала формална дефиниција једноставном, формулисано је у смислу подргрупе природних бројева.

Формално, проблем одлуке је подгрупа природних бројева. Одговарајући неформални проблем је одлучивање да ли је дати број у групи. Проблем одлуке А се назива одлучив или ефективно решив ако је А рекурзивни скуп. За проблем се каже да је делимично одлучив, полу-одлучив, решив или доказив ако је А рекурзивно нумерисана група. Ово значи да постоји алгоритам који се зауставља на крају када је одговор да али може да иде до бесконачности ако је одговор не. Делимично одлучиви проблеми и остали проблем који нису одлучиви се називају недолучивим. 

У теорији усклађености

У теорији усклађености, халтинг проблем је проблем одлучивања који може почети овако :

С обзиром на опис произвољног програма и завршног уноса, одлучити се да ли ће програм завршити са радом или ће радити заувек.

Алан Тјуринг је доказао 1936 да генерални алгоритам који ради на Тјуринговој машини који решава халтинг проблем за све могуће уносе парова програма који су неопходни, не може постојати. Дакле, халтинг проблем је неодлучив за Тјурингове машине.

Однос са Геделовом теоремом непотпуности

Концепти прикупљени преко Геделове теореме о непотпуности су веома слични онима који су прикупљени преко халтинг проблема, и докази су веома слични. У ствари, слабија форма од Прве Теореме Непотпуности која је лака последица неодлучивости халтинг проблема. Ова слабија форма разликује се од стандардне наредбе теореме непотпуности твдећи да је комплетан, доследан и звучно аксиоматизован од свих изјава отприлике природни бројеви су недостижни. "Звучни део" је слаба тачка: то значи да ме захтевамо аксиоматски систем да би доказали тачне наредба о природним бројевима. Важно је посматрати да је изјава стандардне форме Геделове теореме о непотпуности потпуно неупућена у питање тачности, али се само брине од проблему да ли може бити доказан. 

Слабија форма теореме може бити доказана преко неодлучивости халтинг проблема као што следи. Препоставимо да имамо доследну и комплетну аксиматизација свих тачних наредби логика првог реда о природним бројевима. Онда можемо направити алгоритам који набраја све наредбе. Ово значи да постоји алгоритам N(n) који, дату му је природан број n , израчунава логике првог реда наредби о природним бројевима такве да, за све тачне наредбе,  постоји најмање једно n такво да N(n) даје ту наредбу. Сада претпоставима да хоћемо да видимо да ли се алгоритам са репрезентацијом а зауставља при уносу i . Знамо да наредба може бити изражена са наредбом логике првог реда, рецимо H(a,i). Пошто је аксиматизација комплетна следи да или је n такво да је N(n) = H(a,i) или постоји n' такво да је N(n') =   ¬ H(a, i). Тако да ако би извршили итерацију на n док не нађемо H(a,i) или његову негацију, увек ћемо се зауставити. Ово значи да нам ово даје алгоритам да одлучимо халтинг проблем. Пошто знамо да не постоји такав алгоритам, следи претпоставка да  доследна и комплетна аксиматизација свих тачних наредби логика првог реда о природним бројевима мора бити нетачна.

Примери недолучивих проблема

Неодлучиви проблеми могу бити у вези са различитим темама, као што је логика, апстракне машине или топологија. Имати на иму да пошто има небројиво много неодлучивих проблем, свака листа, чак и део бесконачне дужине, је безпотребно недовршена. 

Примери наредби неодлучивости

Постоје два различита чула речи "неодлучивог" у савременој употреби. Први од њих је чуло које се  користи у односу на Геделове теореме, да се изјаве бића не могу доказати, ни оповргнути у одређеном дедуктивном систему. Друго чуло се користи у односу на теорију усклађености и не односи се на изјаве, него  на проблеме одлука, које су усклађени бесконачни скупови питања код којих сваки захтева да или не одговор. За такав проблем се каже да је неодлучив ако нема за израчуниву функцију која тачно одговара на свако питање о проблему у скупу. Веза између ова два је да ако је проблем одлука неодлучив (у рекурзијско теоријском смислу) онда нема доследно ефективног формалног система који доказује да свако питање А у проблему или "одговор на А је да" или "одговор на  А је не ".

Због ова два значења речи неодлучивог, термин независан се понекад користи уместо неодлучивог за "ни недоказивост ни оповргљивост" смислу. Употреба "независни" је двосмислена, свакако. То може да значи само "недоказив", остављајући отворено питање да ли  независна наредба може побити.

Неодлучивост изјаве у одређеном дедуктивној система , само по себи, не одговорара на питање да ли је вредност  наредбе истинита и добро дефинисана , или да ли се може одредити на други начин. Неодлучивост само значи да је посебан дедуктиван систем који се сматра не доказује истину или лаж наредбе. Независно да ли постоје такозване "апсолутно неодлучиве" наредбе, чија је вредност истинита никада не може бити позната или је лоше наведена, је контроверзна тачка између различитих филозофских школа.

За један од првих проблема се сматрало да је недлучив, у другом смислу израза, је била група проблема речи, први пут објављена од стране Макса Дена 1911, који пита да ли финално презентована група за коју не постоји алгоритам да одлучи да ли су све речи исте. Ово је показано у случају 1952.

Комбиновани рад Гедел и Паула Коена је дао два конкретна примера неодлучиве наредбе (у првом смислу те речи): Хипотеза континуума не може бити ни доказана ни демантована у ЗФЦ (стандардна Аксиоматизација теорије скупова), а аксиом избора не може бити ни доказан ни демантован у ЗФ (што су сви ЗФК аксиоми осим аксиома избора). Ови резултати не захтевају теорему некомплексности. Гедел је доказао 1940. да се ниједна од ових изјава не може  оповргнути у ЗФ или ЗФК скупу теорија.  1960, Коен је доказао да није доказиво ни из ЗФ, и  да континуум хипотеза не може бити доказана од ЗФЦ.

1970. Руски математичар Јуриј Матијашевић је показао да  се Хилбертов Десети проблем, постављен 1900. као изазов следећег века математичара, не може решити. Хилбертов  изазов тражи алгоритам који проналази сва решења у Диафонтинове једначине. Диафонтинова једначина је општији случај Ферманове последње теореме; тражимо целе корене полинома у било којем  броју варијабли са целим коефицијентима. Пошто имамо само једну једначину, али n променљивих, бесконачно много решења постоје (и да су лаки за налажење) у комплексној равни; Међутим, проблем постаје немогућ ако су решења  ограничена само на вредности целих бројева. Матијашевић је показао овај проблем да буде нерешен преко мапирања Диафонтинове једначинеса рекурзивним небројивим скупом и позивајући се на Геделову теорему непотпуности.

 1936, Алан Тјуринг је доказао да је халтинг проблем питање да ли се или не зауставља Тјурингова машина  на датом програму-је неодлучив, у другом смислу речи. Овај резултат је касније генерализован од стране  Рајсове теореме.

1973, Белоглави проблем у групи теорија је представљен као неодлучив, у првом смислу речи, у стандрадном сету теорија.

1977, Парис и Харингтон су доказали Парис-Харингтонов принцип, верзију Рамзијеве теореме, је неодлучив у аксиматизацији аритметике дате од стране Пеанових аксиома али може бити доказан тачним у великим системима аритметике другог-реда.

Крускалова теорема дрвета, која има примену у рачунарској науци, је такође неодлучив од Пеано аксиома, али доказива у теорији скупова. У ствари Крускала теорема дрвета (или његов коначни облик) је неодлучив у многим јачим системима кодификације принципа прихватљива на основу филозофије математике названа предикативизам.

Гудстаинова теорема је наредба о Рамзијевој теорији природних бројева коју су Кирби и Парис показали као неодлучиву у Пеано аритматици.

Грегори Чаитин производи неодлучиве наредбе у алгоритмичкој теорији информација и доказаоје  још једану непотпуност теореме у том окружењу. Чаитинова теорема тврди да за сваку теорију која се  може представити довољно аритметички, постоји горња граница с таква да се не може одређени број доказати у тој теорији да има Колмогрову комплексност већу од с. Док Геделова теорема се односи на парадокс лажи, Чаитинов резултат је повезан са Беријевим парадоксом.

2007, истраживачи Курц и Симон, радећи на ранијем раду Џона Конвеја 1970-те, доказали су да је природна генерализација Колацовог проблема неодлучива.

Види још

• Entscheidungsproblem