Turing's Cathedral

Home > Other > Turing's Cathedral > Page 15
Turing's Cathedral Page 15

by George Dyson


  Gödel, who had first been brought to the Institute on a stipend of $200 per month, received a raise to $4,000 per year upon his return in 1940. His salary was paid by the Rockefeller Foundation, under an arrangement negotiated one year at a time. With the war over, von Neumann campaigned for a permanent appointment. “Gödel did some of his best work (continuum hypothesis) at the Institute—actually at a time when he was less normal than now,” von Neumann argued. “The Institute is clearly committed to support him, and it is ungracious and undignified to continue a man of Gödel’s merit in the present arrangement forever.” As to the argument that his best work was already behind him, “he may easily do more work in mathematics proper,” von Neumann continued. “His probability of doing some is no worse than that of most mathematicians past 35.”32

  On December 19, 1945, Gödel was made a permanent member, with a stipend of $6,000 and, in an evident concession to those who opposed his appointment, “it was resolved that Professor Gödel’s stipend as a permanent member should not be drawn from the Mathematics budget but should rather come from general Institute funds.”33

  The Gödels lived in a series of rented apartments and, in 1949, purchased a house on Linden Lane for $12,500, taking advantage of an Institute mortgage at 4 percent. “We have found a place which is very convenient for us and which (so we both think) is exceptionally pretty,” Gödel wrote to Oppenheimer. “We hope we shall soon have the pleasure of seeing you and Mrs. Oppenheimer in our new home and letting you judge for yourself.”34

  After completing his work on the continuum hypothesis, Gödel became preoccupied with two areas of research: cosmology, as a result of having discovered a solution to Einstein’s equations that implied a rotating universe; and the legacy of Gottfried Wilhelm Leibniz, the seventeenth-century pioneer of calculus, binary arithmetic, universal language, the Monadology, and much else. “He seemed to believe,” said Stan Ulam, “that much of Leibniz’s work including mathematical logic and computing has been lost or concealed.” Critics dismissed Gödel’s study of the Leibniz manuscripts as a waste of his mathematical talents, verging on the occult, but according to von Neumann, “a man of his caliber and record ought to be the sole judge of what he does.”35

  In early 1946, when von Neumann was authorized to proceed with building a computer at the Institute, Herman Goldstine and Arthur Burks, both from the ENIAC project, showed up for work at Fuld Hall. Burks commuted from Swarthmore, Pennsylvania, catching the same train from the Thirtieth Street Station in Philadelphia as Goldstine, who, still on active duty, “had obtained an Army car which sat at the Princeton railroad station … and drove us out to the Institute and then we went home the same way.”36

  There was no room at the inn, either in the town of Princeton or in Fuld Hall. Those who had been away for the duration of the war had now returned, and in their absence all nonessential construction had come to a halt. The shortage of building materials remained as severe as it had been during the war, and new construction or even remodeling required authorization from the Civilian Production Administration. Adding to the overcrowding at the Institute, the entire staff of the Economic, Financial and Transit Department of the League of Nations, granted refuge by Aydelotte after the disbanding of their headquarters in Geneva, were crammed into all available space, including the board room, on the third and fourth floors of Fuld Hall. A staff of thirty-six individuals, from eight countries, remained encamped for almost five years, despite Veblen, among others, advocating “a firm refusal to let the other work of the Institute be further hampered by our hospitality to the league.”37

  World government, advocated by Albert Einstein and Edward Teller alike, was spilling out into the halls. “Until the nations of the world can combine into some kind of effective political organization, sacrificing some part of their national sovereignty and delegating to this supra-national organization the power to enforce peace and to settle international controversies by political and judicial processes, the world will continue to live in danger of war,” Aydelotte had warned in February of 1941.38 When the war ended, the debate over the next one had already begun. In adjacent offices two floors below those of the League, von Neumann was arguing for preventive war against the Soviet Union to be followed by a Pax Americana, while Albert Einstein was contributing his call to global disarmament, “One Way Out,” to the Federation of American Scientists’ manifesto One World or None.

  All Institute members except permanent faculty were either sharing offices or relegated to temporary desks in the library. Some were even sleeping in Fuld Hall. One room, however, remained unoccupied: Fuld 219. This was a small office reserved for the secretary to the occupant of Fuld 217. “It was agreed that the room connected with Dr. Gödel’s office might be used for people working on the computing machine,” the School of Mathematics reported on February 13, 1946. “Kurt Gödel didn’t have a secretary, didn’t want one, I assume,” says Arthur Burks. “So for that summer, when of course we didn’t yet have a building for the computer, Herman and I occupied the secretary’s office next to Gödel’s office. It had a blackboard on the wall.”39

  “We spent most of our time the first few months planning this new machine, working out the structure and the instructions, and we would consult periodically with von Neumann,” Burks recalls. “After we’d done a certain amount of planning, we decided we’d better write it up now. Which was fine with me. So Herman and I wrote the first draft and I don’t remember how we divided it but we both worked writing it. Then we’d show it to von Neumann and he would revise, or we’d discuss it, and so forth, and that was issued as a report at the end of June.”40

  “Preliminary Discussion of the Logical Design of an Electronic Computing Instrument” was issued on June 28, 1946. In fifty-four pages, opening with a discussion of the “principal components of the machine,” comprising “certain main organs relating to arithmetic, memory-storage, control and connection with the human operator,” and closing with a list of the order codes, the report specified the logical architecture, if not the physical embodiment, of the new machine. Because, as the authors put it, “the moment one chooses a given component as the elementary memory unit, one has also more or less determined upon much of the balance of the machine,” a full five pages are devoted to the memory architecture, envisioned as 40 Selectron tubes each storing 4,096 bits—reduced to 1,024 as engineering considerations began to set in.

  The report went on to describe—in enough detail to begin planning and coding of actual problems—a complete set of order codes. There were twenty-one instructions, supplemented by a number of input/output orders discussed at the end of the report. Finally, “there is one further order that the control needs to execute,” the authors concluded. “There should be some means by which the computer can signal to the operator when a computation has been concluded, or when the computation has reached a previously determined point. Hence an order is needed which will tell the computer to stop and to flash a light or ring a bell.”41

  Some 175 copies of the report were distributed and then, in May 1947, Goldstine reported that the stencils “are practically worn out and so it is probably not possible to make more copies using them.”42 A second edition, reset on the Institute’s new Varityper, was issued on September 2, 1947. Few technical documents have had as great an impact, in the long run. “Preliminary Discussion of the Logical Design of an Electronic Computing Instrument,” drafted in the annex to Gödel’s office, would end up fulfilling Leibniz’s dreams of digital computing and universal language that Gödel believed had been overlooked.

  Gottfried Wilhelm Leibniz, born in Leipzig in 1646, enrolled in the University of Leipzig as a law student at age fifteen. Our universe, Leibniz theorized, was selected from an infinity of possible universes, optimized so that a minimum of laws would lead to a maximum diversity of results. Leibniz’s reflections on the nature of mind culminated in his Monadology of 1714, a short text describing a universe of elementary mental particles that he cal
led monads, or “little minds.” These entelechies (the local actualization of a universal mind) reflected in their own inner state the state of the universe as a whole. According to Leibniz, relation gave rise to substance, not, as Newton had it, the other way around. “Back to Leibniz!” is how Norbert Wiener titled an article on quantum mechanics in 1932. “I can see no essential difference between the materialism which includes soul as a complicated type of material particle and a spiritualism which includes material particles as a primitive type of soul,” Wiener added in 1934.43

  Leibniz believed, following Hobbes and in advance of Hilbert, that a consistent system of logic, language, and mathematics could be formalized by means of an alphabet of unambiguous symbols manipulated according to mechanical rules. In 1675 he wrote to Henry Oldenburg, secretary of the Royal Society and his go-between with Isaac Newton, that “the time will come, and come soon, in which we shall have a knowledge of God and mind that is not less certain than that of figures and numbers, and in which the invention of machines will be no more difficult than the construction of problems in geometry.” Envisioning what we now term software, he saw that the correspondence between logic and mechanism worked both ways. To his “Studies in a Geometry of Situation,” sent to Christiaan Huygens in 1679, he appended the observation that “one could carry out the description of a machine, no matter how complicated, in characters which would be merely the letters of the alphabet, and so provide the mind with a method of knowing the machine and all its parts.”44

  With his logical calculus, or calculus ratiocinator, Leibniz took the first steps toward his vision of a “universal symbolistic in which all truths of reason would be reduced to a kind of calculus.” Believing that “a kind of alphabet of human thoughts can be worked out and that everything can be discovered and judged by a comparison of the letters of this alphabet and an analysis of the words made from them,” he proposed a universal coding in which primary concepts would be represented by prime numbers—an all-encompassing mapping between numbers and ideas.45

  “I think that a few selected men could finish the matter in five years,” Leibniz claimed. “It would take them only two, however, to work out, by an infallible calculus, the doctrines most useful for life, that is, those of morality and metaphysics.” Anticipating Gödel and Turing, Leibniz promised that through digital computing “the human race will have a new kind of instrument which will increase the power of the mind much more than optical lenses strengthen the eyes.… Reason will be right beyond all doubt only when it is everywhere as clear and certain as only arithmetic has been until now.”46

  Leibniz saw binary coding as the key to a universal language and credited its invention to the Chinese, seeing in the hexagrams of the I Ching the remnants of “a Binary Arithmetic … which I have rediscovered some thousands of years later.” Leibniz’s notes show the development of simple algorithms for translating between decimal and binary notation and for performing the basic functions of arithmetic as mechanically iterated operations on strings of zeros and ones. “In Binary Arithmetic there are only two signs, 0 and 1, with which we can write all numbers,” he explained. “I have since found that it further expresses the logic of dichotomies which is of the greatest use.”47

  In 1679, Leibniz imagined a digital computer in which binary numbers were represented by spherical tokens, governed by gates under mechanical control. “This [binary] calculus could be implemented by a machine (without wheels),” he wrote, “in the following manner, easily to be sure and without effort. A container shall be provided with holes in such a way that they can be opened and closed. They are to be open at those places that correspond to a 1 and remain closed at those that correspond to a 0. Through the opened gates small cubes or marbles are to fall into tracks, through the others nothing. It [the gate array] is to be shifted from column to column as required.”48

  Leibniz had invented the shift register—270 years ahead of its time. In the shift registers at the heart of the Institute for Advanced Study computer (and all processors and microprocessors since), voltage gradients and pulses of electrons have taken the place of gravity and marbles, but otherwise they operate as Leibniz envisioned in 1679. With nothing more than binary tokens, and the ability to shift right and left, it is possible to perform all the functions of arithmetic. But to do anything with that arithmetic, you have to be able to store and recall the results.

  “There are two possible means for storing a particular word in the Selectron memory,” Burks, Goldstine, and von Neumann explained. “One method is to store the entire word in a given tube and … the other method is to store in corresponding places in each of the 40 tubes one digit of the word.” This was the origin of the metaphor of handing out similar room numbers to 40 people staying in a 40-floor hotel. “To get a word from the memory in this scheme requires, then, one switching mechanism to which all 40 tubes are connected in parallel,” their “Preliminary Discussion” continues. “Such a switching scheme seems to us to be simpler than the technique needed in the serial system and is, of course, 40 times faster. The essential difference between these two systems lies in the method of performing an addition; in a parallel machine all corresponding pairs of digits are added simultaneously, whereas in a serial one these pairs are added serially in time.”49

  The 40 Selectron tubes constituted a 32-by-32-by-40-bit matrix containing 1,024 40-bit strings of code, with each string assigned a unique identity number, or numerical address, in a manner reminiscent of how Gödel had assigned what are now called Gödel numbers to logical statements in 1931. By manipulating the 10-bit addresses, it was possible to manipulate the underlying 40-bit strings—containing any desired combination of data, instructions, or additional addresses, all modifiable by the progress of the program being executed at the time. “This ability of the machine to modify its own orders is one of the things which makes coding the non-trivial operation which we have to view it as,” von Neumann explained to his navy sponsors in May of 1946.50

  “The kind of thinking that Gödel was doing, things like Gödel numbering systems—ways of getting access to codified information and such—enables you to keep track of the parcels of information as they are formed, and … you can then deduce certain important consequences,” says Bigelow. “I think those ideas were very well known to von Neumann [who] spent a fair amount of his time trying to do mathematical logic, and he worked on the same problem that Gödel solved.”51

  The logical architecture of the IAS computer, foreshadowed by Gödel, was formulated in Fuld 219. “In the 1930s the realization of an actual physical device that could function as a general-purpose information-processing programmable computer was still decades in the future, yet someone knowledgeable about modern programming languages today looking at Gödel’s paper on undecidability written that year will see a sequence of forty-five numbered formulas that looks very much like a computer program,” says Martin Davis, who arrived at the Institute under the sponsorship of the Office of Naval Research in September of 1952. “In demonstrating that the property of being the code of a proof in PM [Principia Mathematica] is expressible inside PM, Gödel had to deal with many of the same issues that those designing programming languages and those writing programs in those languages would be facing,” Davis notes.52

  Gödel had demonstrated, in 1931, the powers of numerical addressing and self-reference. In a stored-program computer, one of the rules is that you can change the rules. Gödel was well aware that Turing’s Universal Machine and von Neumann’s implementation of it were demonstrations, if not the direct offspring, of his, Gödel’s, ideas. “What von Neumann perhaps had in mind appears more clearly from the universal Turing machine,” he later explained to Arthur Burks. “There it might be said that the complete description of its behavior is infinite because, in view of the non existence of a decision procedure predicting its behavior, the complete description could be given only by an enumeration of all instances. The universal Turing machine, where the ratio of the two complexiti
es is infinity, might then be considered to be a limiting case.”53

  Leibniz’s belief in a universal digital coding embodied his principle of maximum diversity: infinite complexity from finite rules. “Nothing is a better analogy to, or even demonstration of such creation than the origin of numbers as here represented, using only unity and zero or nothing,” he wrote to the Duke of Brunswick in 1697, urging that a silver medallion be struck (with a portrait of the duke on the reverse) to help bring the powers of binary arithmetic, and “the creation of all things out of nothing through God’s omnipotence,” to the attention of the world.54

  Where does meaning come in? If everything is assigned a number, does this diminish the meaning in the world? What Gödel (and Turing) proved is that formal systems will, sooner or later, produce meaningful statements whose truth can be proved only outside the system itself. This limitation does not confine us to a world with any less meaning. It proves, on the contrary, that we live in a world where higher meaning exists.

  “Our earthly existence, since it in itself has a very doubtful meaning, can only be a means toward the goal of another existence,” Gödel wrote to his mother in 1961. “The idea that everything in the world has meaning is, after all, precisely analogous to the principle that everything has a cause, on which the whole of science rests.”55

  SEVEN

  6J6

  Absence of a signal should never be used as a signal.

  —Julian Bigelow, 1947

  JULIAN HIMELY BIGELOW, the fourth of five siblings, was born in Nutley, New Jersey—forty-two miles from Princeton—on March 19, 1913. At the age of three, while staying with an aunt, “he found a screw driver, and removed all the door knobs and put them in a big pile, and it took him a really long time to put all these door knobs back.”1 His father, Richard Bigelow, gave up a teaching career at Wellesley to raise his family—and outwait the Depression—by retreating to Millis, Massachusetts, in search of a self-sufficient rural life.

 

‹ Prev