Entscheidungsproblem

In de wiskunde en informatica is het zogeheten Entscheidungsproblem (Duits voor 'beslissingsprobleem') een uitdaging van David Hilbert in 1928.^[1] Het Entscheidungsproblem vraagt om een algoritme dat als invoer een uitspraak in een eerste-ordelogica (eventueel met een eindig aantal axioma's in plaats van de gebruikelijke axioma's van de eerste-ordelogica) krijgt en antwoordt met "ja" of "nee" al naargelang de uitspraak universeel geldig is of niet, dat wil zeggen, geldig in elke structuur die voldoet aan de axioma's. Vanwege de Volledigheidsstelling van Gödel is een uitspraak slechts dan universeel geldig als hij kan worden afgeleid uit de axioma's, zodat het Entscheidungsproblem ook kan worden gezien als de vraag naar een algoritme om te beslissen of een bepaalde uitspraak bewijsbaar is vanuit de axioma's met behulp van de regels van de logica.

In 1936 publiceerden Alonzo Church en Alan Turing onafhankelijk van elkaar artikelen^[2] die aantonen dat een algemene oplossing voor het Entscheidungsproblem niet mogelijk is, ervan uitgaande dat het intuïtieve begrip 'effectief berekenbaar' gedekt wordt door functies die berekenbaar zijn door een turingmachine. Deze veronderstelling is nu bekend als de Church-Turing-hypothese.

1. ↑ Hilbert en Ackermann
2. ↑ Churchs artikel werd op 19 april 1935 aan de American Mathematical Society aangeboden en gepubliceerd op 15 april 1936. Turing, die aanzienlijke vooruitgang had gemaakt bij het schrijven van zijn eigen resultaten, was teleurgesteld om te horen van het bewijs van Church bij de publicatie daarvan (zie de correspondentie tussen Max Newman en Church in Alonzo Church papers). Turing voltooide snel zijn artikel en publiceerde het vlug; het werd op 28 mei 1936 ontvangen door de Proceedings of the London Mathematical Society, gelezen op 12 november 1936 en gepubliceerd in reeks 2, deel 42 (1936-7); het verscheen in twee delen: in deel 3 (pagina's 230-240), uitgegeven op 30 november 1936 en in deel 4 (pagina 241-265), uitgegeven op 23 december 1936; Turing voegde nog correcties toe in deel 43 (1937) blz. 544-546. Zie voetnoot eind Soare. 1996