This book is an attempt by Petzold to make Turing’s seminal paper, “On computable numbers, with an application to the Entscheidungsproblem” [1], accessible to ordinary readers; it has indeed turned out to be a successful attempt.

“The Entscheidungsproblem asks for an algorithm that will take as input a description of a formal language and a mathematical statement in the language and produce as output either ‘True’ or ‘False’ according to whether the statement is true or false” [2]. This problem formed one of the challenges put forward by mathematician David Hilbert in 1928. Turing’s thesis was that such an algorithm did not exist, and he went on to prove that the Entscheidungsproblem was indeed unsolvable [1].

While this is a very important result in the area of mathematical logic and the paper introduced the powerful concept of Turing machines, the actual content of the paper has been, so far, beyond the reach of all but the most mathematically inclined readers. In this book, Petzold tries to rectify this limitation by providing a very detailed and bottom-up explanation of the paper and the mathematical theory around the subject at hand.

The book is divided into four parts. Section 1, “Foundations,” provides the necessary historical and basic mathematical contexts.

Section 2, “Computable Numbers,” forms the core of the book and explains the major parts of Turing’s paper, especially the ones that relate to what is now known as a Turing machine. Although this section is difficult to follow, due to the text it tackles, Petzold provides an engaging and clear explanation of the content, making the read a rewarding experience.

Section 3, “Das Entscheidungsproblem,” takes up the appendix part of Turing’s paper, in which he tackles the Entscheidungsproblem and explains how the computability results obtained in the earlier part of the paper can be applied to the decision problem. Petzold also explains how mathematician Alonzo Church’s lambda-calculus approach to the decision problem is equivalent to Turing’s. Mathematically, this section is the hardest to comprehend; as the author suggests, less interested readers may be better off skipping parts of it during the first read.

Section 4, “And Beyond,” examines how the concept of a Turing machine, introduced in the paper, has influenced the thinking of a wide range of researchers, in fields such as human consciousness, computer science, cellular automata, and quantum computing.

Petzold does a great job of making something as arcane and intimidating as Alan Turing’s seminal paper on the Entscheidungsproblem accessible to the nonmathematical readers amongst us; this effort deserves to be appreciated. If you are in any way interested in the area of mathematical logic, computation, or computer science, you should read this book.