A digital drama of logical and tragic lives

Who invented computers? Martin Davis puts the question into context and attempts to answer it by looking at the work of logicians and mathematicians over the last three centuries, starting with Leibniz. His focus is very much on the logical foundations of computing with Turing's influence as crucial. This is in contrast with previous accounts which give more importance to von Neumann or J. Presper Eckert and John Mauchly with their highly engineered early machines, the decimal Eniac and later the binary Edvac.

The story that Davis tells is not new. There have been numerous renditions of how the history of mathematics and logic have led to the development of computers. He rightly says that credit cannot go to a single inventor. The contributions of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and von Neumann, which ultimately led to the universal Turing machine as a basis for a digital all-purpose computer, still make compelling reading, especially when described by a distinguished logician like Davis. The extra dimension that this book provides comes from the personal contact the author has had with many of the players in this drama. For example, his boss during a summer job at Bell Laboratories was Claude Shannon, who showed that a Turing machine could be represented by only two states, laying the foundations for the familiar binary representation computers now use. As a young man, Davis attended lectures by Gödel and was at the Princeton Institute of Advanced Studies a few years after Turing had been there. At Princeton, Davis probably produced the first computer-generated mathematical proof using the institute's computer. His PhD supervisor was Alonzo Church, who along with Turing is credited with the thesis that the Turing machine, or, equivalently the lambda calculus, mathematically defines what we mean by an algorithmic procedure.

Taking up the story chronologically, Davis describes Leibniz's dream to find a true alphabet of human thought and the first steps he took in defining one. He gives a nice example of an infinite series Leibniz discovered that adds up to the area of a circle of unit diameter and examines Leibniz's relationship with his patrons. The idea of infinity turns out to be of great importance in this story and it recurs throughout the book. The next major step was the algebraisation of propositional logic undertaken by Boole. Then Frege took up the mantle with his introduction of universal and existential quantifiers that completed the picture for first-order predicate logic. Davis's apt example of a statement that can be formalised in Frege's system but not Boole's is "all failing students are either stupid or lazy". Frege used his system to establish the foundations of arithmetic, but these were seriously undermined by a letter from Russell setting out his eponymous paradox involving the set of all sets that are members of themselves. Russell admired Frege's intellectual honesty in admitting that the paradox had written off years of work. This is contrasted strongly with the view expressed by Michael Dummett on discovering Frege's virulently racist diary written in 1924, the year of his death. After Frege, we are treated to an outline of Cantor's contributions to studies of the infinite, in particular his diagonal method, which showed that there are different classes of infinity for natural and irrational numbers. This method would prove important 50 years later in Gödel's work.

Davis then discusses Hilbert's programme intended to put mathematics on firm foundations, using a series of problems defined in 1900, culminating in the Entscheidungsproblem , concerned the possible existence of a general algorithmic procedure for resolving mathematical questions. He then turns to Gödel's incompleteness theorem, which showed that there are true propositions expressible in a formal system that are not provable within it, and discusses the devastating effect it had on the mathematicians of the time. Von Neumann himself was the first to realise the consequences of the theorem, which effectively destroyed Hilbert's programme. The usual example given for such a proposition was Fermat's Last Theorem, but as that has now been disproved by another Princeton mathematician, Andrew Wiles, no one, not even Davis, seems to have found a suitable substitute. We finally reach Turing's monumental contribution: at the age of 24, he wrote his seminal paper "On computable numbers", which defined the Turing machine. No solution to the Entscheidungsproblem exists, since no Turing machine can be used to solve it.

A refreshing aspect of this book is that it does not eschew equations. Some things cannot be adequately described without recourse to mathematical notation and the foundations of computing is one of them.

Perhaps the most compelling chapter discusses the reasons behind the failure of the development of ACE, Turing's proposed computer which was to be built at the National Physical Laboratory. Turing's minimalist architecture for that machine foreshadows much later developments in microcoding and Risc chip technology. The Mark I in Manchester, which Turing nominally had some role in developing when he left the NPL, was firmly based on the von Neumann architecture, as are almost all processing chips today. Davis suggests that Turing's eccentricity, his homosexuality and, for obvious security reasons, the public ignorance of his work on the decryption of Enigma in the second world war, all contributed to his diminishing influence at the end of his tragic life. Davis correctly states that Turing was hounded to death by the establishment he had played such an important part in saving.

At the end of the book there is an interesting chapter on machine intelligence leading from Turing's own accounts of the possibility of chess-playing computers and his proposed test for determining intelligence by means of a dialogue with a machine that is indistinguishable from one with a human interlocutor. This leads to Davis's differences with Roger Penrose about the significance of Gödel's theorem in the discussion of whether machine intelligence is really ever possible and some discussion of John Searle's philosophical arguments.

The Universal Computer is a very worthwhile book and can be recommended for any student of computing. The explanations are clear and the maths is always put into its political, historical and cultural context. It is essentially a very human story about the endeavours of an amazing collection of individuals, which is ultimately why it is so interesting.

Tony Valsamidis is senior lecturer in information systems, University of Greenwich.