Entscheidungsproblem (německý výraz pro „rozhodovací problém“) je úloha, kterou poprvé předložil německý matematik David Hilbert roku 1928. Ptá se, existuje-li postup (algoritmus), který by uměl rozhodnout, jestli je dané matematické tvrzení v daném formálním jazyce pravdivé nebo nepravdivé.
Alonzo Church (1936) a Alan Turing (1937) nezávisle na sobě dokázali, že takový algoritmus neexistuje.
Zdroj
Poslední aktualizace obsahu: 2024-03-25 16:34:39
Zdroj: Wikipedia (autoři článku Entscheidungsproblem)
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.