Entscheidungsproblem: razlika između inačica

Izvor: Wikipedija
Izbrisani sadržaj Dodani sadržaj
m r2.7.2+) (robot Dodaje: sv:Avgörbarhetsproblemet
Addbot (razgovor | doprinosi)
m Bot: brisanje 13 međuwiki poveznica premještenih u stranicu d:q11030584 na Wikidati
Redak 8: Redak 8:
{{mrva-rač}}
{{mrva-rač}}
[[Kategorija:Teorija računanja]]
[[Kategorija:Teorija računanja]]

[[ar:مشكلة القرار (رياضيات)]]
[[ca:Entscheidungsproblem]]
[[cs:Entscheidungsproblem]]
[[en:Entscheidungsproblem]]
[[es:Entscheidungsproblem]]
[[fr:Problème de la décision]]
[[it:Entscheidungsproblem]]
[[pt:Entscheidungsproblem]]
[[ru:Проблема разрешения]]
[[simple:Entscheidungsproblem]]
[[sv:Avgörbarhetsproblemet]]
[[uk:Задача розв'язності]]
[[zh:可判定性]]

Inačica od 15. travnja 2013. u 08:25

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.

Nedovršeni članak Entscheidungsproblem koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.