Turing's Cathedral

by George Dyson

  At the time the computer project was launched in 1946, Veblen occupied room 124 on the ground floor, with bay windows looking out toward the end of Olden Lane. Einstein was directly above, in room 225. Von Neumann was in room 120 on the ground floor, adjacent to the common room, and flanked to the left by secretaries Betty Delsasso in 121 and Gwen Blake in 122. On the second floor, the right wing was occupied by economists Walter W. Stewart in 212, Winfield Riefler in 210, and Robert B. Warren in 213, with Judy Sachs, the librarian, in 215. Stewart, Riefler, and Warren, respectively of the Bank of England, the U.S. Federal Reserve, and the U.S. Treasury, jointly constituted the School of Economics and Politics whose establishment, without the approval of the other faculty, led to Flexner’s resignation in 1939. In the left wing, adjacent to Weyl and Einstein, and above von Neumann, next to the library, was Kurt Gödel, in Fuld 217.

  “Formal logic has to be taken over by mathematicians,” Veblen had announced on New Year’s Eve 1924, when the plans for what would become the Institute for Advanced Study were first taking form in his mind. “There does not exist an adequate logic at the present time, and unless the mathematicians create one, no one else is likely to do so.”10 It was Gödel, above anyone else—and now directly above von Neumann—who proved Veblen’s instincts correct.

  In 1924 both von Neumann and Gödel were working on the logical foundations of mathematics, before Gödel’s incompleteness theorems brought the Hilbert program to a close. Von Neumann “believed in Hilbert’s goal of a final and conclusive axiomatization of mathematics,” according to Stan Ulam, “and yet, in a 1925 paper, in a mysterious flash of intuition, he pointed out the limits of any axiomatic formulation of set theory. That was perhaps a sort of vague forecast of Gödel’s result.”11 The seeds of doubt were sown.

  In September of 1930, at the Königsberg conference on the epistemology of the exact sciences, Gödel made the first, tentative announcement of his incompleteness results. Von Neumann immediately saw the implications, and, as he wrote to Gödel on November 30, 1930, “using the methods you employed so successfully … I achieved a result that seems to me to be remarkable, namely, I was able to show that the consistency of mathematics is unprovable,” only to find out, by return mail, that Gödel had got there first.12 “He was disappointed that he had not first discovered Gödel’s undecidability theorems,” explains Ulam. “He was more than capable of this, had he admitted to himself the possibility that Hilbert was wrong in his program. But it would have meant going against the prevailing thinking of the time.”13

  Von Neumann remained a vocal supporter of Gödel—whose results he recognized as applying to “all systems which permit a formalization”—and never worked on the foundations of mathematics again. “Gödel’s achievement in modern logic is singular and monumental … a landmark which will remain visible far in space and time,” he noted. “The result is remarkable in its quasi-paradoxical ‘self-denial’: It will never be possible to acquire with mathematical means the certainty that mathematics does not contain contradictions.… The subject of logic will never again be the same.”14

  Gödel set the stage for the digital revolution, not only by redefining the powers of formal systems—and lining things up for their physical embodiment by Alan Turing—but by steering von Neumann’s interests from pure logic to applied. It was while attempting to extend Gödel’s results to a more general solution of Hilbert’s Entscheidungsproblem—the “decision problem” of whether provable statements can be distinguished from disprovable statements by strictly mechanical procedures in a finite amount of time—that Turing invented his Universal Machine. All the powers—and limits to those powers—that Gödel’s theorems assigned to formal systems also applied to Turing’s universal machine, including the version that von Neumann, from his office directly below Gödel’s, was now attempting to build.

  Gödel assigned all expressions within the language of the given formal system unique identity numbers—or numerical addresses—forcing them into correspondence with a numerical bureaucracy from which it was impossible to escape. The Gödel numbering is based on an alphabet of primes, with an explicit coding mechanism governing translation between compound expressions and their Gödel numbers—similar to, but without the ambiguity that characterizes the translations from nucleotides to amino acids upon which protein synthesis is based. This representation of all possible concepts by numerical codes seemed to be a purely theoretical construct in 1931.

  “Metamathematical notions (propositions) thus become notions (propositions) about natural numbers or sequences of them; therefore they can (at least in part) be expressed by the symbols of the system … itself,” wrote Gödel in the introduction to his proof.15 Gödel constructed a formula, the Gödel sentence (G) saying, in effect, “The sentence with Gödel number g cannot be proved,” where the details of the system are manipulated so that the Gödel number of G is g. G cannot be proved within the specified system, and so it is true. Since, assuming consistency, its negation cannot be proved, the Gödel sentence is therefore formally undecidable, rendering the system incomplete. Thus Gödel brought Hilbert’s dream of a universal, all-encompassing formalization to a close.

  Gödel arrived at the Institute in the fall of 1933 but, suffering depression, returned to Vienna in May of 1934. After retreating to the sanatorium at Purkersdorf, where he was diagnosed with nervous exhaustion, he returned to Princeton in September of 1935, where he fell into an even more severe depression, resigning his position and returning to Austria at the end of November. He admitted himself to the sanatorium in Rekawinkel, and then recovered sufficiently to spend several weeks with his future wife, Adele Nimbursky (née Porkert), a Viennese cabaret dancer, at the spa in Aflenz.

  Veblen, Marston Morse, and von Neumann (who visited Gödel in Vienna) were determined to bring him back to the Institute, although Aydelotte, who later confided to Gödel’s psychiatrist that “I have always been a little worried by the fact that he does not take more recreation,” maintained his reservations, and, in 1950, when Gödel was finally offered a faculty appointment, “took the point of view that Gödel is not the type of person to be appointed full professor.”16 Nonetheless, Aydelotte supported bringing Gödel back to the United States.

  After his September marriage to Adele, Gödel returned to Princeton in late 1938, but after a semester at Notre Dame, he returned once again to Vienna, in June of 1939, just as war was breaking out. Gödel now found himself caught by the same quasi-paradoxical self-contradiction that had characterized his recent mathematical results. He was born in Brünn, Czechoslovakia, and had naturalized as an Austrian citizen in 1928. After Austria was annexed by the Hitler government in 1938, he lost his teaching position in Vienna and, although not Jewish, was accused of “having travelled in liberal-Jewish circles”; his application to be appointed Dozent neuer Ordnung (Lecturer of the New Order) was declined. With Austria officially nonexistent, he was forced to acquire a German passport, even for a temporary visit to the United States. With the issuance of a German passport, however, came eligibility for German military service, and without fulfilling his military obligation, any request for an exit visa would be denied.

  The German authorities would not grant an exception without a visa from the Americans, and the Americans would not grant a visa without an exception from the Germans. “You will appreciate of course that if Professor Gödel’s difficulty arises from some question relating to military or other matters within the jurisdiction of a foreign government, our consular officer at Vienna would be unable to intervene on his behalf since Professor Gödel is not an American citizen,” the chief of the U.S. Visa Division wrote to Abraham Flexner in October 1939.17

  “Gödel is absolutely irreplaceable; he is the only mathematician alive about whom I would dare to make this statement,” appealed von Neumann, in a letter circulated at the highest diplomatic levels available through Flexner’s Rockefeller Foundation connections at the time. “Salvaging him from the wreck of Europe is one o
f the great single contributions anyone could make.” The Visa Division countered that to be admitted to the United States under a non-quota visa, the applicant had to both hold a current teaching position in the country of residency and be offered a teaching position in the United States. Flexner, Aydelotte, and von Neumann confirmed that Gödel would be “teaching” (even though the Institute had neither students nor classes), but that was not enough. “The objection made against Gödel,” von Neumann explained to Flexner, “is that the two years teaching in the country of origin have to be immediately preceding their application; whereas Gödel was suspended from his position by the Nazis after the Anschluss in 1938. This requirement I think is altogether illogical.”18

  Diplomacy succeeded where logic failed. The German authorities in Vienna granted the Gödels permission to leave, and the American authorities in Washington granted them permission to enter the United States. On January 2, 1940, Gödel cabled von Neumann with the news. “The only complication which remains,” Gödel reported to Aydelotte, “is that I shall have to take the route through Russia and Japan.”19 With visas issued by the Americans on January 8, the Gödels left Berlin for Moscow on January 15, taking the Trans-Siberian Railway to Vladivostok, where they transferred by ship to Yokohama, arriving on February 2, and just missing their intended passage to San Francisco on the Taft, which had sailed on February 1. Aydelotte came to the rescue, wiring $200 to the Gödels at the Yokohama New Grand hotel and booking passage for them on the Cleveland via Honolulu (where Gödel requested another $300) to San Francisco, where they arrived on March 4. They finally arrived in Princeton, by train, on March 9.

  They had escaped just in time. By June, Paris was occupied and Italy had declared war on Britain and France. “My worst premonitions became true,” Stan Ulam wrote to von Neumann on June 18. “My faith in America has almost completely disappeared.”20 The United States did not declare war until December 8, 1941, but many at the Institute were either already displaced by the war or engaged in preparing for it. Von Neumann was already immersed in weapons research; there was talk of the “uranium problem”; Veblen and Morse were both preparing to return to positions with the Army Proving Ground.

  While von Neumann was looking for targets that should be bombed, the Institute’s humanists were enlisted (by the American Commission for the Protection and Salvage of Artistic and Historic Monuments in War Areas) to help identify targets that should not be bombed. Erwin Panofsky, the art historian, was responsible for identifying culturally important resources in Germany, while the Institute’s classicists and archaeologists helped supply similar intelligence for the Mediterranean and Middle East. Even Einstein was debriefed.

  As the war dragged on, the Institute battened down the hatches, conserving fuel by “trying to heat the common room from the fireplace,” and otherwise attempting to keep spirits up. Supplies and materials grew scarce, and purchases were postponed, while the Institute community continued to expand. “Will you please advise us if there is any law against using a trailer for passengers,” Bernetta Miller wrote to the Department of Motor Vehicles, when the station wagon that shuttled between the Institute and the train station became inadequate for the passenger load.21

  The Gödels, holding German passports, were required to register as enemy aliens, and could not leave Princeton without written permission from the Department of Justice in Trenton, even for routine visits to their doctors in New York. “I continue to be a little troubled about the idea of our so-called enemy aliens traveling too far afield,” wrote Aydelotte in December 1941, who had to intermediate with local authorities for the release of individuals picked up on suspicion when they left the IAS.22

  “I have never taken an oath of allegiance to Germany. My wife…has never taken an oath of allegiance to Germany,” Gödel wrote to the Department of Justice in Washington, D.C., requesting to amend their status under the Alien Registration Act. “Since we came to this country on German passports and were under the impression that Austrian citizenship was no longer recognized in this country, and were not advised to the contrary when we questioned the officials on this point, we felt that we had no choice but to register as Germans.”23

  “The procedure for such amendment or correction has not, as yet, been set up but in all probability it will be soon,” Earl G. Harrison, special assistant to the attorney general, answered. “In the meantime your letter will be filed appropriately with your record in the Alien Registration Division.” Aydelotte stepped in to help. “When Dr. and Mrs. Gödel filed their declaration of intention they were put down as of German nationality, he being listed as born in Brünn, Germany, and she as being born in Vienna, Germany. These cities were, of course, not German at the time that Dr. and Mrs. Gödel were born and these statements on the declaration of intention should, it seems to me, be corrected,” he wrote to the U.S. District Court. “I am at a loss to know just how to go about it to get this correction made.”24

  “As Mr. Gödel is a naturalized Austrian citizen and Mrs. Gödel an Austrian Citizen through birth, their nationality, as far as the declaration of intention is concerned, will have to remain German due to the fact that this Country recognized Germany’s conquest of Austria thereby making it a part of the German Reich,” came the answer from the court. “This is borne out by the issuance of a German passport. However, when Mr. and Mrs. Gödel file their petitions for citizenship, this status will be changed in accordance with the modified rule regarding Austrians.”25

  Despite these obstacles, Gödel produced his third landmark work, a monograph on the consistency of the continuum hypothesis, published in 1941. “Gödel obtained this result by a very ingenious construction which uses the tricks of his proofs in formal logics! Did you hear about this?” von Neumann wrote to Stan Ulam in May of 1941. “Please send Gödel continuum hypothesis notes,” Alan Turing cabled from King’s College, Cambridge, on December 16.26 Proposed by George Cantor in 1877, and presented in 1900 as the first of Hilbert’s twenty-three unsolved problems, the continuum hypothesis states that the set of real numbers (the continuum) is the smallest infinity whose size is larger than the set of integers, and that no intermediate-sized infinities lie in between. Gödel proved that within a strictly defined system it was impossible to disprove the hypothesis—a result that has been strengthened in recent years.

  Unable to return to Austria, Gödel grew more anxious. “The evidence we have had here of Dr. Gödel’s difficulties comes from the fact that he thinks the radiators and ice box in his apartment give off some kind of poison gas,” Frank Aydelotte wrote to Max Gruenthal, Gödel’s psychiatrist, in December of 1941. “He has accordingly had them removed, which makes the apartment a pretty uncomfortable place in the winter time. Dr. Gödel seems to have no such distrust of the heating plant at the Institute and he carries on his work here very successfully.”27

  Aydelotte requested a prognosis, and finally got to the point. “I should like also especially to know,” he asked, “whether you consider that there is any danger of his malady taking a violent form.” Dr. Gruenthal wrote back, politely but tersely, refusing to discuss Gödel’s condition without his patient’s permission, but willing “to reassure you insofar of his malady taking a violent form.”28

  With no hope of returning to Europe, the Gödels settled down in Princeton and applied for permanent residency in the United States. One more obstacle remained. Once Gödel’s status was recognized as formerly Austrian, not German—allowing him some security on the path to U.S. citizenship—he became eligible for the draft, and was classified 1A. In April of 1943 he was ordered to report to the Trenton Army Induction Center for examination.

  “Dr. Gödel, like most refugees from Nazi Germany, is eager to do anything he can in support of the American war effort,” Aydelotte answered the draft board on Gödel’s behalf, “but under the circumstances I think I ought to inform the Selective Service Board that Dr. Gödel has twice since he has been in Princeton shown such signs of mental and nervous instabi
lity as to cause the doctors who were consulted to diagnose him as a psychopathic case.” Aydelotte went on to extol Gödel’s genius, while asking the Draft Board to consider that “this ability, however, is unfortunately accompanied by certain mental symptoms which, while they do not prevent active work in mathematics, might prove serious from the standpoint of the Army.”29

  “Although the Board is in sympathy with your knowledge of Mr. Gödel’s condition, we are unable to effect a disqualification for this man at the local board,” the draft board answered. “It will be necessary for him to be forwarded to the induction station for the Army examination.”30 The army had its own psychiatrists, and they would make the decision concerning Dr. Gödel for themselves.

  “I have secured a certain amount of additional evidence concerning him which I believe the Selective Service Board would be glad to have,” Aydelotte replied, explaining that during Gödel’s convalescence in Austria he “had the idea that all the sanitarium food was poisoned and he would eat only things that were prepared and brought to him by a young woman friend of the family (whom he later married) and then only on condition that she eat with him from the same plate and with the same spoon,” and that his mother “was so frightened concerning his condition that she slept always in a locked room at night.”31 With this statement, Gödel’s Selective Service file comes to an end.