Kurt Gödel
Bewies, dass die Mathematik nicht alles über sich selbst entscheiden kann — mit einem Kodierungstrick, der die eigentliche Idee hinter Programmen als Daten ist.
Kurt Gödel (1906–1978) veröffentlichte 1931 die beiden Unvollständigkeitssätze, die Hilberts Hoffnung auf eine vollständige und beweisbar widerspruchsfreie Grundlage der Mathematik beendeten. Was ihn ebenso sehr zu einer Figur der Informatik wie der Mathematik macht, ist die Methode: Die Gödelnummerierung kodiert Formeln und Beweise als ganze Zahlen, sodass ein formales System von innen heraus Aussagen über seine eigenen Sätze treffen kann. Ein Programm als Daten darzustellen, die ein anderes Programm lesen kann, ist genau dasselbe Manöver — fünfzehn Jahre vor dem ersten gespeicherten Befehl.
1934 definierte er zudem die allgemein-rekursiven Funktionen, eines von drei Berechenbarkeitsmodellen, die sich später als gleichwertig erwiesen. Trotzdem glaubte er Churchs These erst, nachdem er Turings Arbeit gelesen hatte — es war das Bild der Maschine, nicht der Lambda-Kalkül, das ihn von der Richtigkeit der Definition überzeugte. Ein Brief an von Neumann von 1956 formuliert zudem im Kern die Frage P versus NP, fünfzehn Jahre bevor sie sonst jemand aufschrieb.