He accomplished this with iron rigor disguised as sleight of hand. He employed the formal rules of PM and, as he employed them, also approached them metamathematically—viewed them, that is, from the outside. As he explained, all the symbols of PM—numbers, operations of arithmetic, logical connectors, and punctuation—constituted a limited alphabet. Every statement or formula of PM was written in this alphabet. Likewise every proof comprised a finite sequence of formulas—just a longer passage written in the same alphabet. This is where metamathematics came in. Metamathematically, Gödel pointed out, one sign is as good as another; the choice of a particular alphabet is arbitrary. One could use the traditional assortment of numerals and glyphs (from arithmetic: +, −, =, ×; from logic: ¬, ∨, ⊃, ∃), or one could use letters, or one could use dots and dashes. It was a matter of encoding, slipping from one symbol set to another.
Gödel proposed to use numbers for all his signs. Numbers were his alphabet. And because numbers can be combined using arithmetic, any sequence of numbers amounts to one (possibly very large) number. So every statement, every formula of PM can be expressed as a single number, and so can every proof. Gödel outlined a rigorous scheme for doing the encoding—an algorithm, mechanical, just rules to follow, no intelligence necessary. It works forward and backward: given any formula, following the rules generates one number, and given any number, following the rules produces the corresponding formula.
Not every number translates into a correct formula, however. Some numbers decode back into gibberish, or formulas that are false within the rules of the system. The string of symbols “0 0 0 = = =” does not make a formula at all, though it translates to some number. The statement “0 = 1” is a recognizable formula, but it is false. The formula “0 + x = x + 0” is true, and it is provable.
This last quality—the property of being provable according to PM—was not meant to be expressible in the language of PM. It seems to be a statement from outside the system, a metamathematical statement. But Gödel’s encoding reeled it in. In the framework he constructed, the natural numbers led a double life, as numbers and also as statements. A statement could assert that a given number is even, or prime, or a perfect square, and a statement could also assert that a given number is a provable formula. Given the number 1,044,045,317,700, for example, one could make various statements and test their truth or falsity: this number is even, it is not a prime, it is not a perfect square, it is greater than 5, it is divisible by 121, and (when decoded according to the official rules) it is a provable formula.
Gödel laid all this out in a little paper in 1931. Making his proof watertight required complex logic, but the basic argument was simple and elegant. Gödel showed how to construct a formula that said A certain number, x, is not provable. That was easy: there were infinitely many such formulas. He then demonstrated that, in at least some cases, the number x would happen to represent that very formula. This was just the looping self-reference that Russell had tried to forbid in the rules of PM—
This statement is not provable
—and now Gödel showed that such statements must exist anyway. The Liar returned, and it could not be locked out by changing the rules. As Gödel explained (in one of history’s most pregnant footnotes),
Contrary to appearances, such a proposition involves no faulty circularity, for it only asserts that a certain well-defined formula … is unprovable. Only subsequently (and so to speak by chance) does it turn out that this formula is precisely the one by which the proposition itself was expressed.♦
Within PM, and within any consistent logical system capable of elementary arithmetic, there must always be such accursed statements, true but unprovable. Thus Gödel showed that a consistent formal system must be incomplete; no complete and consistent system can exist.
The paradoxes were back, nor were they mere quirks. Now they struck at the core of the enterprise. It was, as Gödel said afterward, an “amazing fact”—“that our logical intuitions (i.e., intuitions concerning such notions as: truth, concept, being, class, etc.) are self-contradictory.”♦ It was, as Douglas Hofstadter says, “a sudden thunderbolt from the bluest of skies,”♦ its power arising not from the edifice it struck down but the lesson it contained about numbers, about symbolism, about encoding:
Gödel’s conclusion sprang not from a weakness in PM but from a strength. That strength is the fact that numbers are so flexible or “chameleonic” that their patterns can mimic patterns of reasoning.… PM’s expressive power is what gives rise to its incompleteness.
The long-sought universal language, the characteristica universalis Leibniz had pretended to invent, had been there all along, in the numbers. Numbers could encode all of reasoning. They could represent any form of knowledge.
Gödel’s first public mention of his discovery, on the third and last day of a philosophical conference in Königsberg in 1930, drew no response; only one person seems to have heard him at all, a Hungarian named Neumann János. This young mathematician was in the process of moving to the United States, where he would soon and for the rest of his life be called John von Neumann. He understood Gödel’s import at once; it stunned him, but he studied it and was persuaded. No sooner did Gödel’s paper appear than von Neumann was presenting it to the mathematics colloquium at Princeton. Incompleteness was real. It meant that mathematics could never be proved free of self-contradiction. And “the important point,” von Neumann said, “is that this is not a philosophical principle or a plausible intellectual attitude, but the result of a rigorous mathematical proof of an extremely sophisticated kind.”♦ Either you believed in mathematics or you did not.
Bertrand Russell (who, of course, did) had moved on to more gentle sorts of philosophy. Much later, as an old man, he admitted that Gödel had troubled him: “It made me glad that I was no longer working at mathematical logic. If a given set of axioms leads to a contradiction, it is clear that at least one of the axioms must be false.”♦ On the other hand, Vienna’s most famous philosopher, Ludwig Wittgenstein (who, fundamentally, did not), dismissed the incompleteness theorem as trickery (“Kunststücken”) and boasted that rather than try to refute it, he would simply pass it by:
Mathematics cannot be incomplete; any more than a sense can be incomplete. Whatever I can understand, I must completely understand.♦
Gödel’s retort took care of them both. “Russell evidently misinterprets my result; however, he does so in a very interesting manner,” he wrote. “In contradistinction Wittgenstein … advances a completely trivial and uninteresting misinterpretation.”♦
In 1933 the newly formed Institute for Advanced Study, with John von Neumann and Albert Einstein among its first faculty members, invited Gödel to Princeton for the year. He crossed the Atlantic several more times that decade, as fascism rose and the brief glory of Vienna began to fade. Gödel, ignorant of politics and naïve about history, suffered depressive breakdowns and bouts of hypochondria that forced him into sanatoria. Princeton beckoned but Gödel vacillated. He stayed in Vienna in 1938, through the Anschluss, as the Vienna Circle ceased to be, its members murdered or exiled, and even in 1939, when Hitler’s army occupied his native Czechoslovakia. He was not a Jew, but mathematics was verjudet enough. He finally managed to leave in January 1940 by way of the Trans-Siberian Railway, Japan, and a ship to San Francisco. His name was recoded by the telephone company as “K. Goedel” when he arrived in Princeton, this time to stay.♦
Claude Shannon had also arrived at the Institute for Advanced Study, to spend a postdoctoral year. He found it a lonely place, occupying a new red-brick building with clocktower and cupola framed by elms on a former farm a mile from Princeton University. The first of its fifteen or so professors was Einstein, whose office was at the back of the first floor; Shannon seldom laid eyes on him. Gödel, who had arrived in March, hardly spoke to anyone but Einstein. Shannon’s nominal supervisor was Hermann Weyl, another German exile, the most formidable mathematical theorist of the new quantum mechanics. Weyl was
only mildly interested in Shannon’s thesis on genetics—“your bio-mathematical problems”♦—but thought Shannon might find common ground with the institute’s other great young mathematician, von Neumann. Mostly Shannon stayed moodily in his room in Palmer Square. His twenty-year-old wife, having left Radcliffe to be with him, found it increasingly grim, staying home while Claude played clarinet accompaniment to his Bix Beiderbecke record on the phonograph. Norma thought he was depressed and wanted him to see a psychiatrist. Meeting Einstein was nice, but the thrill wore off. Their marriage was over; she was gone by the end of the year.
Nor could Shannon stay in Princeton. He wanted to pursue the transmission of intelligence, a notion poorly defined and yet more pragmatic than the heady theoretical physics that dominated the institute’s agenda. Furthermore, war approached. Research agendas were changing everywhere. Vannevar Bush was now heading the National Defense Research Committee, which assigned Shannon “Project 7”:♦ the mathematics of fire-control mechanisms for antiaircraft guns—“the job,” as the NDRC reported dryly, “of applying corrections to the gun control so that the shell and the target will arrive at the same position at the same time.”♦ Airplanes had suddenly rendered obsolete almost all the mathematics used in ballistics: for the first time, the targets were moving at speeds not much less than the missiles themselves. The problem was complex and critical, on ships and on land. London was organizing batteries of heavy guns firing 3.7-inch shells. Aiming projectiles at fast-moving aircraft needed either intuition and luck or a vast amount of implicit computation by gears and linkages and servos. Shannon analyzed physical problems as well as computational problems: the machinery had to track rapid paths in three dimensions, with shafts and gears controlled by rate finders and integrators. An antiaircraft gun in itself behaved as a dynamical system, subject to “backlash” and oscillations that might or might not be predictable. (Where the differential equations were nonlinear, Shannon made little headway and knew it.)
He had spent two of his summers working for Bell Telephone Laboratories in New York; its mathematics department was also taking on the fire-control project and asked Shannon to join. This was work for which the Differential Analyzer had prepared him well. An automated antiaircraft gun was already an analog computer: it had to convert what were, in effect, second-order differential equations into mechanical motion; it had to accept input from rangefinder sightings or new, experimental radar; and it had to smooth and filter this data, to compensate for errors.
At Bell Labs, the last part of this problem looked familiar. It resembled an issue that plagued communication by telephone. The noisy data looked like static on the line. “There is an obvious analogy,” Shannon and his colleagues reported, “between the problem of smoothing the data to eliminate or reduce the effect of tracking errors and the problem of separating a signal from interfering noise in communications systems.”♦ The data constituted a signal; the whole problem was “a special case of the transmission, manipulation, and utilization of intelligence.” Their specialty, at Bell Labs.
Transformative as the telegraph had been, miraculous as the wireless radio now seemed, electrical communication now meant the telephone. The “electrical speaking telephone” first appeared in the United States with the establishment of a few experimental circuits in the 1870s. By the turn of the century, the telephone industry surpassed the telegraph by every measure—number of messages, miles of wire, capital invested—and telephone usage was doubling every few years. There was no mystery about why: anyone could use a telephone. The only skills required were talking and listening: no writing, no codes, no keypads. Everyone responded to the sound of the human voice; it conveyed not just words but feeling.
The advantages were obvious—but not to everyone. Elisha Gray, a telegraph man who came close to trumping Alexander Graham Bell as inventor of the telephone, told his own patent lawyer in 1875 that the work was hardly worthwhile: “Bell seems to be spending all his energies in [the] talking telegraph. While this is very interesting scientifically it has no commercial value at present, for they can do much more business over a line by methods already in use.”♦ Three years later, when Theodore N. Vail quit the Post Office Department to become the first general manager (and only salaried officer) of the new Bell Telephone Company, the assistant postmaster general wrote angrily, “I can scarce believe that a man of your sound judgment … should throw it up for a d——d old Yankee notion (a piece of wire with two Texan steer horns attached to the ends, with an arrangement to make the concern blate like a calf) called a telephone!”♦ The next year, in England, the chief engineer of the General Post Office, William Preece, reported to Parliament: “I fancy the descriptions we get of its use in America are a little exaggerated, though there are conditions in America which necessitate the use of such instruments more than here. Here we have a superabundance of messengers, errand boys and things of that kind.… I have one in my office, but more for show. If I want to send a message—I use a sounder or employ a boy to take it.”♦
One reason for these misguesses was just the usual failure of imagination in the face of a radically new technology. The telegraph lay in plain view, but its lessons did not extrapolate well to this new device. The telegraph demanded literacy; the telephone embraced orality. A message sent by telegraph had first to be written, encoded, and tapped out by a trained intermediary. To employ the telephone, one just talked. A child could use it. For that very reason it seemed like a toy. In fact, it seemed like a familiar toy, made from tin cylinders and string. The telephone left no permanent record. The Telephone had no future as a newspaper name. Business people thought it unserious. Where the telegraph dealt in facts and numbers, the telephone appealed to emotions.
The new Bell company had little trouble turning this into a selling point. Its promoters liked to quote Pliny, “The living voice is that which sways the soul,” and Thomas Middleton, “How sweetly sounds the voice of a good woman.” On the other hand, there was anxiety about the notion of capturing and reifying voices—the phonograph, too, had just arrived. As one commentator said, “No matter to what extent a man may close his doors and windows, and hermetically seal his key-holes and furnace-registers with towels and blankets, whatever he may say, either to himself or a companion, will be overheard.”♦ Voices, hitherto, had remained mostly private.
The new contraption had to be explained, and generally this began by comparison to telegraphy. There were a transmitter and receiver, and wires connected them, and something was carried along the wire in the form of electricity. In the case of the telephone, that thing was sound, simply converted from waves of pressure in the air to waves of electric current. One advantage was apparent: the telephone would surely be useful to musicians. Bell himself, traveling around the country as impresario for the new technology, encouraged this way of thinking, giving demonstrations in concert halls, where full orchestras and choruses played “America” and “Auld Lang Syne” into his gadgetry. He encouraged people to think of the telephone as a broadcasting device, to send music and sermons across long distances, bringing the concert hall and the church into the living room. Newspapers and commentators mostly went along. That is what comes of analyzing a technology in the abstract. As soon as people laid their hands on telephones, they worked out what to do. They talked.
In a lecture at Cambridge, the physicist James Clerk Maxwell offered a scientific description of the telephone conversation: “The speaker talks to the transmitter at one end of the line, and at the other end of the line the listener puts his ear to the receiver, and hears what the speaker said. The process in its two extreme states is so exactly similar to the old-fashioned method of speaking and hearing that no preparatory practice is required on the part of either operator.”♦ He, too, had noticed its ease of use.
So by 1880, four years after Bell conveyed the words “Mr. Watson, come here, I want to see you,” and three years after the first pair of telephones rented for twenty dollars, more than sixty thousand
telephones were in use in the United States. The first customers bought pairs of telephones for communication point to point: between a factory and its business office, for example. Queen Victoria installed one at Windsor Castle and one at Buckingham Palace (fabricated in ivory; a gift from the savvy Bell). The topology changed when the number of sets reachable by other sets passed a critical threshold, and that happened surprisingly soon. Then community networks arose, their multiple connections managed through a new apparatus called a switch-board.
The initial phase of ignorance and skepticism passed in an eyeblink. The second phase of amusement and entertainment did not last much longer. Businesses quickly forgot their qualms about the device’s seriousness. Anyone could be a telephone prophet now—some of the same predictions had already been heard in regard to the telegraph—but the most prescient comments came from those who focused on the exponential power of interconnection. Scientific American assessed “The Future of the Telephone” as early as 1880 and emphasized the forming of “little clusters of telephonic communicants.” The larger the network and the more diverse its interests, the greater its potential would be.
What the telegraph accomplished in years the telephone has done in months. One year it was a scientific toy, with infinite possibilities of practical use; the next it was the basis of a system of communication the most rapidly expanding, intricate, and convenient that the world has known.… Soon it will be the rule and not the exception for business houses, indeed for the dwellings of well-to-do people as well, to be interlocked by means of telephone exchange, not merely in our cities, but in all outlying regions. The result can be nothing less than a new organization of society—a state of things in which every individual, however secluded, will have at call every other individual in the community, to the saving of no end of social and business complications, of needless goings to and fro, of disappointments, delays, and a countless host of those great and little evils and annoyances.