カート・ゲーデル
数学は自分自身についてすべてを決定できないことを証明した。その符号化の技法は、プログラムをデータとして扱う発想の核心でもある。
カート・ゲーデル（1906–1978）は1931年に2つの不完全性定理を発表し、数学の完全で、かつ無矛盾性が証明できる基礎づけというヒルベルトの希望を終わらせた。計算機科学でも重要人物である理由は、結果よりも方法にある。ゲーデル数は式や証明を整数に符号化し、形式体系が自分の定理について内側から語れるようにした。プログラムを、別のプログラムが読めるデータとして表現するのも同じ操作で、最初のプログラム内蔵方式の15年前に現れていた。
1934年には一般再帰関数も定義した。これは、結果的に一致した3つの計算可能性モデルの一つである。それでも、チューリングの論文を読むまでチャーチのテーゼを受け入れなかった。定義が正しいと彼を納得させたのは、ラムダ計算ではなく機械の描像だった。1956年のフォン・ノイマン宛の手紙は、実質的にP対NP問題を提起しており、他の誰かが書き留める15年前のことである。