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.
Nedovršeni članak Entscheidungsproblem koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
