Author: Martin Davis
Publisher: A K Peters/CRC Press
Aimed at: Anyone interested the logical theory of computing
Pros: Fascinating mix of mathematics and history
Cons: Not about the history of computing
Reviewed by: Mike James
What do people want to know about Turing?
This Turing Centenary Edition is a re-issue of the original 2000 edition of this book. Not much has changed - Martin Davis has added a new preface and some additional sections to bring his book up to date.
This means you almost certainly don't want to buy it again if you already have it. On the other hand, the Turing Centenary is making a whole new audience interested in the ideas behind computing and if you are new to these ideas this is a good place to start.
The most important things to say is what this book is not about. It cerainly isn't a book that concentrates solely on Turing, it isn't a biography and it isn't about the history of computers.
Indeed the seven people it covers aren't usually associated with the invention of the computer at all. What you need to bear in mind is that Martin Davis is a logician and researcher in the theory of computation. The title given the the 2001 paperback edition, "Engines of Logic" is perhaps a better fit with the contents.
The subtitle of the book is "The Road from Leibniz to Turing" and this should give you a better idea what it is all about. The seven people and there works that are covered are - Leibniz, Boole, Frege, Cantor, Hilbert, Godel and Turing. Of these Leibniz, Cantor and Hilbert are generally thought of as "pure" mathematicians. Boole, Frege and Godel are logicians and Turing is a a sort of cross between logic, maths and computer science. So what this book is really about is the development of logic as it applies to computation and vice versa.
Leibniz starts off the story by being the first person to think that reasoning could be translated to symbols and, by implication, automated. You could argue that there are earlier examples of trying to translate thought into "recipes", syllogisms for example, but we have to draw the line somewhere.
From here we have an explanation of how Boole developed the logic named after him as an analog of the usual laws of algebra. At this point you get the clear impression that the arguments were groping towards the modern view of things.
Next comes Cantor who doesn't seem to have much to do with computation, until you realize that his "diagonal" argument allowed both Godel and Turing to show that not everything was included in logic. Cantor's theory of the transfinite number is explained as a way of getting to grips with things that are actually infinite rather than just heading in that direction.
Then we reach Hilbert, where arguably mathematics made the transition to the modern view of what it is and how it works. Godel demonstrated if this is indeed what mathematics is, then there are things that can be correctly formulated using its rules but not proved using those rules. This, added to Turing's formulation of what can and cannot be computed, brings us right up to the modern age.
The book provides a good tour of the subject, but you can argue with the selection of the people it covers. Arguably Cantor, Leibniz, Frege and Hilbert are sideshows on the main event. They all laid foundations that others built on, but perhaps the main story is really about Boole, Godel and Turing. You might also want to add other contributors - Church, and Dedekind, both of of whom are mentioned , for example.
Some material has been added to "justify" a Turing Centenary edition but it draws attention to the way in which the final two chapters seem out of place. Chapter 8, on the invention of the modern computer, doesn't follow naturally from the earlier chapters an is essentially just a set of notes. Nor does chapter on future advances, which is mostly about AI (including mention of IBM's Watson) and the argument about whether or not it is possible.
Given that the author is a logician, it isn't surprising that this book is mostly about the development of modern logic and computation. As such it is an interesting read and very enjoyable. Each of the chapters give lots and lots of biographical details of the lives of the people who thought up the ideas. It also gives good clear explanations of their ideas as well. This means that you might be disappointed in the book if you really want the ideas or if you really want the biographies. I found them both fitted together well and manged to give a background in which the ideas took shape.
As long as you realize that this is a book about logic, and about the Entscheidungsproblem (i.e. what is computable, in particular), then this is a really good book. It is easy to read, it is entertaining and it tells you something.
What is a Turing Machine?
Confronting the unprovable
The Programmer's Guide To The Transfinite
The Universe as a Computer