Entscheidungsproblem
Hangi matematiksel önermelerin aksiyomlardan çıktığına mekanik bir yöntemle karar verilip verilemeyeceği sorusu; bilgisayarı kazara icat eden "hayır" cevabı.
David Hilbert ve Wilhelm Ackermann bunu 1928 tarihli mantık ders kitaplarında sordu: yüklem mantığındaki herhangi bir önermenin evrensel olarak geçerli olup olmadığına karar veren bir yöntem var mı? Hilbert "evet" bekliyordu. Programı matematiği tam, tutarlı ve karar verilebilir kılmayı hedefliyordu; üçüncüsü üçünün en somut olanıydı. Teoremleri çözen bir algoritma matematiği bir araştırma alanı olmaktan çıkarıp kol çevirmeye indirgerdi.
Cevap 1936'da iki yönden aynı anda geldi. Alonzo Church lambda kalkülüsünü, Alan Turing ise sonsuz kâğıt şeritli hayali bir makineyi kullandı. İkisi de: hayır. Mantığın bazı kısımları karar verilebilir (önerme mantığı doğruluk tablolarıyla öyledir) ama bir bütün olarak yüklem mantığı değildir.
Bilişim tarihi için önemli olan, Turing'in önce ne yapmak zorunda kaldığıdır. Hiçbir mekanik yöntemin yetmeyeceğini kanıtlamak için önce mekanik yöntemin ne olduğunu söylemek gerekir. Yazdığı tanım (bir şerit, bir kafa, bir durum tablosu) Turing makinesi oldu ve bilgisayarın ilk kesin tarifi çıktı. Bilgisayar, olumsuz bir sonucun yan ürünü olarak geldi.