Turing had still another attitude. The fact that no one else wanted to work on the naval codes made them doubly attractive. A close friend called Turing “a confirmed solitary.”8 Isolation appealed to him. Announcing that “no one else was doing anything about it and I could have it to myself,” Turing decided to attack the German naval code.9 He began working on naval Enigma with a staff of two “girls” and an Oxford mathematician-physicist, Peter Twinn.10 Turing thought the code “could be broken because it would be so interesting to break it.”11
One of Turing’s first jobs was to reduce the number of tests a bombe had to conduct. Although it was fast, a bombe took 18 minutes to test a possible wheel setting. Assuming the worst, a bombe would need four days to test all 336 possible wheel permutations on an Enigma. Until more bombes could be built, their workload had to be drastically reduced.
Late one night soon after joining Bletchley Park, Turing invented a manual method for reducing the burden on the bombes. It was a highly labor-intensive, Bayesian system he nicknamed Banburismus for the nearby town of Banbury, where a printing shop would produce needed materials.
“I was not sure that it would work in practice,” Turing said.12 But if it did, it would let him guess a stretch of letters in an Enigma message, hedge his bets, measure his belief in their validity by using Bayesian methods to assess their probabilities, and add more clues as they arrived. If it worked, it would identify the settings for 2 of Enigma’s 3 wheels and reduce the number of wheel settings to be tested on the bombes from 336 to as few as 18. At a time when every hour counted, the difference could save lives.
Turing and his slowly growing staff began to comb intelligence reports to collect “cribs,” Bletchley-ese for German words predicted to occur in the plain-text, that is, the original, uncoded message. The first cribs came primarily from German weather reports because they were standardized and repeated often: “Weather for the night,” “Situation Eastern Channel,” and, as one blessed fool radioed nightly, “Beacons lit as ordered.” Reports from British meteorologists about weather in the Channel provided more hunches. Knowing the most frequent letter combinations in German words helped too. When a prisoner of war told them the German navy spelled out numbers, Turing realized that the word “ein” (“one,” “a,” or “an”) appeared in 90% of Enigma messages; Bletchley Park clerks catalogued by hand 17,000 ways “ein” could be encrypted, and a special machine was constructed to screen for them.
In a fundamental breakthrough, Turing realized he could not systematize his hunches or compare their probabilities without a unit of measurement. He named his unit a ban for Banburismus and defined it as “about the smallest change in weight of evidence that is directly perceptible to human intuition.”13 One ban represented odds of 10 to 1 in favor of a guess, but Turing normally dealt with much smaller quantities, decibans and even centibans. The ban was basically the same as the bit, the measure of information Claude Shannon discovered by using Bayes’ rule at roughly the same time at Bell Telephone Laboratories. Turing’s measure of belief, the ban, and its supporting mathematical framework have been called his greatest intellectual contribution to Britain’s defense.
To estimate the probability of a guess when information was arriving piecemeal, Turing used bans to discriminate between sequential hypotheses. He was thus one of the first to develop what came to be called sequential analysis. He used bans to quantify how much information was needed to solve a particular problem so that, instead of deciding how many observations to make, he could target the amount of evidence needed and stop when he had it.
Bans involved a manual, paper-and-pencil system far removed from a modern computerized Bayesian calculation. Bans automated the kind of subjective guessing that Émile Borel, Frank Ramsey, and Bruno de Finetti had tried to validate during the anti-Bayesian onslaught of the 1920s and 1930s. Using Bayes’ rule and bans, Turing began calculating credibility values for various kinds of hunches and compiling reference tables of bans for technicians to use. It was a statistics-based technique and produced no absolute certainties, but when the odds of a hypothesis added up to 50 to 1, cryptanalysts could be close to certain they were right. Each ban made a hypothesis 10 times more likely.
A top modern-day cryptographer explained Turing’s thinking: “When you work day after day, year after year, you need to make a best guess of what’s most likely to be breakable with the resources at hand. You may have too many choices, so you pick the more checkable guesses. At every step you hedge bets. . . . Sometimes you make approximations, and other times you have precisely correct numbers with the right formulas, the right numbers, for the decibans.”14
In operation, Banburismus used 5- or 6-foot-long strips of thin card-board printed in Banbury. Decoders look for repetitions and coincidences, so Wrens, technicians from the Women’s Royal Naval Service, punched each intercepted message by hand, letter by letter, into a Banbury sheet. Then they slipped one strip on top of others so that any two messages could be compared. When enough letter holes showed through both Banburies, the number of repeats was recorded.
As Patrick Mahon, who worked on Banburismus during the war, wrote in his secret history of Bletchley Park, “If by any chance, the two messages have identical content for 4 or 6 or 8 more letters . . . such a coincidence between cipher texts is known as a ‘fit.’”
“The game of Banburismus involved putting together large numbers of pieces of probabilistic information somewhat like the reconstruction of DNA sequences,” Turing’s statistical assistant, I. J. “Jack” Good, explained later.15 Good, the son of a Jewish watchmaker from tsarist Russia, had studied pure mathematics at Cambridge and waited a year for a defense job before being hired on the strength of his chess playing. Good thought “the game of Banburismus was enjoyable, not easy enough to be trivial, but not difficult enough to cause a nervous breakdown.”16 Bayes’ rule was proving to be a natural for cryptography, good for hedging bets when there were prior guesses and decisions to be made with a minimum of time or cost.
Turing was developing a homegrown Bayesian system. Finding the Enigma settings that had encoded a particular message was a classic problem in the inverse probability of causes. No one is sure where Turing picked Bayes up, whether he rediscovered it independently or adapted it from something overheard about Jeffreys, Cambridge’s lone defender of Bayes’ rule before the war. All we know for sure is that, because Turing and Good had studied pure mathematics and not statistics, neither had been sufficiently poisoned by anti-Bayesian attitudes.
In any event, Turing talked at Bletchley Park about bans, not Bayes.
Once Good asked, “Aren’t you essentially using Bayes’ theorem?”17 Turing answered, “I suppose.” Good concluded that Turing knew of the theorem’s existence. But Turing and Good may have been the only ones at Bletchley Park who realized that Banburismus was Bayesian, and heavily so.
Good met a friend, George A. Barnard, one day in London and—strictly against the rules—“told him that we were using Bayes factors, and their logarithms, sequentially, to discriminate between two hypotheses but of course I did not mention the application. Barnard said that curiously enough a similar method was being used for quality control in the Ministry of Supply for discriminating between lots rather than hypotheses. It was really the same method because the selection of a lot can be regarded as the acceptance of a hypothesis.”18 Sequential analysis differed from frequency-based testing, where the number of items to be tested was fixed from the beginning. In sequential analysis, once several tests or observations strongly cleared or condemned a case of, say, field rations or machine-gun ammunition, the tester could move on to the next box. This almost halved the number of tests required, and the use of logarithms massively simplified calculations by substituting addition for multiplication. Abraham Wald of Columbia University is generally credited with discovering sequential analysis for testing ammunition in the United States later during the war. But Good concluded that Turing had used it first and that Turin
g, Wald, and Barnard all deserved credit for discovering and applying it. Oddly enough, after the war Barnard would become a prominent anti-Bayesian.
Turing was making progress when, in May 1940, the doldrums hit. He had both the theory and the method for breaking Enigma codes but still could not read U-boat messages. The Germans were building more U-boats, and Adm. Karl Doenitz had formed wolf packs of subs strung across the North Atlantic; when one U-boat spotted a convoy, it radioed the rest. During the first 40 months of the war, U-boats sank 2,177 merchant ships totaling more than 1 million tons, far more than were lost to German aircraft, mines, warships, and other causes.
If the British were going to be able to route supply convoys around the U-boats, Turing needed more information. He needed to see one of the code-books that U-boat Enigma operators used before broadcasting a ciphered message. One of the factors that made breaking the Enigma code so difficult was that the operator doubly-enciphered a trio of letters that began each message and that indicated the starting positions of the Enigma’s three wheels. The operator enciphered the three letters twice over: once mechanically, with his Enigma machine, and once manually, by selecting one of nine sets of tables in a codebook issued to each sub. The operator learned which table to use each day by consulting a calendar issued with the tables. If a U-boat came under attack, crews had strict orders to destroy the tables either before abandoning ship or as the enemy was about to board.
In a brilliant piece of deduction shortly after war was declared, Turing figured out this double-encipherment system, but he needed a copy of the codebook to make Banburismus work. Enigmas had so many variations that trial-and-error methods were ineffective. A codebook had to be “pinched,” as Turing put it. The wait for a pinch would stretch through ten nerve-racking months.
As Turing waited desperately for the navy to get him a codebook, morale at GC&CS sank. Alastair G. Denniston, the head of GC&CS, told Birch, “You know, the Germans don’t mean you to read their stuff, and I don’t expect you ever will.”19
Long and bitter arguments broke out about whether more bombes should be built, and if so, how many. In August 1940 Birch wrote, “Turing and Twinn are like people waiting for a miracle, without believing in miracles. . . . Turing has stated categorically that with 10 machines [bombes] he could be sure of breaking Enigma and keeping it broken. Well can’t we have 10 machines?”20
A second bombe incorporating Welchman’s improvements arrived later that month, but the fight for more bombes continued throughout 1940. Birch complained that the British navy was not getting its fair share of the bombes: “Nor is it likely to. It has been argued that a large number of bombes would cost a lot of money, a lot of skilled labour to make and a lot of labour to run, as well as more electric power than is at present available here. Well, the issue is a simple one. Tot up the difficulties and balance them against the value to the Nation of being able to read current Enigma.”21
To capture a codebook, Lt. Cmdr. Ian Fleming, the future creator of James Bond but at the time an aide to the head of Britain’s Directorate of Naval Intelligence, concocted Operation Ruthless. It was a scheme worthy of his postwar spy. The British would outfit a captured German plane with a crew that was to include a “word-perfect German speaker” (Fleming himself, who had studied German in Austria as a youth).22 After the plane faked a crash into the Channel and its crew was rescued by a German boat, the British would capture the vessel and bring it and its Enigma equipment home to Turing. The escapade was elaborately planned but canceled, and Turing and Twinn went to Birch looking “like undertakers cheated of a nice corpse . . . , all in a stew.”23 Instead, documents and papers—bits and pieces of clues to the contents of the all-important codebooks—were taken from two weather ships captured off Iceland and, in a commando raid organized specifically to help Turing, from an armed German trawler off the Norwegian coast. With these clues, Turing began trying to deduce the contents of the all-important codebooks.
Turing’s group was beginning to break the German naval cipher on the glorious day of May 27, 1941, when the British sank the Bismarck, then the world’s largest battleship. By June Turing had succeeded in reconstructing the codebooks from various clues, and for the first time Bletchley Park could read the messages to and from the U-boat wolf packs within an hour of their arrival. Finally, the British could reroute convoys safely around the subs. For 23 blessed days in June 1941, a time when Britain still fought alone, no convoy in the North Atlantic was attacked.
By then, Bletchley Park regarded Turing fondly as its eccentric genius, although some of his unconventional behavior made practical sense. He wore a gas mask while bicycling to work during the June hay fever season. And he managed his bicycle’s broken chain by counting pedal strokes and executing a certain maneuver every 17 revolutions. Bicycle parts were scarce, and he liked identifying repeated patterns in his work.
By autumn of 1941, Banburismus was again in trouble, critically short of typists and junior clerks, otherwise known as “girl power.” Turing and three other decoders took a direct but unorthodox approach to the problem. Appealing directly to Churchill on October 21, they wrote, “We despair of any early improvement without your intervention.” Welchman probably drafted the letter, but Turing signed it first, followed by Welchman, their colleague Hugh Alexander, and P. Stuart Milner-Barry, a Cambridge mathematics graduate who was the chess correspondent for The Times newspaper. Milner-Barry took a train to London, hailed a taxi, and “with a sense of total incredulity (can this really be happening?) invited the taxi driver to take him to 10 Downing Street.” There he persuaded a brigadier general to deliver the letter personally to the prime minister and to stress its urgency.
Churchill, who had visited Bletchley Park, had recently been informed that Britain was running out of food and war supplies. He immediately sent a memorandum to his chief of staff: “Action this day: Make sure they have all they want on extreme priority and report to me that this had been done.”24 Turing and company heard nothing directly in response but noticed that work went more smoothly, bombes were built faster, and staff arrived sooner.
As Bletchley Park was beginning to break naval Enigma, Hitler invaded Russia with two-thirds of his forces in June 1941 and launched a merciless bombardment of Moscow. Early in the campaign, Russia’s greatest mathematician, Andrei Kolmogorov, was evacuated east to safety in Kazan along with the rest of the Russian Academy of Sciences. Shortly after, Russia’s Artillery Command, reeling from Germany’s massive bombing raids, asked Kolmogorov to return to the capital for consultations. Amidst the chaos, he was lodged for awhile on a sofa.
In a country that idolized its intelligentsia, Kolmogorov was a famous man. When a professor’s wife heard he was going to visit her home, she began frantically cleaning and cooking. When a maid asked why, the hostess replied, “How can I explain it to you? Just imagine that you will be getting a visit from the tsar himself.”25 Kolmogorov’s legend began with his mother, an independent woman of “lofty social ideals” who never married and died in childbirth. Her two sisters raised Andrei, ran a small school for him and his friends, and published a newsletter with little problems he had composed, such as “How many different ways can a button with four holes be sewn?”26 At the age of 19 at Moscow State University he escaped final examinations in his 14 courses by writing 14 original papers. He was more proud of having taught school to pay his way through the university than of winning any of his awards; late in life he volunteered at a school for gifted children, where he introduced them to literature, music, and nature.
Kolmogorov became the world’s authority on probability theory. In 1933 he demonstrated that probability is indeed a branch of mathematics, founded on basic axioms and far removed from its indecorous gambling origins. So fundamental was Kolmogorov’s approach that any mathematician, frequentist or Bayesian, could legitimately use probability. Kolmogorov himself espoused the frequentist approach.
Now the generals were asking him about using Bayes agains
t the German barrage. Russia’s artillery, like that of the French, had used Bayesian firing tables for years, but the generals were split over an esoteric point about aiming. They asked Kolmogorov his opinion.
“Strictly speaking,” he told the generals, starting with Bayes’ 50–50 prior odds was “not only arbitrary but surely wrong because it contradicts the main requirements of the probability theory.”27 But with Germany on Moscow’s doorstep, Kolmogorov felt he had no choice but to start with equal priors. Agreeing with Joseph Bertrand’s strictly reformed version of Bayes, Kolmogorov told the generals they should start with 50–50 odds whenever shooting repeatedly at a small area. Because it was sometimes better to shoot randomly than aim precisely, the guns in a battery of weapons should aim slightly wide of the mark, the way a hunter shooting at moving birds uses pellets for wider dispersion.
That same autumn of 1941, Kolmogorov taught a wartime course at Moscow State University on firing dispersion theory and made the class compulsory for probability majors. Surprisingly, on September 15, 1941, three months into the German invasion of Russia, Kolmogorov submitted his theory of firing to a journal for publication. The article was so mathematical and theoretical that Russia’s censors, not realizing it could help the Germans as well as the Russians, allowed it to be printed in 1942. Fortunately, the enemy did not understand the theory any better than the censors did. After the war Kolmogorov published two more practical problems of Bayesean artillery that are still in print—in English—for military authorities to study. Years later a general in the Russian artillery recalled that during the invasion Kolmogorov “did a lot of useful things for us as well, we remember it, and appreciate him too.”28
The Theory That Would Not Die Page 10
