The Man Who Knew Too Much: Alan Turing and the Invention of the Computer (Great Discoveries)

by David Leavitt

  Turing

  Must have been alluring

  To get made a don

  So early on.

  The fellowship brought with it £300 per annum—not a lot, but enough to keep him going while he conducted his research. It was at this point that he first started to think about one of the core problems of mathematics: the Entschei-dungsproblem, or, as it was known in English, the decision problem.

  2.

  Turing believes machines think

  Turing lies with men

  Therefore machines do not think

  When Alan Turing included this mordant syllogism in a 1952 letter to his friend Norman Routledge, he was not only alluding to the fearful possibility that his behavior would lead to the suppression of his ideas; he was also calling up—particularly through his use of the locution “to lie with”—the famed “liar’s paradox.” This paradox can be traced back to the fourth century BC, when the Cretan philosopher Epimenides declared, “All Cretans are liars, as a Cretan poet has told me.” Later Eubulides refined (which in mathematics often means generalized) this paradox to the statement “I am lying,” and still later, in the fourteenth century AD, the French philosopher Jean Buridan refined it further by writing, “All statements on this page are false,” on an otherwise blank page.

  In essence, the liar’s paradox works like this. Take the statement “All statements on this page are false.” If this statement is true, then the one statement written on the page—“All statements on this page are false”—is false. But if it is false, then the statement written on the page must be true—and it is on the page on which all statements are false . . . and on and on.* Stoned undergraduates have for years stared up at ceilings pondering the implications of the paradox, which I first learned about in the late 1960s, from an episode of Star Trek called “I, Mudd.” At episode’s end, the eponymous villain, Harry Mudd, incapacitates a superandroid called Norman by compelling him to process a version of the liar’s paradox. As Norman spits out the running loop of contradictions (“everything I say is a lie, therefore I am lying, therefore everything I say is the truth”), his speech gets faster and his voice gets higher in the manner of a tape being played at an accelerated speed. Eventually he more or less explodes, then shuts down—and that is the point. Absurd, contradictory statements are disabling. If you think about the liar’s paradox too much, like Norman, it’ll blow your mind.

  Of course, a certain kind of astute reader who believes in the “real world” (someone, in fact, rather like Wittgenstein) will here raise an objection or two, pointing out that when I implement the liar’s paradox in its most watertight form—when I say, “I am lying”—I am neither telling the truth in the sense that I tell the truth when I say, “I am writing a book about Alan Turing,” nor lying in the sense that I lie when I tell my editor I’m further along on that book than I actually am. Instead, I am making an intellectual parry in an arena where statements are symbols, and where meanings matter less than the relations between them. This is the arena in which the battle to establish a solid foundation for mathematical thought has generally been fought—a battle in the course of which many luminaries have fallen. Still more mathematicians have refused to venture anywhere near the place. When I asked a Portuguese mathematician of my acquaintance whether he had any insight to offer me on the subject, he replied, “The foundations of mathematics are full of holes and I never felt comfortable dealing with such things.”

  Full of holes. Earlier generations of mathematicians assumed that the stability of the landscape on which mathematical structures were built was guaranteed by God or nature. They strode in like pioneers or surveyors, their task to map the fundamentals and in so doing secure the territory that future generations would colonize. But then the holes—of which the liar’s paradox is merely one—started popping up, and the mathematicians started falling in. Never mind! Each hole could be plugged. But soon enough another would open, and another, and another . . .

  Bertrand Russell (1872–1970) spoke for any number of idealistic mathematicians when he wrote in 1907,

  The discovery that all mathematics follows inevitably from a small collection of fundamental laws, is one which immeasurably enhances the intellectual beauty of the whole: to those who have been oppressed by the fragmentary and incomplete nature of most existing chains of deduction, this discovery comes with all the overwhelming force of a revelation: like a palace emerging from the autumn mist as the traveller ascends an Italian hill-side, the stately storeys of the mathematical edifice appear in their due order and proportion, with a new perfection in every part.

  I remember that when I read George Eliot’s Middlemarch in college, I was particularly fascinated by the character of Mr. Casaubon, whose lifework was a Key to All Mythologies that he could never finish. If Mr. Casaubon’s Key was doomed to incompletion, my astute professor observed, it was at least in part because “totalizing projects,” by their very nature, ramify endlessly; they cannot hope to harness the multitude of tiny details demanded by words like “all,” just as they cannot hope to articulate every generalization to which their premises (in this case, the idea that all mythologies have a single key) give rise. Perhaps without realizing it, my professor was making a mathematical statement—she was asserting the existence of both the infinite and the infinitesimal—and her objections to Mr. Casaubon’s Key hold as well for any number of attempts on the part of mathematicians to establish a Key to All Mathematics.

  Consider, for instance, the never-written project of which G. W. Leibniz (1646–1716) dreamed at the end of the seventeenth century: to create a special mathematical language by means of which he could write a sort of encyclopedia comprising all human knowledge. This language would be made up of mathematical symbols that could be manipulated according to rules of deduction. Leibniz called this program a calculus ratiocinator. “If controversies were to arise,” Russell wrote (ventriloquizing Leibniz), “there would be no more need of disputation between two philosophers than between two accountants. For it would suffice to take their pens in their hands, to sit down to their desks, and to say to each other (with a friend as witness, if they liked), ‘Let us calculate.’”

  Doomed to failure though it was, Leibniz’s “grand program” did at the very least give rise to the discipline of symbolic logic as it was later developed by George Boole (1815–1864) and Gottlob Frege (1848–1925). Boole was a schoolmaster before he became professor of mathematics at Queen’s College, Cork, and perhaps for this reason his writings—principally The Mathematical Analysis of Logic, published in 1847—display little of Leibniz’s ostentation; on the contrary, an appealing modesty and remoteness from worldly ambition (also seen in Turing) are evident in his work. In essence, Boole’s objective was to establish a system for transforming logical propositions into equations. Thus, even as he employed real-world examples (white things, horned things, sheep, horned white sheep), his emphasis was in fact on the dissociation of the symbols he used from the situations they described; in his hands, episodes that required deductive reasoning or decision making were reduced to basic procedures in which the operative terms were “and” and “not,” while the white sheep and the horned sheep were w and h.* In such a system, Boole wrote, “every process will represent deduction, every mathematical consequence will express a logical inference. The generality of the method will even permit us to express arbitrary operations of the intellect, and thus lead to the demonstration of general theorems of ordinary mathematics.”

  Frege* took Boole’s ideas a step farther, not just by complicating them but by using them to lay the foundations for “logicism,” the principal thesis of which was “that arithmetic is a branch of logic and need not borrow any ground of proof whatever from either experience or intuition.” His Begriffs-schrift, published in 1879, sought to establish “a formal language, modeled on that of arithmetic, for pure thought.” With such a language, stories about the stuff of the world—teapots, cars, dogs, wicked queens, apples, not to mention
Boole’s white sheep and horned sheep—could be distilled into strings of symbols the sense of which was completely beside the point. Frege also provided a strict definition of mathematical proof that has not been challenged, and in his 1884 Die Grundlagen der Arithmetik (The Foundations of Arithmetic) took on the question of what cardinal numbers actually are,† defining each number n as the class or set of all collections with n members: “7,” for example, would be defined as the set of all collections with seven members, everything from the Seven Dwarfs to the Seven Hills of Rome to the seven letters in the word “letters.” In such a system, as Russell later explained, a “particular number is not identical with any collection of terms having that number: the number 3 is not identical with the trio consisting of Brown, Jones, and Robinson. The number 3 is something which all trios have in common, and which distinguishes them from all other collections.” This definition was more rigorous than those which preceded it, in that it drew a distinction between the collection itself (Brown, Jones, and Robinson) and its category (3); it also contributed significantly toward Frege’s goal of constructing an axiomatic theory of arithmetic.

  The first volume of Frege’s magnum opus, Die Grund-gesetze der Arithmetik (The Basic Laws of Arithmetic), was published in 1893. In contrast to the Grundlagen, which included no symbolism and only sketches of proofs (as opposed to proofs that would meet Frege’s own rigorous standard), the Grundgesetze aspired to achieve the goal of using logic to establish a foundation for the practice of mathematics. But then on June 16, 1902, just as the second volume was about to go to press, Russell sent Frege a letter (in German) in which, having first praised the Grundgesetze, he noted, “There is just one point where I have encountered a difficulty.” He then effectively undermined Frege’s entire program.

  The problem, in essence, had to do with the idea of sets of sets. Already Frege had defined the number 7 as the set of all sets with seven members: the Seven Deadly Sins, the Seven Hills of Rome, the Seven Dwarfs, etc. This set might be imagined as a box labeled “Sets with 7 Members.” A similar box might be labeled “Sets with an Even Number of Members,” another simply “Couples.” Some sets could be members of themselves, and some could not. Consider, for instance, the set of all dogs, of which my fox terrier, Tolo, is a member. Is this set a member of itself? No: as Russell put it, mankind is not a man, just as “all dogs” is not any particular dog. Other sets, however—for example, the set consisting of “things that are not a dog”—are members of themselves, since whatever “a thing that is not a dog” is, it is most emphatically not Tolo or any other particular dog. Likewise “the set of all sets with infinite members” is a member of itself, since it has infinite members.

  This was where the “difficulty” entered in. Imagine a set labeled “Sets That Are not Members of Themselves.” Is this set a member of itself? If it is, then by definition it is one of the sets that are not members of themselves, in which case it is not a member of itself. If it is not, then it is not one of the sets that are not members of themselves, in which case it is a member of itself. Russell liked to phrase this cousin of the liar’s paradox, which would come to be known as Russell’s paradox or Russell’s antimony, by positing a male barber who daily shaves every man in his town who does not shave himself, and no one else. If the barber does not shave himself, he is one of the men who do not shave themselves, and thus must shave himself. On the other hand, if he does shave himself, he is one of the men who do shave themselves, and therefore he must not shave himself.

  Russell’s letter devastated Frege, who had to hurry to insert an appendix into the second volume of the Grundgesetze acknowledging the contradiction (or as Russell called it, more ominously, the “Contradiction”). Naturally distraught, he replied on June 22,

  Your discovery of the contradiction caused me the greatest surprise and, I would almost say, consternation, since it has shaken the basis on which I intended to build arithmetic. . . . It is all the more serious since, with the loss of my Rule V, not only the foundations of my arithmetic, but also the sole possible foundations of arithmetic, seem to vanish.

  Subsequently Frege and Russell worked together to try to resolve the paradox or, short of that, to find a means of keeping it from infecting the foundational system that they were trying to build. Frege, however, soon gave up on this ambition, focusing his attention instead on the philosophy of language, while after much effort Russell did find a rather serpentine route around the paradox he himself had brought into the world. Unfortunately, the complexities of the jerry-rigging that Russell had to perform meant that his magnum opus—the three-volume Principia Mathematica, coauthored with Alfred North Whitehead, and describing a formalized mathematical system based on a set of axioms (general propositions the truth of which is self-evident) and rules of inference through which any piece of correct mathematical reasoning could be expressed*—was both unwieldy and difficult to use.

  Still, the Principia Mathematica did work—and well enough that in 1928, when the German mathematician David Hilbert (1862–1943) gave a famous address calling for proofs of the completeness, consistency, and decidability of mathematics, PM, as it was commonly called, provided the testing ground on which Kurt Gödel and, later, Alan Turing tried their hands. Gödel tackled completeness and consistency, Turing decidability. The results changed mathematics irrevocably—and took it in directions of which Frege had not dreamed.

  3.

  Hilbert’s ambition was to establish and secure the foundations of formalized mathematical systems. PM, for all its cumbersomeness, is the classic example of such a system, in that it was designed so that from its axioms and rules of inference any true mathematical sentence could be derived. Yet Hilbert’s program differed from Russell’s and Frege’s on two key philosophical points. First, Hilbert repudiated what Hardy called “the extreme Russellian doctrine, that all mathematics is logic and that mathematics has no fundamentals of its own,” allying himself instead with Kant, who argued “that mathematics has at its disposal a content secured independently of all logic and hence can never be provided with a foundation by means of logic alone.” Second, whereas Russell viewed logic and mathematics, in Hardy’s words, as “substantial sciences which in some way give us information concerning the form and structure of reality” and argued that “mathematical theorems have meanings, which we can understand directly, and this is just what is important about them,” Hilbert viewed mathematics as a formalized system, in which the elementary signs were drained of all meaning. Postulates and theorems would thus be regarded as strings of marks that could be put together, taken apart, and put together again in a new way simply by applying a preestablished set of rules.

  Hilbert’s invocation of Kant provoked skepticism in Hardy, who made rather facetious fun of his faith in “concrete signs,” writing, “I had better state at once what is to me a fatal objection to this view. If Hilbert has made the Hilbert mathematics with a particular series of marks on a particular sheet of paper, and I copy them on another sheet, have I made a new mathematics? Surely it is the same mathematics and that even if he writes in pencil and I in ink, and his marks are black and mine are red . . .” For Hardy, the axioms of formalist mathematics could be likened to “the chessmen, the bat, ball and stumps, the material with which we play. . . . To use Weyl’s illustration, we are playing chess. The axioms correspond to the given position of the pieces; the process of proof to the rules for moving them; and the demonstrable formulae to all possible positions which can occur in the game.” But the game has no meaning in the sense that the king has no kingdom, the queen no lover, and the pawns no land to till; it is “cardinal in Hilbert’s logic that, however the formulae of the system may have been suggested, the ‘meanings’ which suggested them lie entirely outside the system, so that the ‘meaning’ of a formula is to be forgotten immediately it is written down.”

  Hardy’s objections notwithstanding, formalist mathematics allowed Hilbert to make an important step forward. Just as it is possibl
e to discuss and analyze a particular game of chess, it is also possible to make general statements or judgments about chess. Now Hilbert showed that, by the same logic, one could make statements about a formalized (if meaningless) system. Such statements Hilbert defined as falling under the category of “metamathematics.” Thus (to borrow an example from Ernest Nagel and John R. Newman), 2 + 3 = 5 is a mathematical expression. But the statement “2 + 3 = 5 is an arithmetical formula” belongs to metamathematics “because it characterizes a certain string of arithmetical signs as being a formula.” Likewise the statement “Any formalized mathematical system is complete, consistent, and decidable” belongs to metamathematics. By complete, Hilbert meant that within that system, any true statement could be formally proven and any false statement formally disproven. By consistent, he meant that within that system, no invalid statement, such as 2 + 2 = 5 or 1 = 0, could be arrived at through a valid process of proof. Lastly, by decidable, he meant that within that system, there could be shown to be a “definite method” by means of which the truth or falsity of any statement might be ascertained. This last question was commonly referred to by its original German name: the Entscheidungsproblem, or “decision problem.”

  So strong was Hilbert’s confidence in these assertions that when, in an address delivered in 1928 in Bologna, he asked for proofs of them, he took it for granted that the call would yield positive results. As early as 1900, in a famous speech in Paris, he had declared that the “conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus.” In 1930 he went further, avowing in a speech occasioned by his being made an honorary citizen of his native Königsberg that “there is no such thing as an unsolvable problem.” It was in this speech, after once again disparaging “the foolish ignorabimus,” that he made his famous exhortation: “Wir müssen wissen, Wir werden wissen.” (“We must know, we shall know.”)