American Scientist

THE ANNOTATED TURING: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine. By Charles Petzold. xii + 372 pp. Wiley Publishing, Inc., 2008. Paper, $29.99.

As the 20th century drew to a close, Time magazine devoted an issue to the 20 greatest thinkers of the century. Along with such obvious choices as Albert Einstein and John Maynard Keynes, the editors included the less familiar name of Alan Turing. In the issue's article on Turing, Paul Gray gave this explanation:

So many ideas and technological advances converged to create the modern computer that it is foolhardy to give one person the credit for inventing it. But the fact remains that everyone who taps at a keyboard, opening a spreadsheet or a word-processing program, is working on an incarnation of a Turing machine.

In the same issue of Time, Turing's importance was also acknowledged in an article by Nathan Myhrvold on John von Neumann:

Virtually all computers today, from $10 million supercomputers to the tiny chips that power cell phones . . ., have one thing in common: they are all "Von Neumann machines," variations on the basic computer architecture that John von Neumann, building on the work of Alan Turing, laid out in the 1940s.

Turing expounded remarkable insights that revolutionized the way people think about computation in a paper published in 1936 with the forbidding title "On Computable Numbers, with an Application to the Entscheidungsproblem." Although it appeared in a technical mathematical journal (the Proceedings of the London Mathematical Society), for the most part very little mathematical knowledge is needed to understand the article, because its focus is the clarification of the concept of computation itself. In his paper, Turing describes "machines" that have only a pencil-and-paper existence; their simple workings could readily be explained to a child. They "operate" on a linear tape with no limit on its length. The tape is ruled into symbol-containing squares; a machine is at any moment sensitive to the contents of only a single one of these squares and changes the symbols according to instructions contained in a table. These Turing machines, as later writers called them, derive their significance from Turing's remarkable claim that any symbolic process that can be carried out algorithmically can also be accomplished by such a machine. In The Annotated Turing, the well-established technical writer Charles Petzold has undertaken to make Turing's seminal classic paper accessible to the general educated public by providing a line-by-line close reading of the full text, with careful explanations of background material as needed.

Petzold's other books are aimed mainly at the professional software developer writing programs intended to run on the various versions of the Microsoft Windows operating system. His online writings show the eclectic nature of his interests. In one piece he notes that although New Yorkers speak of their avenues as running in a north-south direction, in fact they point from northeast to southwest. He then proceeds in a workmanlike manner to determine the actual angle with true north that Fifth Avenue makes. The latitude and longitude of any point can be read off Google Maps, and this makes it a problem in trigonometry. Petzold first uses a flat-earth approximation (perfectly reasonable for an area the size of Manhattan) so that plane trigonometry can be used. Then he moves to spherical trigonometry, which gives a better approximation, and computes the angle as 29 degrees. Another online article of much more general interest is a carefully documented piece skewering the creationists' claims that James Clerk Maxwell had argued against biological evolution.

Petzold will be a stalwart companion to any reader who undertakes to read Turing's classic with his aid. The Annotated Turing will also be quite enjoyable to a more casual reader who chooses to dip into various parts of the text.

Turing undertook the investigation that led to this paper in order to solve an important open problem, the Entscheidungsproblem (literally, "problem of deciding") of the title. This problem, whose importance was stressed by the great mathematician David Hilbert, essentially called for an algorithm that could test whether or not a proposed inference between certain premises and a desired conclusion is indeed logically correct. Thus stated, the problem may seem somewhat vague, but the development of mathematical logic made the notion of a correct logical inference quite precise. However, there were a number of reasons to suspect that there is no algorithm such as Hilbert wanted, and Turing's goal in this paper was to prove that that is indeed the case, that the Entscheidungsproblem is unsolvable.

Turing's approach was to prove that none of his pencil-and-paper machines could solve the Entscheidungsproblem and to present an argument that any algorithmic process could be carried out by such a machine. The argument was, in effect, that by successively eliminating irrelevant complications, the behavior of a person carrying out a computation could be modeled by a Turing machine. Unbeknownst to Turing, other researchers were also working on the same issues, attempting precise mathematical formulations of the informal notion of algorithmic process. Happily, all of these formulations turned out to be equivalent, although Turing's argument for their correctness proved the most persuasive.

In addition to offering the abovementioned method of suppressing irrelevant complications, Turing provided examples of the reach of his notion of computability by constructing machines (we might say "programming" them) to carry out various tasks. Of these, the most significant for computer science was his "universal" machine: Although this was itself just one of Turing's pencil-and-paper machines, he showed that it could be made to carry out any computation performed by any other of his machines. It accomplished this by initializing the tape of the universal machine with an appropriate string of symbols. This pencil-and-paper universal machine was a prototype of today's "all-purpose" computers. It made it clear that, subject only to limitations of space and time, a machine could be built that was capable of carrying out any algorithmic process.

The Annotated Turing is divided into four parts. "Foundations" gives readers the historical and mathematical information they need to understand the paper; "Computable Numbers" contains the largest part of the annotated text; "Das Entscheidungsproblem" provides background in mathematical logic and contains the remainder of Turing's paper; and the final section, "And Beyond," demonstrates the paper's relevance and shows how the information in it has been used to enhance our understanding of computers, consciousness and the universe.

Any book about Turing's work would seem incomplete if it did not provide at least a brief account of his fascinating and tragic life, and Petzold does a good job of weaving biographical information into the first two sections. Turing made key contributions, kept secret for many years, to Britain's remarkable success in breaking Germany's military ciphers during World War II. After the war he attempted to participate in the design of the earliest modern computers. To his frustration, however, people saw him as a mere theoretician, and he couldn't tell them about his secret accomplishments in practical matters. In 1954, after being hounded by the British government because of his homosexuality, he ate an apple laced with cyanide and died, an apparent suicide at age 41. Thus did stupid prejudice prematurely rob the world of a creative genius.

Martin Davis is professor emeritus in the department of computer science and the Courant Institute of Mathematical Sciences at New York University. He is the author of Computability and Unsolvability (McGraw-Hill,1958; reprinted by Dover in 1983) and The Universal Computer: The Road from Leibniz to Turing (W. W. Norton, 2000), the paperback version of which is titled Engines of Logic: Mathematicians and the Origins of the Computer (W. W. Norton, 2001).