Entscheidungsproblem: razlika između inačica
Nema sažetka uređivanja |
m →top: točke u wikipoveznice s godinama |
||
| Redak 1: | Redak 1: | ||
U [[matematika|matematici]], '''''Entscheidungsproblem''''' ([[Njemački jezik|njem]]. za '[[problem odluke]]') je izazov koji je postavio [[David Hilbert]] [[1928]] |
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 "istina" ili "laž", ovisno o tome je li tvrdnja istinita ili lažna. Program ne treba opravdati svoj odgovor, niti pružiti dokaz, važno je jedino da uvijek da 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. |
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 "istina" ili "laž", ovisno o tome je li tvrdnja istinita ili lažna. Program ne treba opravdati svoj odgovor, niti pružiti dokaz, važno je jedino da uvijek da 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. |
||
Posljednja izmjena od 22. ožujka 2021. u 00:56
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, niti pružiti dokaz, važno je jedino da uvijek da 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 neovisno objavili 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.
