Kurt Gödel
Bevisade att matematiken inte kan avgöra allt om sig själv, med ett kodningstrick som är själva idén bakom program som data.
Kurt Gödel (1906–1978) publicerade 1931 de två ofullständighetssatser som avslutade Hilberts hopp om en fullständig och bevisbart motsägelsefri grundval för matematiken. Metoden är det som gör honom till en datavetenskaplig gestalt och inte bara en matematisk: gödelnumrering kodar formler och bevis som heltal, så att ett formellt system kan uttala sig om sina egna satser inifrån sig självt. Att representera ett program som data som ett annat program kan läsa är exakt samma rörelse, femton år före den första lagrade instruktionen.
Gödel definierade 1934 också de allmänt rekursiva funktionerna, en av de tre formalismer för beräkningsbarhet som visade sig sammanfalla. Han trodde ändå inte på Churchs tes förrän han läst Turings uppsats — det var maskinbilden, inte lambdakalkylen, som övertygade honom om att definitionen var den rätta. Ett brev till von Neumann 1956 ställer dessutom en fråga som i allt väsentligt är P mot NP, femton år innan någon annan formulerade den.