Kurt Gödel
Proved mathematics cannot settle everything about itself, using an encoding trick that is the whole idea behind treating programs as data.
Kurt Gödel (1906–1978) published the two incompleteness theorems in 1931, ending Hilbert's hope of a complete and demonstrably consistent foundation for mathematics. It is the method, rather than the result, that makes him a figure in computing as much as in mathematics: Gödel numbering encodes formulas and proofs as integers, so that a formal system can make statements about its own theorems from the inside. Representing a program as data that another program can read is the same manoeuvre, arriving fifteen years before the first stored instruction.
In 1934 he also defined the general recursive functions, one of the three models of computability that turned out to coincide. Even so, he did not accept Church's thesis until he had read Turing's paper — it was the picture of a machine, not the lambda calculus, that convinced him the definition was the right one. A 1956 letter to von Neumann poses what is essentially P versus NP, fifteen years before anyone else wrote it down.