Entscheidungsproblem

Entscheidungsproblem je matematický problém, který spočívá v rozhodnutí, zda existuje algoritmus, který dokáže rozhodnout, zda je daná formule výrokové logiky platná nebo neplatná. Otázka Entscheidungsproblemu je úzce spjata s algoritmickou teorií, zvláště s teorií výpočetnosti. Byl představen v roce 1928 matematikem Davidem Hilbertem jako jeden z 23 problémů matematiky. Pojetí Entscheidungsproblemu bylo formalizováno v roce 1936 logikem Alonzo Church a následně také matematikem Emilem Postem ve svých nezávislých pracích. Church ukázal, že Entscheidungsproblem je nerozhodnutelný, tedy že žádný takový algoritmus neexistuje. Tento výsledek byl posílen v roce 1936 Alanem Turingem, který ukázal, že i určování zastavení Turingova stroje je nerozhodnutelný problém. Entscheidungsproblem měl obrovský vliv na rozvoj teorie výpočetnosti a otevřel cestu k objevu dalších nerozhodnutelných problémů. Je považován za jeden z nejdůležitějších matematických problémů 20. století a jeho studium bylo klíčové pro vytvoření teoretického základu pro moderní informatiku.