Neodlučiv zadatak

U teoriji usklađenosti i teoriji kompleksnosti, neodlučiv zadatak je problem odlučivanja za koji se zna da je nemoguć konstruisati u jednom algoritmu koji uvek dovodi do tačno da-ili-ne odgovora.

Problem odluke je bilo koje proizvoljno da-ili-ne pitanje nad beskonačnim skupom unosa. Zbog toga, tradicionajlno je definisati problem jednakosti kao skup unosa kojima problem vraća da. Ovi unosi mogu biti prirodni projevi, ali takođe i druge vrednosti neke druge vrste, kao što su stringovi formalnog jezika. Koriteći neko kodiranje, kao što je Gedelovo numerisanje, stringovi mogu biti kodirani kao prirodni brojevi. Zato, problem odluke neformalno je formulisan u smislu formalnog jezika koji je jednak skupu prirodnih brojeva. Da bi se zadržala formalna definicija jednostavnom, formulisano je u smislu podrgrupe prirodnih brojeva.

Formalno, problem odluke je podgrupa prirodnih brojeva. Odgovarajući neformalni problem je odlučivanje da li je dati broj u grupi. Problem odluke A se naziva odlučiv ili efektivno rešiv ako je A rekurzivni skup. Za problem se kaže da je delimično odlučiv, polu-odlučiv, rešiv ili dokaziv ako je A rekurzivno numerisana grupa. Ovo znači da postoji algoritam koji se zaustavlja na kraju kada je odgovor da ali može da ide do beskonačnosti ako je odgovor ne. Delimično odlučivi problemi i ostali problem koji nisu odlučivi se nazivaju nedolučivim. 

U teoriji usklađenosti

U teoriji usklađenosti, halting problem je problem odlučivanja koji može početi ovako :

S obzirom na opis proizvoljnog programa i završnog unosa, odlučiti se da li će program završiti sa radom ili će raditi zauvek.

Alan Tjuring je dokazao 1936 da generalni algoritam koji radi na Tjuringovoj mašini koji rešava halting problem za sve moguće unose parova programa koji su neophodni, ne može postojati. Dakle, halting problem je neodlučiv za Tjuringove mašine.

Odnos sa Gedelovom teoremom nepotpunosti

Koncepti prikupljeni preko Gedelove teoreme o nepotpunosti su veoma slični onima koji su prikupljeni preko halting problema, i dokazi su veoma slični. U stvari, slabija forma od Prve Teoreme Nepotpunosti koja je laka posledica neodlučivosti halting problema. Ova slabija forma razlikuje se od standardne naredbe teoreme nepotpunosti tvdeći da je kompletan, dosledan i zvučno aksiomatizovan od svih izjava otprilike prirodni brojevi su nedostižni. "Zvučni deo" je slaba tačka: to znači da me zahtevamo aksiomatski sistem da bi dokazali tačne naredba o prirodnim brojevima. Važno je posmatrati da je izjava standardne forme Gedelove teoreme o nepotpunosti potpuno neupućena u pitanje tačnosti, ali se samo brine od problemu da li može biti dokazan. 

Slabija forma teoreme može biti dokazana preko neodlučivosti halting problema kao što sledi. Prepostavimo da imamo doslednu i kompletnu aksimatizacija svih tačnih naredbi logika prvog reda o prirodnim brojevima. Onda možemo napraviti algoritam koji nabraja sve naredbe. Ovo znači da postoji algoritam N(n) koji, datu mu je prirodan broj n , izračunava logike prvog reda naredbi o prirodnim brojevima takve da, za sve tačne naredbe,  postoji najmanje jedno n takvo da N(n) daje tu naredbu. Sada pretpostavima da hoćemo da vidimo da li se algoritam sa reprezentacijom a zaustavlja pri unosu i . Znamo da naredba može biti izražena sa naredbom logike prvog reda, recimo H(a,i). Pošto je aksimatizacija kompletna sledi da ili je n takvo da je N(n) = H(a,i) ili postoji n' takvo da je N(n') =   ¬ H(a, i). Tako da ako bi izvršili iteraciju na n dok ne nađemo H(a,i) ili njegovu negaciju, uvek ćemo se zaustaviti. Ovo znači da nam ovo daje algoritam da odlučimo halting problem. Pošto znamo da ne postoji takav algoritam, sledi pretpostavka da  dosledna i kompletna aksimatizacija svih tačnih naredbi logika prvog reda o prirodnim brojevima mora biti netačna.

Primeri nedolučivih problema

Neodlučivi problemi mogu biti u vezi sa različitim temama, kao što je logika, apstrakne mašine ili topologija. Imati na imu da pošto ima nebrojivo mnogo neodlučivih problem, svaka lista, čak i deo beskonačne dužine, je bezpotrebno nedovršena. 

Primeri naredbi neodlučivosti

Postoje dva različita čula reči "neodlučivog" u savremenoj upotrebi. Prvi od njih je čulo koje se  koristi u odnosu na Gedelove teoreme, da se izjave bića ne mogu dokazati, ni opovrgnuti u određenom deduktivnom sistemu. Drugo čulo se koristi u odnosu na teoriju usklađenosti i ne odnosi se na izjave, nego  na probleme odluka, koje su usklađeni beskonačni skupovi pitanja kod kojih svaki zahteva da ili ne odgovor. Za takav problem se kaže da je neodlučiv ako nema za izračunivu funkciju koja tačno odgovara na svako pitanje o problemu u skupu. Veza između ova dva je da ako je problem odluka neodlučiv (u rekurzijsko teorijskom smislu) onda nema dosledno efektivnog formalnog sistema koji dokazuje da svako pitanje A u problemu ili "odgovor na A je da" ili "odgovor na  A je ne ".

Zbog ova dva značenja reči neodlučivog, termin nezavisan se ponekad koristi umesto neodlučivog za "ni nedokazivost ni opovrgljivost" smislu. Upotreba "nezavisni" je dvosmislena, svakako. To može da znači samo "nedokaziv", ostavljajući otvoreno pitanje da li  nezavisna naredba može pobiti.

Neodlučivost izjave u određenom deduktivnoj sistema , samo po sebi, ne odgovorara na pitanje da li je vrednost  naredbe istinita i dobro definisana , ili da li se može odrediti na drugi način. Neodlučivost samo znači da je poseban deduktivan sistem koji se smatra ne dokazuje istinu ili laž naredbe. Nezavisno da li postoje takozvane "apsolutno neodlučive" naredbe, čija je vrednost istinita nikada ne može biti poznata ili je loše navedena, je kontroverzna tačka između različitih filozofskih škola.

Za jedan od prvih problema se smatralo da je nedlučiv, u drugom smislu izraza, je bila grupa problema reči, prvi put objavljena od strane Maksa Dena 1911, koji pita da li finalno prezentovana grupa za koju ne postoji algoritam da odluči da li su sve reči iste. Ovo je pokazano u slučaju 1952.

Kombinovani rad Gedel i Paula Koena je dao dva konkretna primera neodlučive naredbe (u prvom smislu te reči): Hipoteza kontinuuma ne može biti ni dokazana ni demantovana u ZFC (standardna Aksiomatizacija teorije skupova), a aksiom izbora ne može biti ni dokazan ni demantovan u ZF (što su svi ZFK aksiomi osim aksioma izbora). Ovi rezultati ne zahtevaju teoremu nekompleksnosti. Gedel je dokazao 1940. da se nijedna od ovih izjava ne može  opovrgnuti u ZF ili ZFK skupu teorija.  1960, Koen je dokazao da nije dokazivo ni iz ZF, i  da kontinuum hipoteza ne može biti dokazana od ZFC.

1970. Ruski matematičar Jurij Matijašević je pokazao da  se Hilbertov Deseti problem, postavljen 1900. kao izazov sledećeg veka matematičara, ne može rešiti. Hilbertov  izazov traži algoritam koji pronalazi sva rešenja u Diafontinove jednačine. Diafontinova jednačina je opštiji slučaj Fermanove poslednje teoreme; tražimo cele korene polinoma u bilo kojem  broju varijabli sa celim koeficijentima. Pošto imamo samo jednu jednačinu, ali n promenljivih, beskonačno mnogo rešenja postoje (i da su laki za nalaženje) u kompleksnoj ravni; Međutim, problem postaje nemoguć ako su rešenja  ograničena samo na vrednosti celih brojeva. Matijašević je pokazao ovaj problem da bude nerešen preko mapiranja Diafontinove jednačinesa rekurzivnim nebrojivim skupom i pozivajući se na Gedelovu teoremu nepotpunosti.

 1936, Alan Tjuring je dokazao da je halting problem pitanje da li se ili ne zaustavlja Tjuringova mašina  na datom programu-je neodlučiv, u drugom smislu reči. Ovaj rezultat je kasnije generalizovan od strane  Rajsove teoreme.

1973, Beloglavi problem u grupi teorija je predstavljen kao neodlučiv, u prvom smislu reči, u standradnom setu teorija.

1977, Paris i Harington su dokazali Paris-Haringtonov princip, verziju Ramzijeve teoreme, je neodlučiv u aksimatizaciji aritmetike date od strane Peanovih aksioma ali može biti dokazan tačnim u velikim sistemima aritmetike drugog-reda.

Kruskalova teorema drveta, koja ima primenu u računarskoj nauci, je takođe neodlučiv od Peano aksioma, ali dokaziva u teoriji skupova. U stvari Kruskala teorema drveta (ili njegov konačni oblik) je neodlučiv u mnogim jačim sistemima kodifikacije principa prihvatljiva na osnovu filozofije matematike nazvana predikativizam.

Gudstainova teorema je naredba o Ramzijevoj teoriji prirodnih brojeva koju su Kirbi i Paris pokazali kao neodlučivu u Peano aritmatici.

Gregori Čaitin proizvodi neodlučive naredbe u algoritmičkoj teoriji informacija i dokazaoje  još jedanu nepotpunost teoreme u tom okruženju. Čaitinova teorema tvrdi da za svaku teoriju koja se  može predstaviti dovoljno aritmetički, postoji gornja granica s takva da se ne može određeni broj dokazati u toj teoriji da ima Kolmogrovu kompleksnost veću od s. Dok Gedelova teorema se odnosi na paradoks laži, Čaitinov rezultat je povezan sa Berijevim paradoksom.

2007, istraživači Kurc i Simon, radeći na ranijem radu Džona Konveja 1970-te, dokazali su da je prirodna generalizacija Kolacovog problema neodlučiva.

Vidi još

• Entscheidungsproblem