1900'de Paris'te David Hilbert matematiğin 23 büyük sorununu sıraladı. Çekirdek kaygı şuydu: matematik, sağlam aksiyomlardan yola çıkıp her doğru önermeyi sonlu sayıda mekanik adımla kanıtlayabileceğimiz bir sistem üzerine kurulabilir mi? Russell ve Whitehead'in "Principia Mathematica" (1910–1913) bu programın somut girişimiydi: bin sayfa boyunca sembol manipülasyonuyla aritmetiği mantığa indirgemeye çalıştılar. Hilbert 1920'lerde programı netleştirdi — matematik tutarlı, tam ve karara-bağlanabilir olmalıydı.

25 yaşında, Viyana Üniversitesi'nde doktorasını yeni bitirmiş Kurt Gödel, 1931'de "Monatshefte für Mathematik und Physik" dergisinde 25 sayfalık bir makale yayımladı: "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I". İçinde iki teorem vardı. Birincisi: Peano aritmetiği gibi yeterince güçlü, tutarlı her formel sistemde, sistemin kendi araçlarıyla ne kanıtlanabilir ne de çürütülebilir ama yine de doğru olan önermeler vardır. İkincisi: Böyle bir sistem kendi tutarlılığını kendi içinde kanıtlayamaz. Yöntemi zarif ve sert: her matematiksel ifadeye bir tamsayı ("Gödel sayısı") atadı, böylece sistem kendi cümleleri hakkında konuşur hale geldi; sonra "bu cümle kanıtlanamaz" diyen bir cümle inşa etti. Cümle yanlışsa kanıtlanır; ama kanıtlandığı an sistemin tutarlılığı çöker. Demek ki doğru — ama kanıtlanamaz.

Sonuç sarsıcıydı. Hilbert programı bu haliyle imkânsızdı; matematik hiçbir zaman tek bir formel sistemde tamamıyla kapatılamayacaktı. Ama Gödel bir yıkıcı değil bir sınır-çizicidir: matematiğin yanlış ya da güvenilmez olduğunu söylemez; sınırlı sayıda kural üzerine kurulu hiçbir formel sistemin tüm matematiksel gerçeği kapsayamayacağını gösterir. Sezgi, yaratıcılık ve yeni aksiyom kabul etme — bu adımlar mekanikleştirilemez. John von Neumann sonradan "bu çalışma matematik ve mantık tarihinde benzersizdir" diyecekti.

Gödel'in tekniği — özyineli sayma, kendine-gönderme, biçimsel sistemler hakkında biçimsel akıl yürütme — beş yıl sonra Alan Turing'in elinde "hesaplanabilirlik" kavramına dönüştü. "Karar verme problemi"nin çözümsüz olduğunu gösteren Turing makinesi, modern bilgisayarın kuramsal temeli oldu. Böylece eksiklik teoremleri yalnızca matematik felsefesinin değil, bilgisayar bilimi, yapay zekâ tartışmaları ve zihin felsefesinin de doğum belgesi haline geldi: Penrose'un "insan zihni bir algoritma değildir" iddiasından modern kanıt asistanlarına kadar tartışma hâlâ açık.