Hilbert and his famous problem

In 1936 mathematics was changing profoundly, thanks to Turing and his fellow revolutionaries Gödel and Church. Older views about the nature of mathematics, such as those powerfully advocated by the great mathematician David Hilbert, were being swept away, and simultaneously the foundations for the modern computer era were being laid. These three revolutionaries were also catching the first glimpses of an exciting new world—the hitherto unknown and unimagined mathematical territory that lies beyond the computable. In the 1930s a group of iconoclastic mathematicians and logicians launched the field that we now call theoretical computer science. These pioneers embarked on an investigation to spell out the meaning and limits of computation. Pre-eminent among them were Alan Turing, Kurt Gödel, and Alonzo Church. These three men are pivotal figures in the story of modern science, and it is probably true to say that, even today, their role in the history of science is underappreciated. The theoretical work that they carried out in the 1930s laid the foundations for the computer revolution, and the computer revolution in turn fuelled the rocketing expansion of scientific knowledge that characterizes modern times. Previously undreamed of number-crunching power was soon boosting all fields of scientific enquiry, thanks in large part to these seminal investigations. Yet, at the time, Turing, Gödel, and Church would have thought of themselves as working in a most abstract field, far flung from practical computing. Their concern was with the very foundations of mathematics. Kurt Gödel (Fig. 7.1), a taciturn 25-year-old mathematician from Vienna University, ushered in a new era in mathematics with his 1931 theorem that arithmetic is incomplete. In a sentence, what Gödel showed is that more is true in mathematics than can be formally proved. This sensational result shocked, and even angered, some mathematicians. It was thought that everything that matters ought to be provable, because only rigorous proof by transparent and obvious rules brings certainty.