Computability theory textbooks usually have little historical content, while popular treatments usually have few technical details. This book is the exception that carefully explains one of the fundamental papers of the 20th century, putting it in historical context, including the backgrounds of the important contributors. That paper is “On Computable Numbers, with an Application to the Entscheidungsproblem,” published in 1936, when computing was done by humans rather than digital computers. Turing’s goal was to show that there was no process to determine the provability of arbitrary statements in mathematical logic.

Three of the four sections of the book do not require much mathematical background, but the technical parts of each section are not easy reading, requiring attention to detail in order to follow the low-level steps of Turing machine computations. The parts of Turing’s paper are shown in gray, followed by Petzold’s explanations that expand upon the examples, making Turing’s paper accessible to readers willing to patiently think through the details.

Section 1, “Foundations,” provides historical background starting with Diophantus and equations with integer solutions that are tied to the final chapter, which discusses the conclusion that there is no decision process that can determine in a finite number of steps whether such an equation is solvable.

Section 2, “Computable Numbers,” covers the nine parts of Turing’s paper that use what have come to be called Turing machines. Although it takes effort to work through the details, it is rewarding to follow the thoughts of a man who may have the best claim to being called the father of the computer. Turing’s universal machine that could execute any other Turing machine foreshadows the idea of the stored program computer in contrast to computers constructed to solve specific problems.

The third section, continuing Turing’s paper to apply his computability results to the decision problem, is more mathematical; Petzold invites readers less interested in mathematical logic to skip it. This section includes Church’s lambda calculus and Turing’s appendix showing that his approach to the decision problem is equivalent to Church’s, which was developed independently at the same time. Turing went on to earn a PhD under Church at Princeton.

The final section shows why its title, “Is Everything a Turing Machine?” is an appropriate description of developments after Turing. McCullough, Pitts, von Neumann, and Wiener relate computing and neural functioning. With cellular automata and quantum computing, computing and physics are increasingly intertwined, to the point where some say that the universe is a Turing machine.

One could browse this book and get a good survey of computability and Turing’s work, including stories about Turing and other contributors. To those willing to read carefully, Petzold provides a fabulous resource for one of the great milestones of computing.