Entscheidungsproblem: razlika između inačica
m robot Dodaje: cs:Entscheidungsproblem |
m robot Uklanja: de:Entscheidungsproblem |
||
Redak 11: | Redak 11: | ||
[[ca:Entscheidungsproblem]] |
[[ca:Entscheidungsproblem]] |
||
[[cs:Entscheidungsproblem]] |
[[cs:Entscheidungsproblem]] |
||
[[de:Entscheidungsproblem]] |
|||
[[en:Entscheidungsproblem]] |
[[en:Entscheidungsproblem]] |
||
[[es:Entscheidungsproblem]] |
[[es:Entscheidungsproblem]] |
Inačica od 3. studenoga 2009. u 15:38
U matematici, Entscheidungsproblem (njem. za 'problem odluke') je izazov koji je postavio David Hilbert 1928.
Entscheidungsproblem potražuje računalni program koji će uzeti kao ulaz opis formalnog jezika i matematičku tvrdnju u tom jeziku i vratiti kao izlaz "Istina" ili "Laž", ovisno o tome je li tvrdnja istinita ili lažna. Program ne treba opravdati svoj odgovor, ili pružiti dokaz, sve dok uvijek daje 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 objavili neovisne radove u kojima pokazuju da je nemoguće algoritamski odlučiti jesu li tvrdnje u aritmetici istinite ili lažne, te je stoga općenito rješenje Entscheidungsproblema nemoguće. Ovaj je rezultat poznat kao Church-Turingov teorem.