The Universal Computer: The Road from Leibniz to Turing

Open a typical history of computing, and you will likely find the names of engineers such as Babbage, Atanasoff, Zuse, Aiken, Mauchly, and Eckert. Why then does Martin Davis's The Universal Computer contain chapters on the logicians Leibniz, Boole, Frege, Cantor, Hilbert, Gödel, and Turing? Because, Davis argues, the old histories tell only half of the story: what the engineers were able to do was to create a universal Turing machine, and it is the idea of a universal computing machine which is truly revolutionary. His book tells the story of this idea.

The story begins with Leibniz. As a student, while learning Aristotle, Leibniz began to formulate what he called "his wonderful idea": to find a way to symbolize all ideas, in such a way that one would then be able to calculate using the symbols. In a sense, his hope was to do for all human thought what algebra had done in mathematics. It is unclear how much progress Leibniz made towards this goal, but in his published works, at least, it was minimal.

The first major advance came when George Boole developed an algebra of logic. His system was able to capture a fair amount of what might be called everyday reasoning, but it still had limitations. Gottlob Frege was able to address these limitations, and in so doing, created essentially the system of first-order logic which we use today. In terms of Leibniz's dream, however, it was not possible to "calculate" easily with Frege's system: no procedure was known for determining whether a given statement is true or false.

The following chapter on Cantor is labelled a "Detour through Infinity." It presents Cantorian set theory, including his diagonal argument and a discussion of the Continuum Hypothesis, but Davis only hints at the reason for this detour. The main thread reappears with Hilbert, as the problem of finding a finite procedure for determining the validity of an expression in first-order logic becomes known as Hilbert's Decision Problem.

Gödel also appears as something of a detour. He did substantial work on other problems from Hilbert, particularly the unprovability of the consistency of arithmetic and the relative consistency of the Continuum Hypothesis. But it took Turing to answer Hilbert's Decision Problem in the negative: no finite procedure can determine the validity of any first-order sentence. In order to do this, Turing needed to conceptualize what any "finite procedure" might look like, and in so doing, he developed what have become known as Turing machines. He then realized that a Turing machine could be created which would mimic the actions of any Turing machine; thus appeared the idea of a universal computer.

Where, then, do Cantor and Gödel fit? Turing used both Cantor's diagonal argument and coding techniques similar to Gödel's in his solution of the Decision Problem. Thus the intellectual history of the universal Turing machine is most clearly read backwards: Turing used ideas from Cantor and Gödel to solve Hilbert's problem in Frege's system of logic which improved Boole's. And all of these were attempts in one way or another to fulfill Leibniz's dream of a calculation system for human reasoning.

It may be clearer in hindsight, but the story is much more interesting when read chronologically, particularly as Davis has written it. Historical background, important secondary characters (particularly Bertrand Russell and John von Neumann), and Davis's own encounters with these ideas and some of the people involved all contribute to a rich and rewarding reading experience. Among its unexpected pleasures are several odd little connections, such as Gödel's essay on Russell which argues that Leibniz must have made more progress towards his calculus of reasoning than we see in his publications, or the founding of Göttingen (Hilbert's home for forty-eight years) by the son of one of Leibniz's patrons.

Read this book. Have your friends read it. And remember both the logicians and the engineers the next time you boot up your universal computer.

Mark Johnson (johnsonm@central.edu) is Associate Professor of Computer Science and Mathematics at Central College in Pella, IA.