Kurt Gödel
Dimostrò che la matematica non può decidere tutto su se stessa, con un trucco di codifica che è l'idea alla base del trattare i programmi come dati.
Kurt Gödel (1906–1978) pubblicò i due teoremi di incompletezza nel 1931, ponendo fine alla speranza di Hilbert di un fondamento della matematica completo e dimostrabilmente coerente. È il metodo, più che il risultato, a farne una figura dell'informatica oltre che della matematica: la numerazione di Gödel codifica formule e dimostrazioni come interi, così che un sistema formale possa fare affermazioni sui propri teoremi dall'interno. Rappresentare un programma come dati leggibili da un altro programma è la stessa manovra, arrivata quindici anni prima della prima istruzione memorizzata.
Nel 1934 definì anche le funzioni ricorsive generali, uno dei tre modelli di calcolabilità che si rivelarono coincidenti. Eppure non accettò la tesi di Church finché non lesse l'articolo di Turing: fu l'immagine di una macchina, non il calcolo lambda, a convincerlo che la definizione fosse quella giusta. Una lettera del 1956 a von Neumann pone in sostanza il problema P contro NP, quindici anni prima che qualcun altro lo mettesse per iscritto.