The Annotated Turing

(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.