Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The universal computer : the road from Leibniz to Turing
Davis M., A. K. Peters, Ltd., Natick, MA, 2011. 240 pp. Type: Book (978-1-466505-19-3)
Date Reviewed: Oct 1 2012

Davis states in the last chapter of this book that the “connection between logic and computation has been a principal theme of this book.” I’ve always been “in violent agreement” with those who assert that connection, but now my agreement is a hundredfold more informed. Examples constructed by the author and explained in this narrative history made many ultra-technical things clearer to me than they had ever been, including concepts such as Cantor’s transfinite arithmetic and diagonalization process, certain specifics of the Hilbert program, Gödel numbers, and Turing quintuples and machines. The subtitle’s “road from Leibniz to Turing” is traced in the chapter titles: “Leibniz’s Dream,” “Boole Turns Logic into Algebra,” “Frege: From Breakthrough to Despair,” “Cantor: Detour through Infinity,” “Hilbert to the Rescue,” “Gödel Upsets the Applecart,” “Turing Conceives of the All-Purpose Computer,” “Making the First Universal Computers,” and “Beyond Leibniz’s Dream.”

The brief epilogue should not be missed, nor the preface and introduction. Those I’ll call the protagonists--Leibniz, Boole, Frege, Cantor, Hilbert, Gödel, and the climactic hero Turing--are known to one extent or another from other sources that are largely disconnected. The book’s thread also includes a set of appropriately placed and mostly indispensable giants in their own right who comprise the context and also the--forgive me--glue-logic of the main narrative and its branches: Aristotle, Pascal, Huygens, Newton, Kant, Gauss, Babbage, Lovelace, Russell, Kronecker, Dedekind, Weierstrass, Peano, Brouwer, Post, Weyl, Poincaré, von Neumann, Eckert, and others. All but the most hardheaded code-jockeys among us share some part of Leibniz’s dream of encoding concepts in a language that realizes reasoning as deterministic calculation, on whose true/false, correct/incorrect result all would have to agree (as they would in an analogous sum-of-integers computation). The automation of such reasoning has evolved from Leibniz’s day onward to the formal methods of the current day.

The more general issue of decidability and computability is the perspective of this book, with the author achieving the feat of rendering a high abstraction as an almost palpable concrete entity: his well-substantiated and lucid description of the universal Turing machine. But there are also concrete instances of human and technical interest that are part of the narrative’s natural flow, including well-balanced biographical highlights.

The Hanover dynasty thought Leibniz’s most important job was to work out the Hanover genealogy. Leibniz intended a mining project initiative to support his logico-mathematical research. Boole’s founding of algebraic logic via generalization of logic to nonsyllogistic reasoning is clearly explained, as is his atypical life. Frege “wanted to provide a purely logical theory of the natural numbers,” that is, to found mathematics on logic. Russell’s devastating letter to Frege is part of this narrative, and there is material on Frege’s reaction and subsequent decline.

Cantor, along with the perennial issue of potential and actual infinities, is treated in masterly fashion. Cantor’s nonconstructive “paradise” is depicted with great clarity, including the transfinite numbers and the continuum hypothesis. The book’s account of Cantor’s anti-Helmholtz diatribes serves to reinforce Cantor’s primacy of concepts. Hegel’s absolute idealism is cited in this connection.

Hilbert’s pivotal position is certainly done justice, and his nonconstructive proof by contradiction of the basis theorem seems a perfect point of departure. The story of Hilbert’s subsequent constructive proof of the same theorem lends texture to the narrative, which characterizes Hilbert’s main interest as foundational. Hilbert’s axioms of geometry “plugged some gaping holes in Euclid’s classic treatment.” Kronecker’s “ghost” appears most usefully in the Hilbert chapter, along with Poincaré, Peano, and Brouwer, to sharpen the constructivist versus formalist or nonconstructivist distinction. X exists, according to a nonconstructivist, if assuming X’s existence does not lead to a contradiction. The authors conclude that “Gödel quietly destroys Hilbert’s program,” which serves as a segue to the next chapter. The “view [of] a logical system from the outside as opposed to the inside,” and the distinction between provability and truth are fundamental here. “The keystone in Gödel’s proof of the existence of undecidable propositions is the fact that provability in PM [1] can be expressed in PM itself.” Gödel numbering is given ultra-clear treatment in an appendix to this chapter.

The final chapter of the section on personalities introduces Alan Turing and his solution to Hilbert’s halting problem. The demonstration of an actual Turing machine multiplying 4231 by 77 is worth the proverbial thousand words. Turing’s practical bent is substantiated by the fact that the ancillary decoding machines that were built from his design during the war effort “worked correctly as soon as they were made.” Chapter 8 makes a convincing case that the ACE architecture Turing designed was closer to the universal Turing machine than von Neumann’s design, without deprecating the latter. Universality is “what was really revolutionary.” This book is a must-read along all axes: style, structure, content, and authoritativeness.

Reviewer:  George Hacken Review #: CR140571 (1301-0023)
1) Whitehead, A. N., Russell, B. Principia Mathematica, 3 vols. Cambridge University Press, 1910-1913.
Bookmark and Share
  Reviewer Selected
Editor Recommended
Featured Reviewer
 
 
History of Computing (K.2 )
 
Would you recommend this review?
yes
no
Other reviews under "History of Computing": Date
Binding time: six studies in programming technology and milieu
Halpern M., Ablex Publishing Corp., Norwood, NJ, 1990. Type: Book (9780893916916)
Sep 1 1993
An interview with Fernando Jose Corbató
Frenkel K. Communications of the ACM 34(9): 82-90, 1991. Type: Article
Sep 1 1992
Route 128
Rosegrant S., Lampe D., Basic Books, Inc., New York, NY, 1992. Type: Book (9780465046393)
Jun 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy