American Scientist

The Man Who Knew Too Much: Alan Turing and the Invention of the Computer. David Leavitt. x + 319 pp. W. W. Norton, 2006. $22.95.

To "compute" used to mean to perform a calculation, presumably with numbers. How is it then that our modern computers can be used to carry out so many varied tasks that, at least on the face of it, seem to have little to do with calculation? It is to Alan Turing that we owe our understanding of the full extent of the concept of computation as well as the realization that a computing machine can be "all-purpose": There is no need for a myriad of separate devices to perform the full variety of possible computational tasks.

Turing was conceived in India, where his father was a civil servant under the Raj, and was born in London in 1912. Much of his childhood was spent in England, while one or both of his parents stayed in India. His interest in scientific matters developed early and began to flower while he was at the Sherborne School, a traditional British "public" school (which is to say a private one) for boys. It was also there that he had an intense schoolboy crush on a brilliant fellow student, whose death devastated him. Turing's mathematical ability, which was noticed but rather disdained at Sherborne, led to a scholarship at King's College, Cambridge. After his degree, he was elected a Fellow of the college and was on a well-worn path to a career as a journeyman mathematician.

Lectures on the foundations of mathematics by Max Newman led to an abrupt shift in direction. In the early 1930s there was much excitement concerning the discovery by Kurt Gödel that no single formal system of logic could decide all propositions of mathematics. Newman, a topologist, had no professional expertise in these matters but evidently provided a thorough and captivating account, beginning with the basics and leading his students up to the frontier of knowledge. In particular, he called attention to David Hilbert's Entscheidungsproblem.

Hilbert had asked for an algorithm that, provided with some premises and a purported conclusion as input, all written in the language of formal logic, would determine whether that conclusion was indeed a logical consequence of the premises. In a sense, this was an old problem, going back at least to Leibniz, but it attained its sharp form only with the 20th-century development of "symbolic" logic. Mathematicians were very familiar with algorithms, and many important algorithms were part of the body of mathematics. But many doubted that an algorithm existed that could do what Hilbert wanted. In fact, another theorem of Gödel's suggested very strongly that no such algorithm could exist.

But how could one prove such a negative? Mathematicians certainly could recognize an algorithm when they saw one. However, to prove there is no algorithm for some particular problem, this would not suffice. It seemed one would need a precise definition of what constituted an algorithm, and when Turing began thinking about the problem, no such definition was available to him. He began by analyzing and simplifying what it is that a human being does when executing an algorithm with pencil and paper, and then presented a convincing argument that such a process could, with no loss, be replaced by a very simple imagined device that did nothing but move back and forth on a linear tape, noting and replacing symbols. To prove that the Entscheidungsproblem is unsolvable, Turing proceeded by showing that no such device could solve it. This type of device would later be known as a Turing machine.

In addition he showed that there is a universal Turing machine, a single Turing machine that, all by itself, could accomplish anything that any other Turing machine could do. The universal machine worked by being programmed to accomplish just what a specialized Turing machine would have done—using a formal description of that particular Turing machine as input. This strategy provided an abstract prototype of an all-purpose computer with the machine description, the input, playing the role of a program. That the same input could be regarded both as a machine description (hardware) and as a program to be executed (software) was itself an important insight into the nature of computation.

After spending two years at Princeton, where related work was being done, Turing found himself back in England just as the Second World War loomed. The war would put the practical side of Turing's understanding of computation to the test. He was part of a group assembled at Bletchley Park, an estate midway between Oxford and Cambridge, to undertake the desperately important effort to decode German military communications. It was Turing's logic machines (called bombes) that made it possible to decipher German naval communications and thus to defeat the submarine fleet that was choking Britain's Atlantic lifeline. Remarkably, these devices, built from Turing's plan, worked immediately, without further testing. Unfortunately, this work remained supersecret even when the war was over, and so only a few realized that this theoretical mathematician understood a thing or two about the practicalities of automatic computation.

Making matters worse, Turing's efforts to initiate the development of an all-purpose electronic computer, one with advanced features that were only reinvented much later, were stalled by bureaucratic obstacles, while engineers with less vision forged ahead. Turing gave up any efforts to be involved in machine design, took a position at the University of Manchester and became an enthusiastic user of the new computer there, shifting his focus to computational problems in biology.

It was in Manchester that Turing's unabashed attitude about his homosexuality led to catastrophe. His house was burglarized by an acquaintance of a young man with whom Turing had been having a sexual relationship. Turing's naive report of the burglary to the police led to his arrest and conviction for "gross indecency." To spare him a prison sentence, the judge required a year of estrogen injections intended to subdue Turing's sex drive. But that barbarity wasn't the end of it. The authorities actively interfered with any foreign amorous interests, because in the Cold War hysteria of the 1950s, his homosexuality together with the wartime knowledge of government secrets in his head made him a "security risk." He died from eating a poisoned apple in June 1954, an apparent suicide.

David Leavitt's new biography of Turing, The Man Who Knew Too Much, is part of W. W. Norton's "Great Discoveries" series, two other volumes of which also deal with mathematical subjects. Each of the three books was written by a prominent writer of fiction without specific mathematical expertise, and all three contain numerous errors, most of which could have been avoided if the manuscripts had been checked by an expert. But all in all, Leavitt has done an admirable job. He has worked through Turing's groundbreaking paper, which was written for professional mathematicians, and has done a commendable job of explaining it to his audience. His discussion of the German ciphers and what it took to break them is also quite detailed. The book is beautifully written, and the errors that will irritate an expert won't be noticed by most readers. (Be warned, though, that the discussion of Gödel's theorem is confused: The undecidable propositions are only undecidable with respect to a given formal system. Thus in the explanation Leavitt gives [and confusingly puts quotation marks around] in the first paragraph on page 44, the phrase or any related system should be deleted.) Leavitt has indicated that corrections will be made in the paperback edition.

It is in his empathy for Turing's situation as a homosexual man living in a hypocritical, sexually repressive society that Leavitt really shines. In an article that appeared in the April 3, 1994, New York Times, he wrote:

What is unique about English homophobia is that it is part and parcel of a national fervor for gay sex. . . . Do what you will under wraps, England tells its men, but cross this line and I will destroy you. It's no wonder that Oscar Wilde characterized his adopted country as "the native land of the hypocrite."

Only very gradually was it realized that our modern computers are embodiments in silicon of Alan Turing's universal machine. There was controversy over the relative importance of the mathematician John von Neumann and the engineers at the University of Pennsylvania in the development of the EDVAC, an early electronic computer built there, yet there was no mention of Turing at all. But by the end of the last century, Time magazine included Alan Turing in its list of the 20 greatest thinkers of the century, writing that "everyone who taps at a keyboard, opening a spreadsheet or a word-processing program, is working on an incarnation of a Turing machine." (Full disclosure: Far too generously, Leavitt credits me for this change of attitude.)