Charles Petzold

Summer Reading: “The Man Who Knew Too Much: Alan Turing and the Invention of the Computer”

August 11, 2006
Roscoe, NY

The Man Who Knew Too Much: Alan Turing and the Invention of the Computer (W. W. Norton, 2006) by David Leavitt (the novelist best known for The Lost Language of Cranes) is part of Norton's Great Discoveries Series, an innovative and interesting pairing of topics and authors.

There are some who would say that Andrew Hodges' Alan Turing: The Enigma (Simon & Schuster, 1983) has made any other Turing biography unnecessary and redundant, but I mostly enjoyed Leavitt's take on the subject. Leavitt certainly pays homage to "Hodges' magisterial 1983 biography" (pg. 6) but judging from the footnotes, Leavitt also spent a considerable amount of time himself roaming the Turing Archive at King's College, Cambridge, and a lot in this book sounded new to me. I particularly liked Leavitt's portrait of Alonzo Church, his evocation of 1930s Princeton, his recounting of the famous Wittgenstein Lectures on Mathematics, and his retelling of Turing's work at Bletchley Park. Leavitt even found new angles for the discussion of Turing's writings on machine intelligence and the controversies that surrounded them.

Throughout the text, Leavitt connects Turing's life with a variety of cultural reference points. Some of these references are expected by readers of Hodges (Snow White and the Seven Dwarfs) and some are unexpected (Erewhon, Middlemarch, Spartacus, two mentions of Star Trek in the first 26 pages), but what works the best are Leavitt's references to The Man in the White Suit and the novels of E.M. Forster, including (but not limited to) Maurice. In 1931, Leavitt observes, Turing lived very close to Forster. "Had he been less shy, Turing might have made Forster's acquaintance and perhaps been invited to one of the evening gatherings in which the author, now getting on in years, read aloud from the manuscript of Maurice." (pg. 17) (Actually, E.M. Forster was only 52 in 1931; Forster died in 1970 at the age of 91 and Maurice was finally published the following year.)

Unfortunately, Chapter 3 of The Man Who Knew Too Much, which attempts to describe Turing's historic paper “On Computable Numbers, with an Application to the Entscheidungsproblem,” is pretty much a disaster. There's simply too much detail here, and the main points are missed entirely. Leavitt has obviously consulted Roger Penrose's The Emperorer's New Mind for some help, which is safe only if Leavitt realizes that Penrose's Turing Machines are quite different from Turing's own machines. Leavitt also anachronistically refers to the "halting problem" (pg. 82), a term that Martin Davis originated and which first appeared in print in his 1958 book Computability and Unsolvability. It doesn't make any sense to refer to the halting problem in connection with Turing's paper because Turing's machines don't have a Halt instruction. Turing's "good" machines (the ones Turing labels as "circle-free" or "satisfactory") always run forever printing digits. They need to run forever because each machine computes a particular real number between 0 and 1, and in the general case, the digits never stop.

It seems to me that understanding Turing's paper requires a good grasp of the concept of enumerability, and that's something Leavitt doesn't get into at all. It needs to be clear why integers are enumerable, rational numbers are enumerable, algebraic numbers are enumerable, but real numbers are not.

It's easy to establish that each of Turing's machines is uniquely represented by an integer, which he calls the Description Number. This is a no-brainer for people now because we're familiar with the nature of machine code and know that every EXE file is basically a humungus integer. It's clear that these Description Numbers are enumerable, and hence the Computable Numbers are enumerable, which means that the Computable Numbers must necessarily be a subset of the real numbers. Already the limitations of computing machines become evident. Computing machines are incapable of calculating the vast majority of possible real numbers!

In section 8 of "On Computable Numbers" Turing applies Cantor's two proofs of the non-enumerability of the real numbes to the computable numbers, and here he encounters a paradox. Applying Cantor's diagonalization process to an enumeration of computable numbers seems to reveal that computable numbers are not enumerable. Something is clearly wrong, and Turing's breakthrough comes with unraveling this contradiction. Although circle-free machines are enumerable because they are a subset of the integers, they cannot actually be enumerated through a finite process because enumerating circle-free machines requires determining whether a particular Description Number represents a circle-free machine or a circular machine.

And that leads to Turing's realization that it is not possible to devise a general finite process to determine what a particular machine will do without actually running the machine or tracing through it, which is the equivalent of running it. This means, of course, that you can't write a general "debugger" program that will analyze other programs. None of this quite comes out in Leavitt's discussion, and it's unfortunate, because a more comprehensible Chapter 3 would greatly elevate this entire book.

Alan Turing was an unapologetic gay man who lived in a time and a country where any type of sexual contact between men was illegal. His 1952 arrest for the crime of gross indecency (the same law under which Oscar Wilde was prosecuted half a century earlier) seemed to come as a bit of a surprise to him. His suicide two and a half years later is usually attributed to this arrest and the humiliating hormone treatments he was subjected to in lieu of prison.

Turing's suicide has always been very mysterious, and it remains mysterious even with Leavitt's attempts to illuminate it. Leavitt writes "The little that was left of Alan Turing's life after his arrest was a slow, sad descent into grief and madness." (pg. 268) Why then did Turing's acquaintances find the suicide so surprising?

To understand this era a little better, earlier this year I read David K. Johnson's The Lavender Scare: The Cold War Prosecution of Gays and Lesbians in the Federal Government (University of Chicago Press, 2004). Pretty much everybody nowadays knows about Senator Joseph McCarthy's "red scare" ravings in the early 1950s about communists in the State Department. There actually weren't very many communists in the State Department, but there were a lot of closeted gay people working in government jobs in Washington D.C., and these were the people victimized by the real witch hunts and purgings. "Over the course of the 1950s and 1960s, approximately 1,000 persons were dismissed from the Department of State for alleged homosexuality." (p. 76)

In theory, the term "security risk" could be applied to anyone who might have a tendency to divulge government secrets. In practice, the term was basically a euphemism for "homosexual." (See pgs. 7-8) The assumption was that homosexuals could be blackmailed into revealing state secrets. However, the best example anyone could come up with of this actually happening involved the head of Austrian intelligence before World War I, and it was never quite clear what the real story was. (pgs. 108-109)

Although Johnson's book focuses almost entirely on the United States, what was happening in the U.S. also had implications for Great Britain. As Johnson writes,

(Interestingly enough, part of Johnson's source for this information is Hodges' biography!) Turing might have felt his professional opportunities getting more and more narrow. With his arrest record, he would certainly have trouble getting security clearance to work on government projects, and he might also be prevented from travelling to the U.S. as he did during the war. Was this enough to make Turing suicidal? I don't know. A book similar to The Lavender Scare but covering the situation in Great Britain might clarify exactly how hot it had gotten under Turing's feet when he took his life.