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

by David Leavitt

  In peacetime the International Congress of Mathema-ticians took place at regular four-year intervals. Because of the First World War, however, there had been no congress in 1916, whereas in 1920 and 1924, because of postwar anger at German nationalism, Germany was pointedly not invited to send a delegation. In 1928 the Italian organizers of the congress did invite the Germans. This time, however, the mathematician Ludwig Bieberbach (1886–1982), working in conjunction with L. E. J. Brouwer (1881–1966), organized a boycott to protest Germany’s exclusion from earlier congresses and, more generally, the Treaty of Versailles. Hilbert did not support the boycott, and wrote in response to a letter sent out by Bieberbach, “We are convinced that pursuing Herr Bieberbach’s way will bring misfortune to German science and will expose us all to justifiable criticism from well disposed sides. . . . It appears under the present circumstances a command of rectitude and the most elementary courtesy to take a friendly attitude toward the Congress.” In the end, Hilbert himself led a delegation of sixty-seven mathematicians to Bologna, where he underlined the pacifist theme in the speech he gave:

  Let us consider that we as mathematicians stand on the highest pinnacle of the cultivation of the exact sciences. We have no other choice than to assume this highest place, because all limits, especially national ones, are contrary to the nature of mathematics. It is a complete misunderstanding of our science to construct differences according to peoples and races, and the reasons for which this has been done are very shabby ones.

  Mathematics knows no races. . . . For mathematics, the whole cultural world is a single country.

  Hilbert suggests, here, a close parallel between pacifism and formalism. Racial and national differences were mere “suggestive meanings” from which the signs had to be liberated if peace was to be achieved and then maintained. The boundaryless landscape he described brings to mind Russell’s evocation of the mathematical edifice emerging “from the autumn mist as the traveller ascends an Italian hill-side”; an ideal realm unsullied by political division. Alas, not many years later the Berlin correspondent of the Times of London would be reporting on a meeting of mathematicians

  at Berlin University to consider the place of their science in the Third Reich. It was stated that German mathematics would remain those of the “Faustian man,” that logic alone was no sufficient basis for them, and that the Germanic intuition which had produced the concepts of infinity was superior to the logical equipment which the French and Italians had brought to bear on the subject. Mathematics was a heroic science which reduced chaos to order. National Socialism had the same task and demanded the same qualities. So the “spiritual connexion” between them and the new order was established—by a mixture of logic and intuition.

  Hardy, too, took note of national differences in mathematics, remarking in his rather skeptical essay on Hilbertian proof theory, “I am primarily interested at the moment in the formalist school, first because it is perhaps the natural instinct of a mathematician (when it does not conflict with stronger desires) to be as formalistic as he can, secondly because I am sure that much too little attention has been paid to Formalism in England. . . .” English pragmatism led to a natural distrust of German formalism, the creepy impersonality of which made it as appealing to the propaganda machine of the Third Reich as to Hilbert with his dreams of a world without borders.

  Indeed, one can read into Hilbert’s program an attempt, through mathematics, to ward off the coming nightmare, just as one can read into Kurt Gödel’s subsequent derailing of that program both the death knell of prewar idealism and the advent of a bloody, off-kilter epoch in which the prevailing metaphors would be of chaos and night, not order and morning. Like Frege and Russell before him, Hilbert hoped to establish once and for all the security of the mathematical landscape (and by extension, the security of Europe): to give a proof that for the truth or falsity of any mathematical assertion—even long unproven assertions such as Goldbach’s conjecture, which holds simply that any positive integer greater than 2 is the sum of two prime numbers—there had to exist, somewhere, a proof. And not just any proof; on the contrary, lest some naysayer from the fringe of mathematics should balk, this proof of provability had to be “absolute,” by which Hilbert meant that it should use a minimum number of principles of inference and should not rely upon the consistency of another set of axioms. Only an absolute proof would guarantee that a mathematical description was uninfected by hidden contradictions such as Russell’s antimony. Already, in a lecture on infinity and the revolutionary work of Georg Cantor (1845–1918), Hilbert had spoken of the contradictions that “appeared, sporadically at first, then ever more severely and ominously” in mathematics, summing up,

  Let us admit that the situation in which we presently find ourselves with respect to the paradoxes is in the long run intolerable. Just think: in mathematics, this paragon of reliability and truth, the very notions and inferences, as everyone learns, teaches, and uses them, lead to absurdities. And where else would reliability and truth be found if even mathematical thinking fails us?

  Yet Hilbert would not admit defeat. On the contrary, he insisted that there had to be

  a completely satisfactory way of escaping the paradoxes without committing treason against our science. . . .

  We shall carefully investigate those ways of forming notions and those modes of inference that are fruitful; we shall nurse them, support them, and make them usable, wherever there is the slightest promise of success. No one shall be able to drive us from the paradise that Cantor created for us.*

  An absolute proof that mathematics was airtight would eliminate forever the risk of being expelled—mathematical Adams and Eves—from that Eden.

  Viewed in the light of its imminent decimation, not to mention the decimation of Europe, Hilbert’s program comes across as highly idealistic, even Platonic. At its heart, after all, is the assumption that even undiscovered proofs already exist “somewhere out there”; doubt is taken away, and the mathematician reassured that, with enough time and hard work, he or she can lasso any beast that lurks in the metaphysical wilderness. The program was the perfect expression of Hilbert’s determination to endow younger mathematicians with the will to discover, since it sought to remove from the mathematical endeavor any cause for despair or even uncertainty. Instead, it promised a way out of any maze. “Wir müssen wissen, Wir werden wissen”: though the unicorn itself might not exist, somewhere in the world there had to be evidence that unicorns either were or were not and, if they were, that their existence could be shown by some definite method. Still, Hilbert’s very language suggests at least a trace of anxiety. After all, in the Judeo-Christian universe, Edens are by nature temporary. What God gives, God can also take away. Through his reference to “paradise,” Hilbert seems to be bowing, albeit subconsciously, to the knowledge that though paradise may be infinite, our stay there is decidedly finite. For a serpent lurks in the trees—the paradox.

  4.

  On all three counts—completeness, consistency, and decidability—Hilbert turned out to be wrong. In a 1931 paper entitled “On Formally Undecidable Propositions of Principia Mathematica and Related Systems,” the young Austrian mathematician Kurt Gödel (1906–1978) showed incontrovertibly that mathematics as we know it cannot be used to prove itself consistent or complete. Ironically, he made his first public announcement of his findings in Königsberg in 1930—the day before David Hilbert was made an honorary citizen of the city and gave his famous address.

  Gödel’s method was ingenious. To begin with, he posited a system in which arithmetical formulae, theorems, and sequences could be expressed in the form of numbers. First, he wrote out the basic symbols—the alphabet—of arithmetic and assigned to each symbol a number (“not” was 1, “or” was 2, etc.). Likewise, numbers were assigned to the basic marks of punctuation, addition, and multiplication (a left parenthesis was 8, a multiplication sign was 12, etc.). Finally, numbers were given for three types of variables: numerical variables, whic
h could be replaced with numerals and numerical expressions; sentential variables, which could be replaced with formulae; and predicate variables, which could be replaced with predicates. With this system, Gödel showed, it was possible to express any arithmetical sentence numerically. For example, the sentence 1 + 1 = 2 would first be rewritten in the form

  s 0 + s 0 = s s 0

  with “s” in this case meaning “the immediate successor of.” These signs would then be rewritten giving their numerical equivalents:

  s 0 + s 0 = s s 0

  7 6 11 7 6 5 7 7 6

  Successive prime numbers each raised to the power of the numbers listed above would now be multiplied together:

  27 × 36 × 511 × 77 × 116 × 135 × 177 × 197 × 236 = ?

  The answer to this multiplication is, admittedly, a number so huge as to defy calculation. Yet here is the important point: that number, according to the fundamental theorem of arithmetic,* can be broken down only one way, into the prime factors listed above; it represents the unique coding of a particular equation. Thus, if one were furnished with the mystery number, it would simply be a matter of calculation to break it down into discrete units that could be translated into 1 + 1 = 2. Nor does the laboriousness of the calculation really matter, since Gödel’s intent was less to offer a working model than a theoretical framework, to show that in principle there existed a means by which to translate arithmetical sentences into Gödel numbers, and then to translate Gödel numbers back into arithmetical sentences. True, it would take a computer to do the calculations. Though Gödel was not looking forward to the computer—at least not consciously—much in his work foreshadowed its invention.

  Yet the system Gödel developed allowed him to do far more than merely code mathematical statements as numbers: it made it possible for him to invent a way of expressing metamathematical sentences about a formal system within that system. In other words, he determined a means not only to rephrase sentences like 2 + 3 = 5 as long numbers but to rephrase sentences like “2 + 3 = 5 is an arithmetical formula” as long numbers, by first reformulating the sentences into symbolic “strings” and then translating the strings into his numerical code. He wasn’t doing this for his health; the point was to code one particular metamathematical sentence—the one that brought the walls tumbling down.

  This crucial sentence reads as follows: “Formula G, for which the Gödel number is g, states that there is a formula with Gödel number g that is not provable within PM or any related system.” Sound familiar? Paradoxes always have that hollow ring to them. Essentially Gödel was positing a formula that stated its own unprovability. If such a formula is true, then it is not provable. If it is provable, then it is not true. Yet in a complete mathematical system, one should be able to prove or disprove every statement made using that system, while in a consistent mathematical system, it should be impossible either to prove a statement that is not true or to disprove a statement that is true. Gödel had just done both. If, in other words, PM and its related systems—all related systems, in effect the whole of arithmetic—was consistent, it could not be complete. And though one could in principle add an axiom in order to make the system consistent, the consistency of this new, stronger system would remain unprovable within that system. Indeed, one could continue adding axioms—an infinity of axioms—each time making the system stronger; yet the consistency of each new system would remain impossible to prove within that system.

  In effect, Gödel had proven that statements could be true but not provable even in systems encompassing the full scope of ordinary mathematics. This meant that any of a host of mathematical assertions might be true but not necessarily provable. For example, Goldbach’s conjecture had, by the time Gödel published his theorem, remained unproven for almost 190 years.* Mathematicians in search of solutions to this and other unsolved problems were now denied any assurance that the treasures they were hunting even existed. No longer could the words “truth” and “proof” be considered mathematically synonymous—a shattering blow to the Hilbert program.

  Not surprisingly, Hilbert’s first reaction to Gödel’s paper was one of anger. As his biographer Constance Reid writes,

  In the highly ingenious work of Gödel, Hilbert saw, intellectually, that the goal toward which he had directed much effort since the beginning of the century . . . could not be achieved. . . . The boundless confidence in the power of human thought which had led him inexorably to this last great work of his career now made it almost impossible for him to accept Gödel’s result emotionally. There was also perhaps the quite human rejection of the fact that Gödel’s discovery was a verification of certain indications, the significance of which he himself had up to now refused to recognize, that the framework of formalism was not strong enough for the burden he wanted it to carry.

  Rather quickly, however, Hilbert adjusted and began to make an effort to deal with the new world Gödel had ushered in, heartened perhaps by Gödel’s own admiration for Hilbert’s work, as well as by the realization “that proof theory still could be fruitfully developed without keeping to the original program.”

  As for Gödel, the impact of his paper would be long-lasting. Although the proof left open the possibility that some new method might be found for proving the consistency of PM from outside, it made absolutely clear that no such proof could be written using the axioms and rules of PM. But this rendered PM’s claims to absoluteness null and void. Gödel had brought to an end the age of the totalizing project, of the Casaubon-like effort to provide a key to all mathematics, and after 1931 no one would try again to write a book with a title as all-encompassing as Principia Mathematica.

  Of Russell and Whitehead’s imposing tome, Gödel wrote in 1944, “How can one expect to solve mathematical problems systematically by mere analysis of the concepts occurring if our analysis so far does not even suffice to set up the axioms?” One might have expected him to stop there. Surprisingly, however, he goes on to write,

  There is no need to give up hope. Leibniz did not in his writings about the Characteristica universalis speak of a utopian project; if we are to believe his words he had developed this calculus of reasoning to a large extent, but was waiting with its publication till the seed could fall on fertile ground.

  Gödel then quotes Leibniz as claiming that within a period of five years “humanity would have a new kind of an instrument increasing the powers of reason far more than any optical instrument has ever aided the power of vision.”

  How seriously are we to take this nostalgic paean to Leibniz’s ancient fantasy—a fantasy, moreover, the foundational impossibility of which Gödel himself, more than anyone else, had shown to be law? Perhaps the nightmare that the dream had turned into—the hole-riddled landscape that replaced Russell’s stately Italian hillside—proved too much to bear. Gödel’s later years were marked by increasingly serious bouts of mental illness, during which he developed a terror of refrigerators and radiators, and became inordinately fond, as Turing was, of the Disney film Snow White and the Seven Dwarfs. His death itself befitted a career built on the exploration of paradox: convinced that unnamed strangers were trying to poison him, he refused to eat, and starved to death. Yet his proofs outlived him and affected the pursuit of pure mathematics as profoundly as Einstein’s theory of relativity did the study of physics. Before his paper, mathematicians had treated logical paradoxes as holes in a landscape the fundamental soundness of which they took for granted. Such anomalies, they believed, could either be filled in or circumnavigated. But now Gödel had shown that the landscape was by its very nature unstable. Beneath the surface fault lines ran. Thanks to Gödel, paradise had been lost, and the new terrain into which mathematicians had been driven was at best inhospitable, at worst hostile.

  That, at least, was the perspective of the old guard. For younger mathematicians, Gödel’s work opened up the possibility of a freer, more intuitive approach to the discipline even as it closed off forever old totalizing dreams. True, he had shown that it was impos
sible to prove the consistency of the axioms, but as Simon Singh notes,

  this did not necessarily mean that they were inconsistent. In their hearts many mathematicians still believed that their mathematics would remain consistent, but in their minds they could not prove it. Many years later the great number theorist André Weil would say: “God exists since mathematics is consistent, and the Devil exists since we cannot prove it.”

  It would have alarmed Turing to learn that the question into which he was delving was so theological.

  * * *

  *Coincidentally, P. N. Furbank, Forster’s biographer, would be named Turing’s literary executor.

  *In the full quotation, Clive reflects that Maurice is “bourgeois, unfinished and stupid.”

  *His closest friendships were with Kenneth Harrison, Fred Clayton (who later wrote a protohomosexual novel, The Cloven Pine, under the pseudonym Frank Clare), and James Atkins. It was with Atkins that he had the extended, on-and-off sexual relationship, about which he had ambivalent feelings, because Atkins, in his mind, could not compare with the lost Christopher.