BOOK REVIEW
Ahead of His Time
Martin Davis
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.)