This is a review of The Annotated Turing by Charles Petzold.

The heart of the book is Turing's On Computable Numbers, with an Application to the Entscheidungsproblem, segmented and the segments interleaved with commentary and corrections from Petzold and Turing's own erratum. It is prefaced with some background material that will be a good refresher or even introduction for non-mathematicians. The end of the book draws connections between Turing and his/our contemporaries who carried forward his work.

Before this, my exposure to the Church-Turing Thesis had always been indirect, via the later works of Kleene and others. It was interesting to see some of the differences in the original presentation of these ideas. For example, I didn't realize or remember that the Halting Problem was introduced by Martin Davis; Turing himself discussed mainly "circle-free" machines that would never halt. I also liked that Petzold gives a rounder portrait of Turing by the inclusion of material on Turing's personal history.

I believe this book would be accessible to readers with no prior cs background. Check it out if you are interested in either computer science or the philosophy of mathematics.

## Wednesday, November 30, 2011

### Book Review: The Annotated Turing

Labels:
book,
church,
computability,
computer science,
cs,
general recursive,
halting problem,
lambda,
petzold,
review,
turing

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment