Charles Petzold

50% size 100% size |
Before digital computers could do much of anything, Alan Turing demonstrated what they could never do.... Coming June 16, 2008! |

ISBN-10: 0-4702-2905-5; ISBN-13: 978-0470229057; Wiley; May 19, 2008; 300 pages.

This book is available for pre-ordering from:

- Wiley
- Amazon US
- Amazon Canada
- Amazon UK
- Amazon Deutsch
- Amazon Français
- Amazon Japan
- Barnes & Noble
- Blackwell

(excerpts from my proposal for the book)

Anyone who has explored the history, technology, or theory of computers has likely encountered the concept of the Turing Machine. The Turing Machine is an imaginary — not even quite hypothetical — computer invented in 1936 by English mathematician Alan Turing (1912–1954) to help solve a question in mathematical logic. As a byproduct, Turing also founded the field of computability theory — the study of the abilities and limitations of digital computers.

Although the concept of the Turing Machine is well known, Turing’s original 1936 paper is only rarely read. This neglect may have something to do with the paper’s title — “On Computable Numbers, with an Application to the Entscheidungsproblem” — and perhaps the paper’s extensive use of a scary German gothic font. That’s too bad, because the paper is not only a fascinating read but a milestone in the history of computing and 20th century intellectual thought in general.

This book presents Turing’s original 36-page paper (and a follow-up 3-page correction) with background chapters and extensive annotations. Mathematical papers like Turing’s are often terse and cryptic. I have elaborated on many of Turing’s statements, clarified his discussions, and provided numerous examples.

Interwoven into the narrative are the highlights of Turing’s own life: his years at Cambridge and Princeton, his secret work in cryptanalysis during World War II, his involvement in seminal computer projects, his speculations about artificial intelligence, his arrest and prosecution for the crime of “gross indecency,” and his early death by apparent suicide at the age of 41.

The book is divided into four parts: Parts I and II together are about 200 pages in length and cover the first 60% of Turing’s paper, encompassing the Turing Machine and computability topics. This part of the book is entirely self-contained and will be of primary interest to most readers.

Part III is a faster paced look at the remainder of Turing’s paper, which involves the implications for mathematical logic. Some readers might want to skip these chapters.

Part IV resumes the more "popular" presentation showing how the Turing Machine has become a vital tool in understanding the workings of human consciousness and the mechanisms of the universe.

Although I expect the primary readers of the book to be programmers, computer science majors, and other “techies,” I have tried my best to make the book accessible to the general reader. There is unavoidably much mathematics in the book, but I have tried to assume that the reader only has knowledge of high-school mathematics, and probably a foggy one at that.

Page numbers shown in bold refer to the pages of Turing's original paper discussed in that chapter.

Chapter 1. This Tomb Holds Diophantus

In Ancient Alexandria an old man grieves for his dead son, and he consoles himself by writing a book of math problems and solutions. Diophantus's problems always have solutions, but many Diophantine problems do not. How can we tell the difference, and what's this thing

Chapter 2. The Irrational and the Transcendental

Georg Cantor explores infinity with surprising results. Some infinities are more infinite than others. This concept is to have profound influences on 20th century mathematics, and still makes people uneasy.

Chapter 3. Centuries of Progress

A century before the Y2K scare, David Hilbert asks whether a generalized procedure can be found to determine the solvability of Diophantine problems. He later formulates the Entscheidungsproblem — the decision problem — which asks whether arbitrary well-formed formulas in 1st-order logic can be determined to be provable. "

Chapter 4. The Education of Alan Turing

Alan Turing reads books, gets smart, goes to Cambridge, gets smarter, and decides to tackle the Entscheidungsproblem. As a tool, he invents an imaginary computing machine. Alas, Alonzo Church beat him to the proof, but Turing's paper is published anyway.

Chapter 5. Machines at Work

Turing’s paper shows several examples of simple computing machines and several ways to notate what they do.

Chapter 6. Addition and Multiplication

While Turing goes to Princeton to earn his PhD in mathematics, Petzold takes a break from Turing’s paper to present a more complex Turing machine that calculates the square root of two. Watch out! Here there be hairy stuff!

Chapter 7. Also Know as Subroutines

Turing next shows how certain common routines can be isolated and reused — a concept familiar to today’s programmer as subroutines or functions. Turing builds an arsenal of tools for a big project coming up in the paper.

Chapter 8. Everything is a Number

Turing returns to England and reports to Bletchley Park in 1939 to help figure out Germany’s Enigma code-making machine. Turing’s paper continues by showing how each computing machine can be represented by an integer. Computing machines are infinite but enumerable.

Chapter 9. The Universal Machine

Turing next shows how a computing machine could be made to read coded instructions and perform the job of any dedicated machine.

Chapter 10. Computers and Computability

While exploring the concept of enumerability of computing machines, Turing’s paper seems to uncover a paradox.

Chapter 11. Of Machines and Men

Turing explores the relationship between human and machine calculators

Chapter 12. First-Order Logic

The remainder of Turing’s paper requires a familiarity with first-order predicate logic. This chapter provides the basics.

Chapter 13. Computability, Continued

Turing’s paper continues by introducing imaginary machines that can solve problems in mathematical logic

Chapter 14. The Major Proof

With the help of his previous demonstration, Turing shows that there can be no machine to determine the provability of arbitrary statements in first-order logic. The Entscheidungsproblem has no solution.

Chapter 15. The Lambda Calculus

Alonzo Church used his λ-calculus for his paper about the Entscheidungsproblem. Turing shows that the two methods are equivalent.

Chapter 16. Consciousness, the Universe, and Turing Machines

With the Turing Machine as a springboard, biologists, cosmologists, and philosophers explore the depths of human consciousness and the very structure of the universe.

Chapter 17. Diophantus Awakes!

With the help of Turing Machines, Yuri Matiyasevich builds on the work of Julia Robinson, Martin Davis, and Hilary Putnum to show that there is no general process for determining the solvability of Diophantine equations.

© Charles Petzold, 2007

cp@charlespetzold.com

This page last updated November 2007