The Annotated Turing
A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine
by
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.
Availability
This book is available for pre-ordering from:
as well as many other real and virtual bookstores.
About the Book
(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.
Tentative Table of Contents
Page numbers shown in bold refer to the pages of Turing's original paper discussed in that chapter.
Part I. Foundations
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 infinity that gets in our way?
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.
"Wir müssen wissen. Wir warden wissen," Hilbert says. Good luck with that!
Part II. Computable Numbers
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. [Turing, 230-233]
Chapter 5. Machines at Work
Turing’s paper shows several examples of simple computing machines and several ways to notate what they do.
[Turing, 233-235] Where is he going with this?
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. [Turing, 235-239]
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. [Turing, 239-241]
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. [Paper, 241-246]
It’s a general-purpose computer, although it takes many years for Turing’s
contribution to the principles of computers to be recognized.
Chapter 10. Computers and Computability
While exploring the concept of enumerability of computing machines, Turing’s paper seems to uncover a paradox.
[Turing, 246-248] The resolution of this paradox leads to the most profound result of his paper:
You can’t design a computing machine to determine if other computing machines work correctly or not.
Chapter 11. Of Machines and Men
Turing explores the relationship between human and machine calculators [Turing, 249-254] and
later becomes interested in artificial intelligence. He runs afoul of the law with serious consequences.
Part III. Das Entscheidungsproblem
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 [Turing, 254-258]
and implement functions as well.
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. [Turing, 259-263]
Chapter 15. The Lambda Calculus
Alonzo Church used his λ-calculus for his paper about the Entscheidungsproblem.
Turing shows that the two methods are equivalent. [Turing, 263-265]
Part IV. And Beyond
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
