Kurt Gödel (1906–1978) lived half his adult life during the computer era – in fact, virtually at the epicenter of the early development of the computer. Yet we have no evidence that the great logician took a serious interest in the nature, workings, power, or limitations of the beast. Nevertheless, I shall argue that Gödel's work has had many and crucial connections to computation for a number of reasons:

• The incompleteness theorem (Gödel, 1931) started an intellectual Rube Goldberg that eventually led to the computer.

• Gödel's early work contains the germs of such influential computational ideas as arithmetization and primitive recursion.

• In a 1956 letter to John von Neumann (see Sipser, 1992), which was not widely known for three decades, Gödel proposed a novel quantitative version of Hilbert's program that turned out to be precisely the P versus NP question.

• Negative results, of which the incompleteness theorem is an ideal archetype, constitute an important and distinguishing tradition in computer science research.

Sections 7.1 and 7.2 recount how the incompleteness theorem motivated a number of mathematicians during the 1930s to further sharpen the result's negative verdict and establish that mathematics, besides being impossible to axiomatize, cannot even be mechanized (axiomatization being only one of the possible ways whereby mathematical thought can be mechanized). For this program to be carried out, however, computation had to be somehow defined, and those brilliant definitions – most notably Alan Turing's (1936) – were the mathematical precursors of the computer.