My Publications

The Military Use of Alan Turing by Andrew Hodges for a conference volume on Mathematics and War (2003/4). For a guide to this website go to the Alan Turing Home Page

Abstract: Alan Turing (1912-1954), British mathematician, was critical in the Anglo-American decipherment of German communications in the Second World War. This experience enabled him to formulate an original plan for the digital computer in 1945, based on his own 1936 concept of the universal machine. He went on to found the program of Artificial Intelligence research. This article discusses the relationship between these developments, and more general questions of mathematics and war illustrated by Alan Turing's life and work.

This article will review Alan Turing's mathematical work in the Second World War, discuss how this relates to the history and philosophy of computing, and then raise the wider question of his place in mathematics and war.

Turing's role in the Second World War was largely dominated by the particular form of the Enigma ciphering machine as elaborated for military and naval purposes by the German authorities. For a recent complete description of the Enigma see (Bauer 2000). Essentially, it was Turing who picked up the relay baton when the Polish mathematicians shared their brilliant cryptanalytic work with Britain and France. It then fell to him to pass on the baton, by sharing British achievements with the United States.

Alan Turing's primary role stemmed partly from the fact that he was the first  scientific figure to join the British cryptanalytic department, the so-called 'Government Code and Cypher School,' which until 1938 was staffed essentially by the language-based analysts of the First World War. (One reason for Turing's recruitment may have been that he had, through his Fellowship of King's College, Cambridge, personal connections with that older British generation; in particular J. M. Keynes may well have formed an important link.) Turing was brought into the work on a part-time basis at the Munich crisis period, and joined full-time immediately on declaration of war. Meanwhile an Oxford mathematics graduate, Peter Twinn, was recruited through open advertisement in 1938, and this belated acceptance of the modern world was shown also in the development of a modern communications infrastructure for the new headquarters at Bletchley Park, Buckinghamshire. Nevertheless, the Polish mathematicians were well in advance at the time of the now famous meeting in July 1939. They had used group-theoretic algebra to deduce the Enigma rotor wirings from information obtained by spying; they had noticed and used other group-theoretic methods and mechanical methods to exploit certain simple forms of indicator system that were then in use by the German forces. It is not clear to what extent Turing had discovered these independently in early 1939 — his report (Turing 1940) does not say — but in any case the Polish group had successfully made an all-important guess which had eluded the British: this was the order in which the keyboard letters were connected to the first rotor. They were in fact in the simple order ABCD.... This almost absurdly simple fact was the most critical piece of information imparted by the Poles.

In late 1939, Turing initiated the two most decisive new developments: he saw the 'simultaneous scanning' principle of what became the British 'Bombe', and he deduced the form of the more sophisticated indicator system that was being used for the German Naval communications.

Turing's 'Bombe' was an electromechanical machine of great logical and technical sophistication. Its property was this: given a stretch of ciphertext and the corresponding plaintext, it could search through all possible settings of the military Enigma and detect those which could possibly have been responsible for the encipherment. It is not difficult to see, from simple counting arguments, that a 'crib' of about 20 letters will generally serve to identify such a setting. (The reader may take it that, once some penetration into cipher traffic has been made, such a 'crib' is not impossible to find.) It is much harder to see that this theoretical possibility can be matched by any practical method. In particular, the Stecker  or plugboard complication introduced in the military Enigma had so many possible settings that serial trial was impossible. In fact serial trial was indeed necessary for searching through the possible positions of the rotors. But Turing's great discovery was that the huge number of plugboard possibilities could effectively be tested in parallel, and virtually instantaneously. His idea was this: suppose we are testing, in the serial sequence, a particular rotor setting. A plugboard setting consists of a number of pairs like (AJ), (UY), representing the swapping of letters performed by the plugboard on entry to, and on exit from, the rotors. There are 150,738,274,937,250 possible settings consisting of ten such pairs, the choice normally made. However there is no need to work through such a number of possibilities. Instead, consider the smaller number of 325 basic pair-possibilities: (AA), (AB), (AC) ... (ZZ), where '(AA)' represents the letter A being left unchanged by the plugboard. Now, given any one basic pair-possibility, e.g. (AA), knowledge of the plaintext, ciphertext, and rotor setting will imply various other pair-possibilities, and these in turn yet more. Turing saw first, that finding a single 'contradiction' serves to eliminate a possibility: that is, if by following the implications (AA) can be shown to imply (AE), then (AA) must be false. He saw the less obvious point that by allowing the logical deductions to continue, (AA) would generally imply all  of (AB) ... (AZ); hence all  must be false; hence the rotor position being tested could not possibly be correct. Turing was proud of this counter-intuitive idea, of continuing to follow through the consequences of what must be false propositions. He said it was akin to the principle in mathematical logic that 'a false proposition implies any proposition.'

Turing also saw how to embody these 'deductions' simply in wired connections between rotors and terminals, so that the flow of implications would take place at the speed of electric current. (But it took another Cambridge mathematician, W. G. Welchman, to improve the circuitry with the 'diagonal board' which automatically identified (AB) with (BA), and so on; it is a curious fact that Turing missed this simple idea.) Finally, it was essential that the machine could be equipped to detect the possibility of a correct   rotor position, with logical switching capable of recognising an incomplete bank of pair-possibilities. With this achieved by the engineers of the British Tabulating Machinery company, Turing's Bombe yielded the central process on which Enigma decryption rested throughout the War. Its principle was highly non-trivial, and it apparently went unnoticed by G. Hasenjäger, the young German logician who was Turing's unseen opponent in this war of logic (Bauer, 2000).

As already noted above, in the business of searching through the 26³ possible rotor positions, no improvement was possible on serial trial using the equivalent of moving Enigma rotors, so that improvements rested on having ever faster, more reliable machines produced in larger numbers. For the question of the choice of rotors and their order, however, which was particularly relevant for the Naval Enigma problem, Turing developed a method called 'Banburismus' which, particularly in 1941, much improved upon the simple trial of the possibilities. This method rested on the logical details of the turnover positions of the different rotors, but also on assessing the statistical identification of likely 'depths' — two different stretches of message, both sent on the same Enigma settings. For detecting depths objectively, giving a reliable probability measure to them, Turing developed a theory of Bayesian inference. The most striking feature of his theory was his measurement of the weight of evidence by the logarithm of conditional probabilities. This was essentially the same as Shannon's measure of information, developed at the same time. This theory was developed into sophisticated methodology (Good 1979, 2000). Whilst the logical principle of the Bombe, and its amazingly effective application, was perhaps Turing's most brilliant single idea, his statistical techniques were more general and far-reaching. In particular, they were also applied to the quite different Lorenz cipher system employed by Germany for high-level strategic messages. Thus it was Turing's theory of probability estimation that underlay the methods mechanised by the large electronic 'Colossus' built in 1943-45 to decipher this type of traffic.

The latter half of the war saw the relay baton pass on to the USA. Turing himself had to cross the Atlantic, at the height of the battle, in connection with naval Enigma crisis of 1942 and the building of American Bombes at Dayton, Ohio. Besides transferring British expertise in Enigma-breaking to the United States, he also had a new top-level role in inspecting and reporting on the American equipment for speech encipherment (to be used by Roosevelt and Churchill), and became fully acquainted with the use of information sampling theory as well as the electronic technology involved. It is fair to say that Turing most enjoyed a pioneering period of breaking into the unknown, and flourished best in such settings; he was not so happy at detailed follow-up or development. After 1943 he spent much of his time on a freshly self-imposed problem: the design of an advanced electronic speech scrambler of a much more compact form than the American equipment he had inspected (Hodges 1983, p. 273).

Sometimes it is blithely asserted that what one mathematician can do, another can undo. Not so: the possibilities of cryptanalysis are highly contingent on details; and even if a system is breakable in the long term, short term considerations may be of the essence. The German military adaptation of the Enigma might have made it unbreakable; the British version of the Enigma, which has attracted far less attention, had more rotors and a non-reciprocal plugboard, and was apparently invulnerable to German attack. The successful continuation of the Polish work may very well have depended critically on Turing as an individual. It was not that Turing merely played the expert part expected of him. Rather, it was at a time when a distinctly pessimistic attitude prevailed, that Turing took on the Naval Enigma problem precisely because no-one else thought it tractable, and so he could have it to himself. This individualistic approach was also necessary in developing from scratch a suitable statistical theory. Thus, it can well be maintained that the Anglo-American command of the Atlantic battle, crucial in the central strategy of the Western war, was owed to Alan Turing's work.

Turing did not create great new fundamental mathematics in this work, but he brought to bear the insights of a deep thinker. The Bletchley Park analysts compared their work with chess problems, and G. H. Hardy had famously called chess problems the hymn tunes of mathematics, as distinct from serious, interesting problems (Hardy 1940). Yet unusually these military hymns had some beauty. In a remarkable comment on an episode in mathematics and war, the contemporary chronicler of the Naval Enigma section ended (Mahon 1945)

In finishing this account of Hut 8's activities I think that it should be said that while we broke German Naval Cyphers because it was our job to do so and because we believed it to be worthwhile, we also broke them because the problem was an interesting and amusing one. The work of Hut 8 combined to a remarkable extent a sense of urgency and importance with the pleasure of playing an intellectual game.

It can, however, be argued that more important than the direct application of new mathematics, was the influence of his wartime experience in leading Turing from being a pure theorist of computation, to being the leading expositor of an actual electronic design for a modern computer. At the age of twenty-four, Turing had published what is now his most celebrated work, defining computability (Turing 1936-7). Its motivation lay in pure mathematical logic, clarifying the nature of an 'effective method' with the Turing machine concept. It did not set out to assist practical computation in any way. Yet it did produce the constructive and highly suggestive idea of the universal Turing machine, and in fact Alan Turing was never entirely 'pure' in his approach: bringing 'paper tape' into the foundations of mathematics was itself a striking breach of the conventional culture. As we shall see, he took an interest in the practical application of his ideas even in 1936. But Turing's harmonious collaboration with the engineers of the Bombe took him very much further towards practicality, indeed into the most advanced practical engineering of 1940. Then his acquaintance with the world-leading technology of the Colossus showed him the viability of a electronic digital machine capable of embodying the idea of the universal machine — in modern terms, a computer with modifiable stored program. Turing was able to write a detailed proposal for such a computer, the ACE, in 1945-6, and was able to survey from a position of considerable strength all the possible forms of data storage available at that point (Turing 1946).

Quick Links: