More actions
Bot: Automatski unos stranica |
m Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige) |
||
| Redak 23: | Redak 23: | ||
== Izvori == | == Izvori == | ||
{{ | {{Citiranje knjige | ||
| last = Brookshear | | last = Brookshear | ||
| first = J. Glenn | | first = J. Glenn | ||
| Redak 32: | Redak 32: | ||
}} 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. | }} 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. | ||
{{ | {{Citiranje knjige | ||
| last = Moret | | last = Moret | ||
| first = B. M. E. | | first = B. M. E. | ||
Posljednja izmjena od 17. studeni 2021. u 23:47
 |
Predloženo je da se ovaj članak spoji s člankom Neodlučivost. (Rasprava) |
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
Lua error in Modul:Citation/CS1 at line 4096: data for mw.loadData contains unsupported data type 'function'. 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.
Lua error in Modul:Citation/CS1 at line 4096: data for mw.loadData contains unsupported data type 'function'. Raspravlja o neukrotivosti problema sa eksponencijalnim algoritmima u poglavlju 2, Mathematical techniques for the analysis of algorithms.