The Theory That Would Not Die

by Sharon Bertsch McGrayne

  Shortly after Germany attacked Russia, British radio listening posts intercepted a new kind of German army message. Analysts at Bletchley Park thought it came from a teletype machine. They were right. The Germans were encrypting and decrypting at the speed of typing. The new Lorenz machines and their family of ultrasecret codes were technically far more sophisticated than the Enigmas, which had been built for commercial use in the 1920s. The supreme command in Berlin relied on its new codes to communicate the highest level of strategy to army group commanders across Europe. The messages were so important that Hitler himself signed some of them.

  Code-naming the new Lorenz machines Tunny for “tuna fish,” a group of Britain’s leading mathematicians began a year of desperate struggle. They used Bayes’ rule, logic, statistics, Boolean algebra, and electronics. They also began work on designing and building the first of ten Colossi, the world’s first large-scale digital electronic computers.

  When Good and others started work on the Tunny-Lorenz codes, they incorporated Turing’s Bayesian scoring system and his fundamental units of bans, decibans, and centibans. They employed Bayes’ theorem and a spectrum of priors: honest priors and improper ones; priors that represented what was known and sometimes not; and in different places both Thomas Bayes’ uniform priors and Laplace’s unequal ones. To deduce the pattern of cams surrounding the wheels of the Tunny-Lorenz machines Turing invented a highly Bayesian method known as Turingery or Turingismus in July 1942. Turingery was a paper-and-pencil method, “more artistic than mathematical. . . . [You had to rely on what] you felt in your bones,” according to Turingery player William T. Tutte.29 The first step was to make a guess and assume, as Bayes had suggested, that it had a 50% chance of being correct. Add more and more clues, some good, some bad, and “with patience, luck, a lot of rubbing out, and a lot of cycling back and forth,” the plain text appeared. When the odds of being correct reached 50 to 1, a pair of wheel settings was declared certain.30

  As Bletchley Park analysts worked on Tunny’s wheel patterns and Russia resisted the German onslaught, Japan attacked the United States at Pearl Harbor on December 7, 1941. Supplying Great Britain immediately became more difficult. When American ships that had protected the convoys supplying Britain were quickly transferred to the Pacific, 15 German U-boats took their places in the shipping lanes off the American East Coast. As convoys of Argentine beef and Caribbean oil hugged the coast, they were silhouetted at night against shore lights that local communities dependent on tourism refused to dim. Miami’s neon signs, for example, stretched for six deadly miles. The U-boats, lying in wait at periscope depth, caused three months of devastation until the U.S. military ordered coastal lights turned off at dusk.

  Making matters worse, the Atlantic U-boats added a fourth wheel to their Enigmas, and the Turing-Welchman bombes were stymied. For most of 1942 Turing and his coworkers could not read any message to or from German submarines. Bletchley Park called it the Great Blackout. For four months the U-boats ran riot in the Atlantic at large, sinking 43 ships in August and September alone. The average U.S. vessel crossed the Atlantic and back three times before it was sunk on its fourth trip.

  Finally, in December 1942, three young British crewmen, Lt. Anthony Fasson, Able-Seaman Colin Grazier, and Tommy Brown, swam from their ship to a sinking German submarine off Egypt to pinch its vital codebook of encrypting tables. Fasson and Grazier drowned in the attempt, but Brown, a 16-year-old canteen assistant, survived to rescue the tables. At last Banburismus was fully operational. Within hours of Bletchley Park’s receiving the tables, U-boat messages from the Atlantic were being decrypted and convoys rerouted.

  The month before that happened, however, would be the war’s most dangerous month for Allied shipping, and during it Turing sailed for the United States on the Queen Elizabeth, a fast ship that traveled without convoy. Clearance from the White House made Turing a liaison between Bletchley Park and the U.S. Navy. The British had been teaching the Americans about Enigma in general before Pearl Harbor. Now Turing was to tell U.S. officials everything that had been learned, and the United States would accelerate the production of bombes. Surprisingly, the British planned his trip rather haphazardly. He arrived with inadequate identification, and U.S. immigration authorities almost confined him to Ellis Island. In addition, he had not been told whether he could discuss Tunny code breaking with Americans, and the Americans did not realize he expected to have full access to their voice-scrambling research. Nevertheless, during his stay he held high-level meetings in Dayton, Ohio, Washington, and New York City.

  Turing spent at least one afternoon in Dayton, where the National Cash Register Company planned to manufacture 336 bombes. He was dismayed to discover that the U.S. Navy was ignoring Banburismus and its ability to economize on bombe usage. The Americans seemed uninterested in the Enigma outside of their obligation to supply bombes for it.

  In Washington, Turing discussed Bletchley Park’s methods and bombes with U.S. Navy cryptographers. According to a previous agreement, the United States was concentrating on Japanese navy codes and ciphers while the British worked on Enigma. Bletchley Park had already sent a detailed technical report of its work to the Americans, but a civilian navy cryptographer, Agnes Meyer Driscoll, had sat on it; she had broken many Japanese codes and ciphers before the war and had her own, mistaken notions about how to solve Germany’s naval Enigma. Turing’s mathematics may also have been too technical for the Americans. At first he was alarmed that no one seemed to be working mathematically “with pencil and paper,” and he tried in vain to explain the general principle that confirming inferences suggested by a hypothesis would make the hypothesis itself more probable.31 Later, he was relieved to meet American mathematicians involved in cryptography.

  From Washington, Turing went to the Bell Laboratory in New York City, where he and Claude Shannon met regularly at afternoon tea. Shannon, like Turing and Kolmogorov, was a great mathematician and an original thinker, and he was using Bayes’ rule for wartime projects. But Turing and Shannon had more than Bayes in common. Both were shy, unconventional men with deep interests in cryptography and machines that could think. As young men, both had written seminal works combining machines and mathematics. In his master’s thesis in mathematics, written at the University of Michigan, Shannon showed that Molina’s relay circuits could be analyzed using Boolean algebra. Both Turing and Shannon liked cycling. Turing rode a bicycle for transportation and exercise; Shannon avoided social chitchat by riding a unicycle through Bell Labs’ hallways, sometimes juggling balls along the way. Both men liked to design equipment, in Shannon’s case whimsical machines like a robotic mouse to solve mazes or a computer for Roman numerals. His garage was filled with chess-playing machines. Unlike Turing, though, Shannon had a warm family life. His father was a businessman, his mother a high school principal, and his sister a mathematics professor, and he and his wife had three children.

  When Turing visited Bell Labs, the next cryptographic frontier was speech. Britain and the United States wanted their best people, Shannon and Turing, working on it. Shannon was already developing the SigSaly voice scrambler; it had a nonsense nursery-rhyme name but by war’s end Franklin D. Roosevelt, Churchill, and their top generals in eight locations around the world could talk together in total secrecy. With naval Enigma reduced to a largely administrative problem, Turing would tackle voice communications when he returned to Britain. When Turing and Shannon met for tea, they probably discussed the SigSaly.

  Shannon was also working on a theory of communication and information and its application to cryptography. In a brilliant insight Shannon realized that noisy telephone lines and coded messages could be analyzed by the same mathematics. One problem complemented the other; the purpose of information is to reduce uncertainty while the purpose of encryption is to increase it. Shannon was using Bayesian approaches for both. He said, “Bell Labs were working on secrecy systems. I’d work on communications systems and I was appointed to some of the com
mittees studying cryptanalytic techniques. The work on both the mathematical theory of communications and the cryptography went forward concurrently from about 1941. I worked on both of them together and I had some of the ideas while working on the other. I wouldn’t say that one came before the other—they were so close together you couldn’t separate them.”32

  Shannon’s efforts united telegraph, telephone, radio, and television communication into one mathematical theory of information. Roughly speaking, if the posterior in a Bayesian equation is quite different from the prior, something has been learned; but when a posterior is basically the same as the prior guess, the information content is low.

  Communication and cryptography were in this sense the reverse of one another. Shannon called his logarithmic units for measuring information binary dibits, or bits, a word suggested by John W. Tukey of Bell Labs and Princeton University. In a confidential report published in 1949 Shannon used Bayes’ theorem and Kolmogorov’s theory of probability from 1933 to show that, in a perfectly secret system, nothing is learned because the prior and posterior of Bayes’ theorem are equal. Bell Labs communications theorists were still developing extensions of Shannon’s theory and using Bayesian techniques extensively in 2007.

  Returning home, Turing boarded the Empress of Scotland in New York City on March 23, 1943. New York was the world’s greatest port during the war: more than 50 vessels streamed in and out of the city’s harbors each day. Turing was traveling during what would be the second most dangerous month of the war for Allied shipping. The U-boat offensive reached its peak that month and would sink 108 Allied ships while losing only 14 subs. Germany had broken the convoys’ routing cipher, and the U-boats’ four-wheel Enigmas still had Bletchley Park’s cryptographers stymied. Approximately 1,350 mostly unarmed merchant ships were at sea every day that spring. They joined a long coastal shipping line that stretched from Brazil to the mouth of the St. Lawrence River, where they formed convoys to cross the Atlantic. Allied escort vessels concentrated on protecting convoys carrying troops to Britain for an invasion of Europe, however, so Turing’s ship was one of 120 fast-moving ships that traveled unescorted. Speed was no guarantee of safety, though; the week before, U-boats had sunk the Empress of Scotland’s sister ship. Despite the Enigma blackout, Turing made it back to England without incident.

  Clearly, the Allies had to locate and destroy the U-boats, not just evade them. U-boats were tying up thousands of Allied ships, planes, and troops needed to supply Britain and invade Continental Europe. The hunt for U-boats involved Bayes’ rule in still another part of the Battle of the Atlantic.

  Applying scientific techniques to the antisubmarine campaign, the British Air Ministry organized a small group of scientists to improve its operational efficiency. This was a new idea, and the British called it O.R., for operational or operations research. Its statistics were fairly elementary but imbued with Bayesian ideas.

  O.R. concentrated on boosting the efficiency of torpedo attacks, airplane navigation, and formation flying by squadrons of planes searching for U-boats. Bayes’ “a priori Method” played “quite a large role in operational research,” especially when comparatively few variables were involved, reported O.R.’s chief, the future developmental biologist Conrad H. Waddington.33

  Typically, O.R. employed Bayes for small, detailed parts of big problems, such as the number of aircraft needed to protect a convoy, the length of crews’ operational tours, and whether an aircraft patrol should deviate from its regular flight pattern. Observing the success of British O.R., Adm. Ernest King, commander in chief of the U.S. Fleet, assigned 40 civilian physicists, chemists, mathematicians, and actuaries to his staff. This Anti-Submarine Warfare Operations Research Group was headed by physicist Philip M. Morse of MIT and chemist George E. Kimball of Columbia University.

  The Allies had built a string of high-frequency direction-finding stations along the perimeter of the Atlantic. Much of the system was devoted to capturing encoded radio messages and relaying them to code breakers in the United States and at Bletchley Park. With six or seven listening posts intercepting the same message from a particular U-boat, the position of a submarine in the Atlantic could be determined within about 10,000 square miles. This gave patrol planes a good idea of where to look, but 10,000 square miles still meant a circle some 236 miles across. The Allies needed an efficient method for narrowing the search.

  Since almost every aspect of searching for targets in the open seas involves uncertainties and probabilities, mathematician Bernard Osgood Koopman of Columbia University was assigned the job of finding a workable method. After graduating from Harvard in 1922, Koopman had studied probability in Paris and earned a Ph.D. from Columbia. His dream was to bridge the gap between Bayes’ “intuitive probability . . . of a subjective nature” and the “purely objective” frequency-based probability used in quantum physics and statistical mechanics.34

  A crusty man with a rough frankness and a pungent wit, Koopman saw no reason to be bashful about Bayes or Bayesian priors. He assumed from the very beginning that he was dealing with probabilities: “Every operation involved in search is beset with uncertainties; it can be understood quantitatively only in terms of . . . probability. This may now be regarded as a truism; but it seems to have taken the developments in operational research of the Second World War to drive home its practical implications.”35

  Searching for a U-boat at sea, Koopman first asked what its heading was likely to be. To him, this was a classic Bayesian “probability of causes” problem. Priors would obviously be needed. “No rational prospector would search a region for mineral deposits unless a geological study, or the experience of previous prospectors, showed a sufficiently high probability of their presence,” he commented. “Police will patrol localities of high incidence of crime. Public health officials will have ideas in advance of the likely sources of infection and will examine them first.”36

  Koopman started right off by assigning Thomas Bayes’ 50–50 odds to the presence of a target U-boat inside the 236-mile circle. Then he added data that were as objective as possible, as Jeffreys advised. Unlike Turing, Koopman had access to enormous amounts of detailed information that the military had accumulated about U-boat warfare.

  Unfortunately, a U-boat could spot a destroyer long before the destroyer’s sonar picked up the U-boat. Many U.S. planes were not equipped with windshield wipers, and crews peered through scratched and soiled windows. “The need for keeping the windows clean and clear cannot be overemphasized,” Koopman admonished. If a crew was lucky enough to get binoculars, they were standard navy 7 x 50 issue, hazy at best. Unless crew members changed stations frequently to minimize the monotony, they lost focus. And the best angle for watching was generally 3 or 4 degrees below the horizon—“a rough and ready rule for finding this locus,” Koopman wrote, “is to extend the fist at arm’s length and look about two or three fingers below the horizon.”37 He figured that most aircraft crews were only a quarter as efficient as lookouts working under laboratory conditions.

  As a practical problem, Koopman asked how a naval officer could find a U-boat within a 118-mile radius if he had 4 planes, each of which could fly 5 hours at 130 knots up and down 5 search lanes, each 5 miles wide. Although few O.R. investigations required such intricate mathematics, Koopman found a way to answer the question mathematically using logarithmic functions. Knowing only that 3 of the 5 lanes had a 10% probability of success, another had 30%, and a fourth had 40%, Koopman could do the Bayesian math. The officer should assign two planes each to the 40% lane and the 30% lane and none to the least probable areas. He calculated this by hand; his problem was not calculating but getting appropriate observational data. He later said that computers would have been irrelevant.

  Applying his theories, Koopman wrote a fat manual of precomputed recipes for conducting a U-boat search. The effort needed for each subsection of the search area equaled the logarithm of the probability at that point. The regions to be searched did not have
to be boxes or circles; they could have squiggly, irregular shapes. But using his formulas, he could tell a commander how many hours of search to devote to each squiggly region.

  Using Koopman’s cookbook, a shipboard officer could lay out the optimal way to search given his limited resources: the expected time needed to find the target; the boundaries beyond which he should not venture; and what he should do every two hours until either the U-boat was found or the search was called off. He could plan an eight-hour day, starting off with an optimum search for the first four hours; then, if a U-boat had not been found, the commander could use Bayes’ rule to update the target’s probable location and launch a new plan every two hours to maximize his chance of locating it.

  All of the commander’s planning for two-hour sequential searches could be done ahead of time in his stateroom. Koopman called it a “continuous distribution of effort.” His U-boat sea searches were theoretically similar to Kolmogorov’s artillery problem. Koopman was searching for an unknown U-boat and needed to spread the search effort over an area in an optimal way, just as Kolmogorov figured the optimal amount of dispersion in order to destroy a German cannon. Minesweepers, who worked with similar problems, adopted Koopman’s techniques.

  Three crucial turning points—two of them top secret—occurred in the European war during 1943. First, in what the Russians still call the Great Patriotic War, the Soviets defeated the Germans on the Eastern Front, at a cost of more than 27 million lives. Second, the tide began to turn against the Germans’ U-boats; they sank a quarter million tons in May but 41 subs were lost. Third, Bletchley Park became a giant factory employing almost 9,000 people. As more bombes came online, the laborious Banburismus cardboards were phased out. Barring unforeseen changes by German cryptographers, decoding naval Enigma was under control.

  Back home safely and free of responsibility for the Enigma and Tunny-Lorenz codes, Turing, the great theoretician, was free to dream. During long walks in the countryside around Bletchley Park, Turing and Good discussed machines that could think with Donald Michie, who would pioneer artificial intelligence. Michie, who had joined Bletchley Park as an 18-year-old, described the trio as “an intellectual cabal with a shared obsession with thinking machines and particularly with machine learning as the only credible road to achieving such machines.” They talked about “various approaches, conjectures, and arguments concerning what today we call AI.”38