“The Annotated Turing” by Charles Petzold ¹

Many of us have learned about ‘Turing Machines’ or ‘Turing Completeness’ but have never actually read the motivating text and explanation. This is a phenomenal book that goes through paragraph by paragraph the paper “On Computable Numbers” ² by Alan Turing in a rigorous way explaining the concept intuitively and completely. Not only does it explain the text, but it also gives enough background so that one could understand and follow through the proofs themselves. It is well written and clear without feeling like a textbook. It is divided into fours sections:

• Background. This section walks you all the way from Diaphanous equations until Gödel’s incompleteness theorem.
• Computable Numbers. This is the first section of the paper and goes from the first paragraph until about 2/3 of the way in. This is where the machine itself is defined.
• Das Entscheidungsproblem. This is the second half of the paper focusing on the application of the machine to decidability.
• “And Beyond” enters the philosophical and discusses Turing’s own thoughts on if machines can ’think’ and connects his thoughts to later thinkers.

Additionally, the book gives a brief biography of Turing including his childhood, education, war efforts, and sad death.

References