Kurt Gödel
A démontré que les mathématiques ne peuvent pas tout trancher sur elles-mêmes, à l'aide d'un procédé de codage qui est l'idée même derrière les programmes traités comme des données.
Kurt Gödel (1906–1978) publie en 1931 les deux théorèmes d'incomplétude qui mettent fin à l'espoir de Hilbert d'un fondement complet et démontrablement non contradictoire pour les mathématiques. C'est la méthode, plus que le résultat, qui en fait une figure de l'informatique autant que des mathématiques : la numérotation de Gödel code formules et démonstrations sous forme d'entiers, si bien qu'un système formel peut énoncer des choses sur ses propres théorèmes depuis l'intérieur. Représenter un programme comme une donnée qu'un autre programme peut lire, c'est exactement la même manœuvre, quinze ans avant la première instruction stockée.
En 1934, il définit aussi les fonctions générales récursives, l'un des trois formalismes de la calculabilité qui se sont révélés équivalents. Il ne croyait pourtant pas à la thèse de Church avant d'avoir lu l'article de Turing — c'est l'image de la machine, et non le lambda-calcul, qui l'a convaincu que la définition était la bonne. Une lettre à von Neumann de 1956 pose par ailleurs une question qui revient pour l'essentiel à P contre NP, quinze ans avant que quiconque d'autre ne la formule.