Popis neodlučivih problema

U teoriji izračunljivosti, neodlučiv problem je problem čiji jezik nije rekurzivan skup. Neformalnije, takve probleme općenito ne može riješiti računalo (vidi neodlučivost). Ovo je popis neodlučivih problema. Valja uočiti da postoji neprebrojivo mnogo neodlučivih problema, tako da ovaj popis nije nužno potpun. Iako neodlučivi jezici nisu rekurzivni, mogu biti podskup turing prepoznatljivih jezika.

Problemi povezani s apstraktnim strojevima

Problem zaustavljanja
Riceov teorem kaže da su sva netrivijalna svojstva računalnih programa neodlučiva.
Određivanje generira li kontekstno neovisna gramatika sve moguće stringove, ili je li nejednoznačna
Za dane dvije kontekstno neovisne gramatike, određivanje generiraju li isti skup stringova, ili generira li jedna podskup stringova koje generira druga, ili postoji li uopće zajednički string koji generiraju.

Drugi problemi

Postov problem korespondencije
problem riječi za grupe
problem riječi za određene formalne jezike
Wangovo popločenje
Kolmogorovljeva složenost
Penroseovo popločenje
Određivanje rješivosti diofantske jednadžbe, poznato kao Hilbertov deseti problem
Određivanje homeomorfnosti dvaju konačnih simplicijalnih kompleksa
Određivanje je li fundamentalna grupa konačnog simplicijalnog kompleksa trivijalna

Izvori

Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. Appendix C uključuje nemogućnost algoritama koji odlučuju sadrži li gramatika nejednoznačnosti, te nemogućnost verificiranja ispravnosti programa algoritmom kao primjer problema zaustavljanja.

Moret, B. M. E. (1991). Algorithms from P to NP, volume 1 - Design and Efficiency. Redwood City, California: Benjamin/Cummings Publishing Company, Inc. Raspravlja o neukrotivosti problema sa eksponencijalnim algoritmima u poglavlju 2, Mathematical techniques for the analysis of algorithms.