Alan Turing: The Enigma The Centenary Edition

by Andrew Hodges

  (2.37) AMT’s great paper, quoted here, was ‘On Computable Numbers, with an Application to the Entscheidungs problem’, Proc. Land. Math. Soc. (2), 42 (1937). It is reprinted in The Undecidable (as note 2.31).

  (2.38) Did AMT think in terms of constructing a universal machine at this stage? There is not a shred of direct evidence, nor was the design as described in his paper in any way influenced by practical considerations. Yet in his obituary of AMT in The Times, Newman wrote: ‘The description that he then gave of a “universal” computing machine was entirely theoretical in purpose, but Turing’s strong interest in all kinds of practical experiment made him even then interested in the possibility of actually constructing a machine on these lines.’ (My italics.) Newman did not repeat this claim in his Royal Society memoir, in which the practical side was so much played down, although there he commented on how bold an innovation it had been to bring ‘paper tape’ into symbolic logic. Both comments reflected the impact made by AMT’s concreteness upon a classical pure mathematician, but like the other obituary writers, Newman was concerned to delineate AMT’s mental unorthodoxy, rather than to document anything in the history of technology. We have nothing more to go on. My own belief is that the ‘interest’ must have been at the back of his mind all the time after 1936, and quite possibly motivated some of his eagerness to learn about engineering techniques. But as he never said or wrote anything to this effect, the question must be left to tantalise the imagination.

  New Men

  (3.1) A. Church, ‘A Note on the Entscheidungs problem’, in J. Symbolic Logic, 1 (1936), reprinted in The Undecidable (note 2.31). The paper of a year earlier was ‘An Unsolvable Problem of Elementary Number Theory’, Amer. J. Math. 58 (1936), presented 19 April 1935.

  (3.2) The first letter in what was to be a more copious flow of correspondence during the Princeton period, in which AMT managed while away to think of something to say every three weeks or so. There are only eighteen letters in KCC for the five academic years 1931 to 1936, but twenty-eight for the two Princeton years. This frequency was never resumed, a total of nine letters home representing the remaining sixteen years of his life.

  (3.3) G.H. Hardy, AMathematician ‘s Apology (Cambridge University Press, 1940).

  (3.4) When Mrs Turing came to write her biography, she found herself better informed about AMT’s environment at Princeton than anywhere else, thanks to his letters. Though largely transcribing the information in these, she added one story which does not derive from a KCC letter: ‘Though prepared to find democracy in full flower, the familiarity of the tradespeople surprised him; he cited as an extreme case the laundry vanman who, while explaining what he would do in response to some request of Alan’s, put his arm along Alan’s shoulder. “It would be just incredible in England.’” Perhaps there was something of an ‘alas!’ in AMT’s remark, which would not have fitted in with Mrs Turing’s ideas about tradesmen.

  (3.5) Two postcards from Scholz, dated 11 February and 15 March 1937, are in KCC.

  (3.6) A remark quoted in the review of von Neumann’s contributions to the ‘Theory of Games and Mathematical Economics’, by H.W. Kuhn and A.W. Tucker, Bull. Amer. Math. Soc. 64 (1958).

  (3.7) Published posthumously in The Undecidable (note 2.31).

  (3.8) Post’s paper is reprinted in The Undecidable.

  (3.9) Letter to the author from Dr A.V. Martin, 26.1.78.

  (3.10) See note 8.67.

  (3.11) The brief logic paper was in J. Symbolic Logic, 2 (1937). The work related to that of Baer was in Compositio Math. 5 (1938). The other group theory paper was in Ann. Math. (Princeton) 39 (1938).

  (3.12) A copy of von Neumann’s letter is held in AMT’s file at the Department of Mathematics, Princeton University. Formal recommendation of AMT came from the Vice-Chancellor of Cambridge University on 25 June.

  (3.13) One letter from Bernays to AMT, dated 24 September 1937, is in KCC. AMT’s correction note appeared in Proc. Lond. Math. Soc. (2) 43 (1937). There were other mistakes and inconsistencies in the specification of the universal machine, some of them detailed by Post in a 1947 paper (reprinted in The Undecidable, as note 2.31).

  (3.14) J. Symbolic Logic, 2 (1937).

  (3.15) As described in The Undecidable, page 71.

  (3.16) J.B. Rosser, J. Symbolic Logic 2 (1937).

  (3.17) Letter from A.E. Ingham dated 1 June 1937 in KCC.

  (3.18) The following account draws heavily on H.H. Edwards, Riemann’s Zeta Function (Academic Press, New York, 1974), which also discusses AMT’s contributions.

  (3.19) S. Skewes, J. Lond. Math. Soc. 8 (1933). There is a letter in KCC from Skewes, dated 9 December 1937, with a brief expression of interest in AMT’s ideas.

  (3.20) A.G.D. Watson, ‘Mathematics and its Foundations’, in Mind 47 (1937).

  (3.21) AMT was right. During the war Gerard Beuttell made important contributions to the design of instruments to estimate the visual range by measuring the scattering of light within a small enclosed space. (J. Scientific Instruments, 26 (1949)). He died on a meteorological reconnaissance flight over the north Atlantic in early 1945.

  (3.22) Letter to the author from Dr M. MacPhail, 17.12.77.

  (3.23) It was in service until 1960, then being supplanted by a digital computer, and may now be seen in the Liverpool City Museum.

  (3.24) Letter from E.C. Titchmarsh in KCC.

  (3.25) The original PhD thesis is held in the mathematics library at Princeton University; it was published as ‘Systems of Logic based on Ordinals’ in Proc. Lond. Math. Soc. (2) 45 (1939), and reprinted in The Undecidable.

  (3.26) Letter to the author from Professor S. Ulam, 16.4.79.

  (3.27) C. Andrew, ‘The British Secret Service and Anglo-Soviet Relations in the 1920s, Part I’ in the Historical Journal, 20 (1977).

  (3.28) Hinsley I (see note 3.31), page 10.

  (3.29) Hinsley I, page 20.

  (3.30) Administrative files relating to GC and CS are held at the Public Record Office in FO 366.

  (3.31) F.H. Hinsley et al., British Intelligence in the Second World War. Volume I (1979), Volume II (1981). Published by HMSO as an official war history.

  (3.32) FO 366/978.

  (3.33) Hinsley I, page 54.

  (3.34) As note 3.27.

  (3.35) Hinsley I, page 53.

  (3.36) Hinsley I, page 54.

  (3.37) From records of the Faculty of Mathematics, Cambridge University.

  (3.38) Parts of the revised Encyklopädie appeared in December 1939, but Scholz’s section on the foundations of mathematics, including the reference to AMT’s work, had to wait until August 1952.

  (3.39) A transcript compiled from notes taken by others attending the lectures has been published as Wittgenstein’s Lectures on the Foundations of Mathematics, Cambridge 1939, ed. Cora Diamond (Harvester Press, 1976). The quoted dialogue comes from lectures 21 and 22. It is perhaps a pity that the most extensive verbatim record of AMT should be concerned with a discussion which was not central to his concerns, and where he was not in his element. AMT sometimes liked to give the impression that he had scored off Wittgenstein at some point, but if so the evidence is not to be found in this transcript. In fact he showed a curious diffidence, one feature being that despite long discussions about the nature of a ‘rule’ in mathematics, AMT never offered a definition in terms of Turing machines.

  (3.40) This is in KCC. It was corrected and completed by A.M. Cohen and M.J.E. Mayhew, Proc. Lond. Math. Soc. (3) 18 (1968). Using AMT’s approach they reduced the ‘Skewes number’ to . But in 1966 R.S. Lehman had by another method reduced the bound to the comparatively miniscule value of 1.65 X 101165.

  (3.41) His paper ‘A Method for the Calculation of the Zeta-function’ appeared only in 1943, in Proc. Lond. Math. Soc. (2) 48.

  (3.42) Quoting from a copy of part of the letter made by Mrs Turing and deposited in KCC. My guess is that she omitted some reference to the function of the proposed machine as a cipher generator, not knowing whether thi
s would be a transgression of secrecy.

  (3.43) Minutes of the Council of the Royal Society.

  (3.44) The blueprint, initialled ‘D.C.M.’, is in KCC.

  (3.45) Hinsley I, page 51.

  The Relay Race

  (4.1) Letter and list of names in FO/366/1059, which contains no further reference to AMT.

  (4.2) M. Muggeridge, The Infernal Grove (Collins, 1973).

  (4.3) Pre-eminently H.F. Gaines, Elementary Cryptanalysis, 1939. Only at the end of the 1970s did a serious technical discussion of specific modern cipher systems begin to appear.

  (4.4) I am grateful to the staff of the National Archives, Washington, for bringing this material to my attention. In late 1940 the German raider Komet made several captures of British merchant ships and took this code and cipher material. This then found its way into German archives captured after the war.

  (4.5) There is an account of Polish Enigma work in the appendix to J. Garlinski, Intercept (Dent, 1979). A fuller and better version is given by M. Rejewski, ‘How Polish Mathematicians Deciphered the Enigma’, in Annals of the History of Computing 3 (1981). This would seem to be the definitive account, ending much confusion and speculation in earlier discussions.

  (4.6) Hinsley I, page 490, itself quoting from the Polish claim at the time.

  (4.7) Hinsley I, page 492.

  (4.8) Letter to the author from Professor R.V. Jones, 7.2.78, expanding upon a passage of his Most Secret War (Hamish Hamilton, 1978).

  (4.9) The following account of the Bombe is a simplified version of Gordon Welchman, The Hut Six Story (McGraw Hill, New York; Allen Lane, London, 1982). It is worth noting Welchman’s comment: ‘We thought very little, in these hectic days, of who should take credit for what.’ AMT would have thought least of all, though he did say that he thought Welchman’s idea had been the important one. Establishing priority and originality is hard enough in open work, let alone when considering ideas kept secret for over forty years. I hope that the departure from truth, in this and other passages suffering from the same difficulty, is not too great. The more important point lies in the fact that pre-war cryptology, fossilised and isolated by secrecy, was transformed as soon as any contemporary mathematical mind was brought to bear on the subject.

  (4.10) Hinsley I, page 493. The account in B. Johnson, The Secret War (BBC, London, 1978), identifies AMT as the ‘emissary’, following a statement made to BBC researchers by General Bertrand before his death. This seems rather unlikely as he was working on the Bombe, not the sheets, and as this was not really a job for a ‘man of the Professor type’. But it might be so – I have found no further evidence one way or the other. EST has a story concerning AMT being sent abroad, a mix-up over papers, and managing for a day with ‘a few francs’, but this could be taken to fit the 1945 mission (page 311).

  (4.11) P. Beesly, Very Special Intelligence (Hamish Hamilton, 1977), which gives the Admiralty side of the story.

  (4.12) Hinsley I, page 103.

  (4.13) Hinsley I, page 336.

  (4.14) Hinsley I, page 163.

  (4.15) F.W. Winterbotham, The Ultra Secret, (Weidenfeld & Nicolson, 1974), which gives a secret service view.

  (4.16) P. Beesly, as note 4.11.

  (4.17) Hinsley I, page 109.

  (4.18) Hinsley I, page 144.

  (4.19) Hinsley I, page 336.

  (4.20) I.J. Good, ‘Studies in the History of Probability and Statistics XXXVII. A.M. Turing’s Statistical Work in World War II’, in Biometnka 66 (1979), which this description of AMT’s ideas follows closely. Further details are given in a note by Good appended to the article by M. Rejewski (note 4.5).

  (4.21) Quoting from I.J. Good’s lecture at the National Physical Laboratory, 1976; this has since been published in slightly revised forms in several places, the most accessible being as a paper ‘Pioneering Work on Computers at Bletchley’ in the misleadingly entitled volume A History of Computing in the Twentieth Century, eds. N. Metropolis, J. Howlett and G.-C. Rota (Academic Press, New York, 1980).

  (4.22) Quotation is from Beesly, as note 4.11, although I follow Hinsley in stating the capture to have been planned and not an accident.

  (4.23) Messages as translated into English at the time, and taken from the first few pages of the gigantic PRO file DEFE 3/1.

  (4.24) Hinsley I, page 337.

  (4.25) Beesly, as note 4.11, pages 57, 97.

  (4.26) Hinsley I, pages 273-4.

  (4.27) Quoted in EST. There he appeared anonymously (presumably because working for GCHQ) as a colleague who later proved a ‘staunch friend’ – Mrs Turing’s only concession to the events of 1952.

  (4.28) Hinsley I, page 296.

  (4.29) R. Lewin, Ultra Goes to War (Hutchinson, 1978), page 183.

  (4.30) Obituary of A.C. Pigou by D.G. Champernowne in Roy. Stats. J. A122 (1959).

  (4.31) As note 4.2.

  (4.32) Dorothy Sayers, The Mind of the Maker (Methuen, 1941). AMT referred to reading it in the first wartime letter to his mother, in August 1941 (see note 5.8), saying ‘You should read it when you come.’ The quoted passage is the one he himself quoted in 1948 (see page 377).

  (4.33) Princeton records show that von Neumann gave a popular lecture on the game of poker on 19 March 1937. It would be very surprising if AMT had not attended it. He did not, in his discussions with Jack Good, draw a connection between his chess programs and game theory – nor indeed with the machines of Computable Numbers. But I have assumed that he had a general acquaintance with game theory, just as he could hardly have forgotten his own ‘machines’. I have also given space to game theory for another reason: AMT certainly showed an interest in it later, and often pointed out examples of strategies in everyday life.

  (4.34) AMT’s letters to Newman are in KCC. They are undated but can mostly be placed by passing references to events.

  (4.35) This essay, ‘The Reform of Mathematical Notation and Phraseology’, remained unpublished. The typescript is in KCC with other unpublished work on type theory. Excerpts are included in a historical paper by R.O. Gandy, ‘The Simple Theory of Types’, in Logic Colloquium 1976, eds. R.O. Gandy and J.M.E. Hyland (1977).

  (4.36) AMT’s joint paper with M.H.A. Newman was ‘A Formal Theorem in Church’s Theory of Types’, in J. Symbolic Logic 7 (1942).

  (4.37) AMT’s paper appeared in the same 1942 volume of the Journal of Symbolic Logic. The two ‘forthcoming’ papers, ‘Some Theorems about Church’s System’ and ‘The Theory of Virtual Types’, never appeared. But in 1947 (see page 355 and note 6.34) he submitted a further paper on type theory which represented a revision of work done at this period.

  (4.38) Hinsley I, page 338.

  (4.39) Beesly, as note 4.11, page 164. I have inserted ‘September’ for Beesly’s ‘November’ to make it consistent with the Hinsley account.

  (4.40) Letter quoted from Hinsley II, page 655.

  (4.41) Hinsley II, page 657.

  (4.42) Quoting from B. Randell, The Colossus, an account written from the engineering side. First published as a University of Newcastle-upon-Tyne report in 1976 this is now available in the Metropolis volume (see note 4.21).

  (4.43) Peter Hilton was speaking informally during a conference session of Reminiscences of Logicians, published as a section of Algebra and Logic, Springer Mathematical Notes 450, ed. J. Crossley, 1975.

  (4.44) As note 4.21.

  (4.45) Hinsley II follows earlier writers in calling the German enciphering machine a Geheimschreiber. But my understanding is that there was more than one type of machine covered by this generic term, and that the photograph of a Siemens machine in B. Johnson, The Secret War (as note 4.10) is not actually of the one that was deciphered as Fish.

  (4.46) As note 4.43.

  (4.47) Stories taken from EST. With mind-boggling sang froid she added: ‘The idea of “Prof.” being nearly arrested caused much amusement in his department.’

  (4.48) As note 4.43.

  (4.49) Hinsley II, page 56.

  (4.50)
I am grateful to the State Department for supplying copies of documents relating to AMT’s entry to the US in 1942. They are of a purely routine administrative nature. They account for all the references to AMT in the general index to State Department files held in the National Archives, Washington. In contrast, there are no corresponding British documents. There is a reference in the index to Foreign Office correspondence for 1942 to ‘Turing: sea travel facilities to Washington: finances.’ But the relevant file has been ‘weeded’: destroyed.

  (4.51) FO/371/32346.

  (4.52) As note 4.2.

  (4.53) I owe this reference to Dr G. DiVita. It was on 14 February 1941. Of course the report gave no indication of the scale and modernity of operations, but it is curious to see any mention whatever of ‘Nazi codes’ being broken, when comprehensive secrecy on the subject lasted for a quarter of a century after Nazi Germany’s demise.

  (4.54) For AMT’s pre-war voyages I was able to draw upon the Board of Trade passenger lists. But none exist for the wartime period, so the evidence here is indirect. The State Department information (see note 4.50) shows that he was admitted at New York on 13 November 1942. Information from the Naval Historical Center, Department of the Navy, Washington D.C. shows that this was the day that the Queen Elizabeth arrived.

  The fast passenger liners converted to troop transporters being the normal means of ferrying high-level personnel, I have assumed this to settle the question. But it is confused by the statement of Mrs Turing that his passage west was very overcrowded, and that he was the only civilian on board apart from a couple of children. Here, surely, she was mistaken. It was the eastbound passages which were desperately crowded. The Queen Elizabeth carried a mere 557 passengers west, most of them civilians, to return in March with 10,261 troops. See also note BP 11, for evidence regarding AMT’s eastbound voyage.