Entscheidungsproblem
De vraag of een mechanische procedure kan beslissen welke wiskundige uitspraken uit de axioma's volgen, en het nee dat per ongeluk de computer uitvond.
David Hilbert en Wilhelm Ackermann stelden haar in hun logicaleerboek van 1928: bestaat er een procedure die voor elke uitspraak uit de predicatenlogica beslist of ze universeel geldig is? Hilbert verwachtte van wel. Zijn programma wilde de wiskunde volledig, consistent en beslisbaar maken, en het derde punt was het meest tastbare. Een algoritme dat stellingen afhandelt had de wiskunde als onderzoeksveld overbodig gemaakt en tot ceremonieel draaien aan een slinger herleid.
Het antwoord kwam in 1936 uit twee richtingen tegelijk. Alonzo Church gebruikte het lambdacalculus, Alan Turing een gedachte machine met een eindeloze papieren band. Beiden zeiden nee. Delen van de logica zijn beslisbaar, zoals de propositielogica via waarheidstabellen, maar de predicatenlogica als geheel niet.
Wat voor de computergeschiedenis telt, is wat Turing eerst moest doen. Om te bewijzen dat geen mechanische procedure volstaat, moet je eerst zeggen wat een mechanische procedure is. De definitie die hij opschreef, een band, een kop en een toestandstabel, werd de Turingmachine en daarmee de eerste precieze beschrijving van wat een computer is. De computer kwam als bijproduct van een negatief resultaat.