Let me start by saying while reading The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine I encountered two other reviews worth note. The first review by Jeff Atwood focused on Alan Turing's personal life as a gay man in the first half of the 1900's and is light on reviewing the actual text of Turing. The second review is by Deirdre Sinnott and does cover the text in depth, but one must carry a certain level skepticism (however undue) toward Deirdre given her relationship to Petzold. I must also alert the reader to my own bias, as I have written well of Petzold in the past and was sent a (signed) copy of Turing. I did however purchase the book before I knew a copy was being sent to me.
For the impatient, busy, or otherwise opposed to reading what has become a lengthy review, I will save you the investment of time by saying now I highly enjoyed this book and would strongly recommend it to any programmer, mathematician, or person with an interest for numbers. I will qualify this recommendation with the disclaimer that if you do not have the time to devote to reading the remainder of this review, you may not have the time needed to read and understand the book's content. I found myself only able to read 10-20 pages a night of this scant 359 page book due to the amount of mental engagement demanded by the subject matter; which only worked to increase my enjoyment. Before we get into the content of the book however, let us take a moment to understand the actors involved...
Alan Turing is our hero in this tale, a brilliant young man who leads a troubled life and finds refuge in a love for numbers. Our narrator, Charles Petzold, shares a great many things in common with Turing, including this love of numbers and the mind to process these numbers in complex ways. I have read many of Petzold's books on Microsoft Windows programming and one constant is that his examples often use calculus or trigonometry equations in a way that the example itself teaches as much on mathematics as the API the text covers. Mathematics and computers, I'm learning, are tied much closer together than most would assume. The last character is myself, the reader, who poses only a basic understanding of college level mathematics (enough to meet CS requirements) and who once wrote a two page mathematical paper that was, in the words of the professor, "an amazing level of insight and effort, but 100% flawed and incorrect". I mention this because while I was not able to understand every formula and proof covered in Turning, this did not detract from my understanding of its significance to the material.
The events in Turing surround Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem." I will probably offend true mathematicians with the following explanation of the Entscheidungsproblem (and again later in this review), but simply put the Entscheidungsproblem asks for a set of steps one can use to determine if a given formula has a solution (but not what that solution might be). Consider A² + B² = C², which we know is true because we can plug in 3, 4, and 5 and see that it works. What about A³ + B³ = C³? Before we start trying some random numbers it would be nice to know if there even is a solution - and this is what the Entscheidungsproblem is all about. (My method would be to try some random numbers, I'm sure a mathematician would start with a much more reasonable and fruitful approach.)
Turing proved that no, there is not a universal method for determining if a given formula has a solution. Turing was not the first to prove this: 6 weeks before Turing's paper was published in 1936, Alonzo Church published a paper that also proved there was no method for the Entscheidungsproblem. Turing's solution was so novel and unique in it's approach however, that it has the rare honor of also being published, and Turning added a proof to his paper that both methods are equivalent.
Truth. To normal folk truth has a somewhat soft definition, but to mathematicians truth has strong and rigid meaning. You may know something to be true simply through common sense, but in the world of mathematics something must be proven in concrete formula before it can be accepted as true; until then it remains unproven and will not even be considered worthy of assumption of truth in all but the most extreme cases.
To tackle the truth of the Entscheidungsproblem, Turning invented (on paper) a machine that could read a sequence of commands that expressed a method to calculate number and print it as the result. This allowed Turing to work with numbers like π without needing to calculate the exact value (something no easier in 2008 than it was in 1936). Further, Turing devised a method to give every possible sequence of commands a unique number, called a Description Number, or DN. The DN for a machine that computed π might be DN 314,257. Last, Turing invented a machine that could be given a DN and generate the sequence of commands that DN represented, then pass this sequence off to another machine to calculate the result. Turing's machines worked in binary, i.e. 0's and 1's only, so Turning then proved it was not possible given a DN to determine if the calculation machine would ever print a 0 as a result of calculation, thus proving there was no universal method to determine if a given formula had a solution.
Just reciting the list of actors and events doesn't convey the story, we must also discuss the meaning and impact. Much of The Annotated Turing is true to the title; Petzold presents the unmodified original Turing paper and provides annotations to help understand the material, while also citing related material and events. In this capacity, Petzold is unsurpassed - the bibliography for Turing cites over 90 books and papers (including a humble citation of Petzold's own Code) and one is given the impression Petzold read many more books not cited. Petzold's greatest contributing to Turing's work comes at the end however, when he explores the impact Turing had on the fields of mathematics, computer science, and philosophy.
Any developer reading above recognized that Turing machines are computers running programs. What may not have been obvious is that Turing's proof also means that no program can be written that will determine the output of another program. That we cannot break this limitation, and our new platforms, languages, and computers will "at best [...] only do jobs faster."
The philosophic impact is far greater, for we humans qualify as Turing machines. Other philosophers and mathematicians have come very close to a proof that the universe is fundamentally digital, can be expressed as 0's and 1's, and qualifies as a Turing machine. If true, this abandons our romantic notions of free will, for as a Turing machine in a digital universe our actions are calculable. Our perception of free will is merely the misunderstanding of the inability to predict the output of our own Turing machine, the mind.
I do not assert I've laid out a solid argument in the above paragraph - for that you'll need to read Turing and possibly the references cited by Petzold. Having just finished Turing hours before writing this review, and being a person who has rejected the idea of fate, I'm still a little uneasy myself. It's as if Alan Turing sat next to me on the airplane and said, "Oh fate? It exists, I have a mathematical proof here somewhere in my backpack I did last summer when I had some spare time." At least I don't have to tell the major religions of the world I was wrong about them too...
Last, I'd like to mention that in planning for CodeSock this summer, we were able to get Wiley Publishing (publisher of Turing) as a supporter. I requested and was granted 5 copies of The Annotated Turing to give away at the end of the conference.