Razlika između inačica stranice »Entscheidungsproblem«

bez sažetka
m
U [[matematika|matematici]], '''''Entscheidungsproblem''''' ([[Njemački jezik|njem]]. za '[[problem odluke]]') je izazov koji je postavio [[David Hilbert]] [[1928]].
 
Entscheidungsproblem potražuje računalni program koji će uzeti kao ulaz opis [[formalni jezik|formalnog jezika]] i matematičku tvrdnju u tom jeziku i vratiti kao izlaz "Istinaistina" ili "Lažlaž", ovisno o tome je li tvrdnja istinita ili lažna. Program ne treba opravdati svoj odgovor, iliniti pružiti dokaz, svevažno je jedino dokda uvijek dajeda točan odgovor. Takav bi računalni program bio u mogućnosti odlučiti, na primjer, jesu li [[hipoteza kontinuuma]] ili [[Riemannova hipoteza]] istinite, čak i ako nije poznat dokaz ili opovrgavanje ovih tvrdnji.
 
1936. su [[Alonzo Church]] i [[Alan Turing]] objavilineovisno neovisneobjavili radove u kojima pokazuju da je nemoguće algoritamski odlučiti jesu li tvrdnje u [[aritmetika|aritmetici]] istinite ili lažne, te je stoga općenito rješenje Entscheidungsproblema nemoguće. Ovaj je rezultat poznat kao [[Church-Turingova teza|Church-Turingov teorem]].
 
{{mrva-rač}}
Anonimni suradnik