Entscheidungsproblem

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.

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.