This post is my personal review of a book I really enjoyed reading: The Annotated Turing by Charles Petzold1. For me, a reader’s honest perspective is a great way of finding and choosing books to read, so here I give you mine. I really recommend this book, it is a great read!

A book about a paper

As far as I know, the format of the book is unique. Essentially it is a reprint of Turing’s paper On Computable Numbers, With Application to the Entscheidungs Problem (1937) intercepted with explanations by the author. In some chapters the paper dominates and in others there is more explanations, examples and background story. If you know any other book using this format, please let me know.

The book consists of four main parts where the second and third part contain Turing’s paper. In the introduction the concepts of rational versus irrational and transcendental versus algebraic numbers are explained. This is done carefully with examples in order to not require a lot of math background. It proceeds with some historical background on the big mathematical questions of the time which sets the stage for Turing’s idea. Turing’s paper then appears in the second part, introduces Turing machines and computable numbers. Again, the author greatly reduces the information density of the paper with examples and explanations. Some chapters do not advance in the paper at all, but simply give and explain additional examples. For me, the toughest section was the “Detailed description of the universal machine”. Without spoiling too much, the universal machine is the key idea in this work. The fact that it exists is crucial and its existence is proved by direct construction. But after you get the idea in plain English, translating it into the formalism is still a lot of hard work. In part three we are guided through first-order logic and the Entscheidungsproblem for it. The final result is presented and proven, namely that no decision procedure for first-order logic exists. This is achieved by encoding an undecidable question about Turing machines in a first-order logic formula. The fourth part discusses related work such as lambda calculus by Church and philosophical implications by asking if everything is a Turing machine. Interesting connections to physics and biology are shown before concluding the book.

Accessible to a motivated reader without math background

Although it is often claimed that this paper started the field of computer science it still is a math paper. However, all notation is explained in detail and the only prerequisite is simple school mathematics. The introduction explains the relevant math concepts but you only really need those to understand the application the Entscheidungsproblem. I think if you skipped it and only read the second part about Turing machines it is still accessible, just a bit out of context.

Reading it as a computer science student

As a computer science student I was already familiar with the concept of a Turing machine including its formal definition. In a course on theoretical computer science we designed some Turing machines, but almost never in detail. Especially when doing reductions, the constructions are often on a higher level using other Turing machines as building blocks. In this book, machines are constructed in full formal detail. On one hand this is very laborious and the process usually provides very little new insights. On the other hand we want the theory to be mathematically rigorous so it is crucial to work out the details exactly. That being said I skipped the detailed construction of the universal machine and accepted it as a fact of life (for now). Still, I learned a lot about the background and motivation of the paper which was completely new to me.