Kurt Gödel
Bewees dat de wiskunde niet alles over zichzelf kan beslechten, met een codeertruc die de kern is van het idee om programma's als data te behandelen.
Kurt Gödel (1906–1978) publiceerde in 1931 de twee onvolledigheidsstellingen, waarmee een einde kwam aan Hilberts hoop op een volledige en aantoonbaar consistente grondslag voor de wiskunde. Het is de methode, meer dan het resultaat, die hem tot een figuur in de informatica maakt, naast die in de wiskunde: de gödelnummering codeert formules en bewijzen als gehele getallen, zodat een formeel systeem van binnenuit uitspraken kan doen over zijn eigen stellingen. Een programma weergeven als data die een ander programma kan lezen is dezelfde zet, vijftien jaar vóór de eerste opgeslagen instructie.
In 1934 definieerde hij ook de algemeen recursieve functies, een van de drie berekenbaarheidsmodellen die uiteindelijk samenvielen. Toch aanvaardde hij de stelling van Church pas nadat hij het artikel van Turing had gelezen: het beeld van een machine, en niet de lambdacalculus, overtuigde hem dat de definitie klopte. Een brief aan von Neumann uit 1956 stelt in wezen de vraag P versus NP, vijftien jaar voordat iemand anders haar opschreef.