You are here

The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine

Charles Petzold
Publisher: 
John Wiley
Publication Date: 
2008
Number of Pages: 
372
Format: 
Paperback
Price: 
29.99
ISBN: 
9780470229057
Category: 
General
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
William J. Satzer
, on
08/28/2008
]

Although Alan Turing’s name is well known, at least throughout the scientific and engineering community, I expect that very few people have actually read the paper that introduced the notion of Turing machines. “On Computable Numbers, with an Application to the Entscheidungsproblem,” first appearing in 1936, became the foundation for the theory of computation and has had widespread influence in computer science and mathematics.

The Annotated Turing is a kind of commentary or exegesis that takes the reader through Turing’s paper, pretty much line by line. Although this book is most likely to appeal to programmers or computer scientists, the author has taken great pains to make the book accessible to readers with no more than high school mathematics. For the more sophisticated reader, this means that there are stretches of elementary material that can easily be skipped. Yet, unless the reader is already very knowledgeable about Turing’s work and this paper in particular, there are surprises. For the less sophisticated reader, there are some very detailed — and, frankly, tedious — parts of Turing’s paper that could be skipped without missing much.

The book is divided into four parts. Part I, “Foundations”, provides historical context and basic mathematical background necessary for reading Turing’s paper. Part II, “Computable Numbers”, is the core of the book. It addresses the major part of Turing’s paper and introduces what we have come to call the Turing machine. The decision problem of the paper’s title is taken up in Part III, “Das Entscheidungsproblem.” This section begins with a brief discussion of mathematical logic and continues with Turing’s application of his earlier results to the decision problem. Part III is the most technically challenging part of the book and the author moves through it pretty quickly. Part IV, “And Beyond”, looks at how the concept of the Turing machine has exerted considerable influence on computing in the broadest sense — to questions about human consciousness (for example, the work of McCullough and Pitts) and whether the universe itself is essentially a Turing machine.

Every word of Turing’s original paper (as well as short follow-up paper with corrections) appears in this book. The author puts Turing’s words in shaded boxes, mostly preserving the typography and layout of the original paper. That typography includes Turing’s fairly extensive use of German Gothic font, but the author mostly succeeds in making even that mostly palatable. The author’s explanations, commentary, clarifications, anecdotes and embellishments surround the shaded boxes. The overall effect is rather like reading a biblical commentary.

This book has its own kind of charm and is well worth reading – if nothing more – for its historical background and plentiful anecdotes. For the student of computability, the line-by-line commentary, particularly with its careful untangling of instructions for the Turing machine, would be particularly valuable.

As I read this I wondered if there other seminal papers that would benefit for this kind of extended commentary, and which ones they might be.


Bill Satzer (wjsatzer@mmm.com) is a senior intellectual property scientist at 3M Company, having previously been a lab manager at 3M for composites and electromagnetic materials. His training is in dynamical systems and particularly celestial mechanics; his current interests are broadly in applied mathematics and the teaching of mathematics.


Introduction.

I Foundations. 

1 This Tomb Holds Diophantus.

2 The Irrational and the Transcendental.

3 Centuries of Progress.

II Computable Numbers. 

4 The Education of Alan Turing.

5 Machines at Work.

6 Addition and Multiplication.

7 Also Known as Subroutines.

8 Everything Is a Number.

9 The Universal Machine.

10 Computers and Computability.

11 Of Machines and Men.

III Das Entscheidungsproblem. 

12 Logic and Computability.

13 Computable Functions.

14 The Major Proof.

15 The Lambda Calculus.

16 Conceiving the Continuum.

IV And Beyond. 

17 Is Everything a Turing Machine?

18 The Long Sleep of Diophantus.

Selected Bibliography.

Index.