Title: The Universal Computer
Author: Martin Davis
Davis, M. (2000). The Universal Computer: The Road from Leibniz to Turing, New York: Norton.
Davis, Martin(2000, 2012). The Universal Computer: The Road From Leibniz To Turing. New York: Norton
QA76.17 .D38 2000
Date Posted: May 2, 2013
A review by Reviewed by Brian E. Blank.
If you teach a course on number theory nowadays, chances are it will generate more interest among computer science majors than among mathematics majors. Many will care little about integers that can be expressed as the sum of two squares. They will prefer instead to learn how Alice can send a message to Bob without fear of eavesdropper Eve deciphering it. No doubt they would be surprised to see the theory of numbers described as a “purely theoretical science without practical applications” or, even more bluntly, as “useless”. Yet, those are exactly the assessments of number theory that were given by Uspensky and Heaslet in 1939 and by Hardy in 1940. It is with a sense of irony that we read these pronounce- ments now, knowing that the seeds of their contradiction had already been sown. Work that would lead to the modern digital computer was already under way.
The great theoretical advance that led to the modern computer may be traced to 1936 when Alan Turing formulated a highly original concept that would eventually be called the Turing machine. At the time, projects to build simpler computing devices were just about to begin. Between 1936 and 1939 the German engineer Konrad Zuse designed and constructed two experimental electro-mechanical digital computers, the Z1 and Z2. In 1937 Howard Aiken submitted to IBM a formal proposal titled Proposed Automatic Calculating Machine. The product of Aiken’s initiative, the Harvard Mark I (also known as the IBM Automatic Sequence Controlled Calculator) was placed in service in the spring of 1944. It is considered the first electro-mechanical number-crunching computer. Mechanical it certainly was. The 750,000 moving parts of Aiken’s machine are said to have produced a roar like that of a textile mill. Less than two years later, in February 1946, a computer known as the ENIAC was fully operational. This 30-ton behemoth, conceived and constructed by John Presper Eckert and John William Mauchly, is considered to be the first electronic computer. Electronic it certainly was. When the ENIAC went online, its 17,468 vacuum tubes are said to have dimmed lights throughout Philadelphia.
The Mark I and the ENIAC were both funded by the military for the purpose of doing numerical calculations vital to the war effort. With the conclusion of the war, seminumerical commercial applications such as accounting, scheduling, record-keeping, and billing were developed. As the computer rapidly evolved from its eponymous function, the list of tasks assigned to it swelled. Even tasks that do not involve a single computation have been taken over by the computer. Nowadays a book review, for example, is likely to be solicited by computer communication, composed, researched, spell-checked, and typeset on a computer, submitted by computer, and posted for access by a worldwide network of computers. Even the “printer’s proofs” might arrive in the form of a computer file.
The conversion of number theory from a “useless” pursuit to an applied science has been due in large part to an especially ironic consequence of the computer’s evolution: in order that we may securely rely on the computer for such noncomputational tasks as commerce, communication, and archiving, we must first enlist the theory of numbers to foil the computational power of the computer to decrypt. Like the sea change in number theory that it occasioned, the metamorphosis of the computer from number cruncher to all-purpose logic machine has been a profound transformation that is now taken for granted but was not originally transparent. Aiken, for example, did not recognize the transition in progress. “If it should turn out,” he wrote in 1956, “that the basic logics of a machine designed for the numerical solution of differential equations coincide with the logics of a machine intended to make bills for a department store, I would regard this as the most amazing coincidence I have ever encountered.”
Although the electronic digital computer is barely more than half a century old, its history has attracted a devoted following. For more than twenty years a scholarly journal, the Annals of the History of Computing, has chronicled the development of computing in minute detail. A steady stream of books—some erudite, some popular—has allowed engineers, historians, and journalists to delve into nearly every facet of the computer revolution. Martin Davis’s new book, The Universal Computer: The Road from Leibniz to Turing, is not like any of them.
Davis’s perspective is unique: he is concerned with the development of the computer as an engine of logic rather than as an instrument of calculation. As he explains in his introduction, “A computing machine is really a logic machine. Its circuits embody the distilled insights of a remarkable collection of logicians, developed over centuries. Nowadays, as computer technology advances with such breathtaking rapidity, as we admire the truly remarkable accomplishments of the engineers, it is all too easy to overlook the logicians whose ideas made it all possible. This book tells their story.”
One cannot imagine an author more qualified than Martin Davis for such an endeavor. Many Notices readers will be familiar with Davis from his contributions, both in research and exposition, to Hilbert’s tenth problem. Others will know him from his excellent text-books, which have become standard references of theoretical computer science. Those who keep track of awards will recognize him as the recipient of the Chauvenet, the Lester R. Ford, and the Leroy P. Steele Prizes. In addition to his credentials as distinguished logician and honored expositor, Davis is also a pioneer programmer who wrote code for both the Institute for Advanced Study computer, a historic machine that has been in the collection of the Smithsonian Institution since 1960, and for one of its clones, an Army Ordnance “johnniac-class” computer known as the ORDVAC. His engaging autobiographical sketch offers a rare glimpse of the programmer’s craft as it existed in 1951, when the state of the art amounted to five kilobytes of random access memory tenuously implemented as static charge on the surfaces of cathode-ray tubes.
In The Universal Computer Davis begins his tale with Leibniz, whose proposal for an algebra of logic is the point of departure on the road to the universal Turing machine. It is indicative of the enthusiasm with which Davis infuses his writing that where others see “fragmentary anticipations of modern logic”, Davis perceives “a vision of amazing scope and grandeur.” As Davis tells the story, Leibniz “dreamt of an encyclopedic compilation, of a universal artificial mathematical language in which each facet of knowledge could be expressed, of calculational rules which would reveal all the logical interrelationships among these propositions. Finally, he dreamed of machines capable of carrying out calculations, freeing the mind for creative thought.” The chapter is called “Leibniz’s Dream”, and that dream is a sort of North Star toward which the axis of each subsequent chapter points.
Following the style of “Leibniz’s Dream”, Davis devotes each of the next six chapters to the life and contributions of a leading logician: the list comprises Boole, Frege, Cantor, Hilbert, Gödel, and Turing. In making these choices, Davis has taken great care not to stray from the road to Turing. Logicians such as Brouwer and Russell are discussed in a fitting amount of detail, but De Morgan, Peano, and Skolem are mentioned only in passing, while Peirce, Schröder, Löwenheim, and Zermelo are not mentioned at all. So coherent is the narrative, however, that one has the illusion that one is reading the entire history of mathematical logic without any discontinuity in its evolution.
Through the first seven chapters the principal logical concepts of each protagonist are presented at a level that is appropriate for a general audience. It was a shrewd idea to embed these discussions inside capsule biographies of the logicians. This stratagem serves both to lighten the load of the reader who has no prior training in mathematical logic and to maintain the interest of the more experienced reader who is already familiar with the logical theories. It is true that standard biographies exist, and, with few exceptions, Davis does not go beyond them. Nevertheless, most readers will welcome his lively, informal synopses, replete as they are with amusing anecdotage. Perhaps the best of these involves Davis himself. Driving in Princeton with his wife, Virginia, he happened to pass the town’s most famous denizen, dressed like a tramp, walking with Gödel, nattily attired in suit and tie, briefcase in hand. “Einstein and his lawyer,” quipped Virginia. Naturally Gödel and Turing provide ample grist for the raconteur’s mill, but the fact is, every one of the featured logicians, the dusty Victorian pedant George Boole included, makes for a fascinating character study.
By the end of the seventh chapter, Davis’s readers will have learned about Boole’s algebra of logic, Frege’s Begriffsschrift , the Continuum Hypothesis, Gödel’s theorem on undecidable propositions, Hilbert’s Entscheidungsproblem , and Turing machines. At this point the timeline of the narrative has reached the end of World War II: all the developments in logic that are needed for the universal computer are in place, and their physical realizations are literally on the drawing board. In keeping with the chronology, Davis interrupts Turing’s biography to direct his attention to the engineers who would take the next steps toward the fulfillment of Leibniz’s dream. He begins his eighth chapter, “Making the First Universal Computers”, with thumbnail summaries of the contributions of the hardware pioneers Aiken, Atanasoff, Eckert, and Mauchly. It may be argued that these sketches are too brief, but in fact these hardware implementations fall outside the scope of Davis’s book. That said, I do find it surprising that Davis accords only one paragraph to Claude Shannon, whose 1938 master’s thesis in electrical engineering showed how to apply Boole’s algebra of logic to electronic switching circuits. The complete omission of Konrad Zuse is even more puzzling. In any event, the early history of computing is well provided for.
The historian Tom Settle has used the death of Galileo to illustrate how elusive historical truth can be. Despite an authentic death certificate that cites the evening of January 8, 1642, calendrical variation renders uncertain which one of four days is actually being specified. It is tempting to believe that more recent events must prove less troublesome. Indeed, the authors of a new book about computer scientists assert that “in most sciences the seminal thinkers lived in the remote past. To uncover what they did…we must scavenge in the historical record, picking among scraps of information, trying to separate facts from mythology. Computer science is different.” Regrettably, this plausible claim is not true. Above all, priority for one of the indispensable principles of modern computing, the stored program concept, has proved to be hopelessly and bitterly controversial.
In a nutshell, John von Neumann, who worked with Eckert and Mauchly, has often been given full credit for the stored program concept because he advanced the idea in a widely circulated report that he released under his name alone. Later both Eckert and Mauchly disputed the importance of von Neumann’s contribution. Their position is argued eloquently in a recent book about the ENIAC. Although Davis admits that the question of von Neumann’s personal contribution “will probably never fully be resolved,” he seems to come down squarely on von Neumann’s side. His analysis is interesting, but in the big picture this acrimonious squabble lacks significance. For one thing, Zuse has a real claim to priority: he unmistakably proposed the stored program concept as early as 1936 (but did not pursue it, since it would have been of little use on his slow, mechanical memory machines). More importantly, the issue is something of a red herring. Davis himself first advanced this point of view in a 1987 article that may be regarded as a skeleton of the book under review. “What was really revolutionary about these machines,” Davis points out, “was their universal all-purpose character, while the stored program aspect was only a means to an end.”
That Turing had nailed the future of computing before all the others may be seen from several of his statements, of which the following from 1945 is typical: “There will positively be no internal alterations to be made even if we wish suddenly to switch from calculating the energy levels of the neon atom to the enumeration of groups of order 720.” In 1948 he put it this way: “We do not need to have an infinity of different machines doing different jobs. A single one will suffice.” Turing did not refer to this single machine by the misnomer that others with narrower visions were already using: he called it the universal machine, and, as Davis compellingly demonstrates, it was Turing’s conception of the universal machine that influenced von Neumann.
When a distinguished expert offers a popular exposition of his subject, we greet the effort with keen anticipation. That is all the more true when the writer is as skilled as Martin Davis. It is a pleasure to report that in this case our anticipation is richly rewarded. Not only does Davis captivate us with a fascinating story, he caps it with a moral as well. I have echoed this moral at the beginning of this review, but it is worth repeating in the author’s own words: “This book underscores the power of ideas and the futility of predicting where they will lead.” Seldom has this point been made so well. Read this book and enjoy.