Kurt Gödel
Matematiğin kendisi hakkındaki her şeyi karara bağlayamayacağını kanıtladı; kullandığı kodlama hilesi, programları veri olarak görmenin de temel fikridir.
Kurt Gödel (1906–1978) iki eksiklik teoremini 1931'de yayımladı ve Hilbert'in matematik için tam ve kanıtlanabilir biçimde tutarlı bir temel umudunu bitirdi. Onu matematik kadar bilgisayar biliminin de figürü yapan sonuçtan çok yöntemidir: Gödel numaralandırması formülleri ve kanıtları tamsayı olarak kodlar; böylece biçimsel bir sistem kendi teoremleri hakkında içeriden ifade kurabilir. Bir programı başka bir programın okuyabileceği veri olarak göstermek aynı manevradır ve ilk saklı programlı makineden on beş yıl önce ortaya çıkmıştır.
1934'te, birbiriyle örtüştüğü sonradan anlaşılan üç hesaplanabilirlik modelinden biri olan genel özyinelemeli fonksiyonları da tanımladı. Buna rağmen Church tezini, Turing'in makalesini okuyana kadar kabul etmedi: tanımın doğru olduğuna onu lambda kalkülüsü değil, makine imgesi ikna etti. von Neumann'a yazdığı 1956 tarihli mektup, kabaca P'ye karşı NP sorusunu ortaya koyar; bunu başka biri yazıya dökmeden on beş yıl önce.