# Alan Turing in America

Author(s):
David E. Zitarelli (Temple University)

### Overview

Alan Turing visited the United States during 1936-38 and 1942-43.  This article describes how two of Turing's greatest accomplishments, in logic and computer design, were influenced by the first of his two visits to the U.S.

# Alan Turing in America – Introduction

Author(s):
David E. Zitarelli (Temple University)

Figure 1.  Alan Turing (1912-1954)  (Source: MacTutor History of Mathematics Archive)

The British mathematician Alan Turing has perhaps achieved greater fame today than during his lifetime.  Thirty-two years after his death in 1954 a play based on part of his work, Breaking the Code, opened in London’s West End theater district; it played in New York the next year.  The Broadway production was nominated for three Tony Awards, a rare accomplishment for a theatrical piece about a mathematician.  But Turing was no ordinary mathematician.  The play deplored his sad demise apparently caused by his homosexuality.  More recently, the movie The Imitation Game depicted Turing’s early education, role in deciphering Enigma in World War II, and the tragedy of his death at age 41.  Here I describe how two of his greatest accomplishments were influenced by one of his two visits to the U.S.

The authoritative account of the life and career of Alan Turing is a book by Andrew Hodges [10].  Two more recent works from different viewpoints are [3] and [11].  In addition, online files from a Princeton conference held to commemorate Turing’s 100th birthday can be accessed at:  http://www.princeton.edu/turing/

# Alan Turing in America – Logic

Author(s):
David E. Zitarelli (Temple University)

It does not seem to be well-known that Alan Mathison Turing (1912-1954) spent two academic years at Princeton University, from the summer of 1936 to the summer of 1938.  Before then Turing had entered Cambridge University in 1931 and while there in the spring of 1935 took a course given by the topologist M.H.A. Hodges called “Foundations of Mathematics” that would dramatically alter the direction of his life.  One of the primary topics in the course was Hilbert’s Entscheidungs problem, which asked if it was possible to find an algorithm that would determine whether an inference in a formal logic system was valid.  Turing soon showed that no such algorithm exists.  (See [8] for a modern analysis of this work.)

This was such a critical breakthrough that Hodges encouraged him to put it in print at once.  But the painfully shy Turing hesitated and did not write up his results until the spring of 1936.  Within days of handing the first draft to Hodges for review, his mentor received the most recent issue of the American Journal of Mathematics, which contained a devastating article by Princeton’s Alonzo Church (1903-1995) establishing the same result [2].

Figure 2. This photo of a young Alan Turing is believed to have been taken during the years he was at Princeton University.  (Source: Convergence Portrait Gallery)

Turing could have wilted under such bad news but instead he flashed resilience.  Events then moved quickly.  That very day Hodges wrote directly to Princeton logician Alonzo Church seeking support for his star student to visit the university.  Church was totally supportive and so that fall Turing crossed the Atlantic to study with Church himself.  By the time Turing arrived he realized that although he had reached the same negative solution to the Entscheidungs problem as Church, his approach was sufficiently different to be worthy of separate publication.  Therefore Turing submitted the paper, “On computable numbers with an application to the Entscheidungsproblem,” to the Proceedings of the London Mathematical Society.  However, mathematics journals generally do not publish papers covering results that have already appeared in print.  By then Hodges was convinced of Turing’s talents and “canvassed vigorously to gain support for [his] paper, writing to [the editor] F.P. White … to argue for its publication” [4, p. 178].

By the time the paper appeared in 1937, Turing had added an appendix “Computability and effective calculability” outlining a proof that his concept of computability was equivalent to Church’s $$\lambda$$-definability.  Turing listed his address as “The Graduate College, Princeton University, New Jersey, U.S.A.”  Moreover, the appendix began, “Added August 28, 1936.”  These two facts misled some people to conclude erroneously that his work had been completed under Church’s direction.

Figure 3. Alonzo Church in October of 1943, Princeton University, New Jersey (Source: Wikimedia Commons)

Alan Turing did study under Alonzo Church over the next two years, however, culminating in his Ph.D. in 1938.  Princeton was so impressed with the quality of this work during his first year as a graduate student that the university awarded him a prestigious Proctor Fellowship for the second year.  His doctoral dissertation, “Systems of logic based on ordinals,” dealt with the undecidability of transfinite sequences of certain formal systems, a study that had been inaugurated by Kurt Gödel.  Thus Turing was deeply influenced by two logicians in the U.S.—Church at Princeton University and Gödel at the Institute for Advanced Study in Princeton.

Before Alan Turing came to America in the summer of 1936 he had resolved one of Hilbert’s famous problems in the negative.  This result alone would have earned him immediate recognition but it was the approach he adopted that has gained him an international reputation that is as strong today as ever primarily because it transcended mathematical logic and became fundamental to the study of modern computers.

# Alan Turing in America – Computers

Author(s):
David E. Zitarelli (Temple University)

Figure 4.  Alan Turing on a 2000 "millennium" stamp commemorating his 1937 theory of digital computing.  Turing was based at Princeton University throughout 1937.  (Source: MacTutor History of Mathematics Archive)

Alan Turing’s viewpoint can be derived from one telling statement in his initial paper.  He wrote, “The behaviour of the computer at any moment is determined by the symbols which he is observing, and his ‘state of mind’ at that moment” [12, p. 250].  To the modern reader the association of “he” with “computer” might sound strange but one must remember that back in the 1930s the term computer referred to a human being who performed computations.  Moreover, the expression “state of mind” referred to distinct states in the course of the computation.  In this sense Turing was developing a precursor to the modern computer.

Tellingly, Turing wrote that “the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares” [12, p. 249].  That “tape” is equivalent to what we refer to as coded instructions, or stored programs today, such as those stored in FORTRAN.  With this in mind, a Turing machine consists of a finite set of quintuples of the form $$p \alpha \beta X q$$.  Here the machine encounters the symbol $$\alpha$$ in state $$p,$$ transforms it into the symbol $$\beta$$ in state $$q,$$ and the machine then moves to a state to the right, left, or same position as the state where it began according to whether $$X$$ is R, L, or N.  Turing called a real number “computable” if such a machine could produce a sequence of binary numbers representing the expansion of that number into 0s and 1s starting with an empty tape.

This whole approach, even as seen in this brief description, appears to be entirely theoretical.  But there was a practical side to Turing as well.  This universal machine provided a model for what we call a “stored program” computer today.  While at Princeton he even designed an electro-mechanical binary multiplier and gained entrance to the graduate-student machine shop in the physics department to try to build the relays himself.  Although he was unable to complete this project before returning to England, once back in Cambridge he was awarded funds to construct a special-purpose analog computer to calculate the zeros of the Riemann zeta-function.  However, World War II broke out and that machine too was never built.

# Alan Turing in America – Cryptography

Author(s):
David Zitarelli (Temple University)

The play Breaking the Code and the movie The Imitation Game popularized Alan Turing’s decisive role in deciphering codes produced by the German encrypting/decrypting machines.  In fact, his interest in cryptography may have been sparked in Princeton when he set out to build the binary-multiplier machine.  In any event, Turing spent the war years at Bletchley Park, a country mansion housing Britain’s leading cryptanalysts.  He was assigned to work with naval communications and, using information supplied by Polish mathematicians, was intimately involved with building machines that could decipher messages sent from the German military.  That project enabled the British Admiralty to defeat German submarine maneuvers aimed at strangling Britain’s shipping routes in the Atlantic.

Not only did Turing pursue his studies on logic and ideas on computing after arriving back in Cambridge, England, but he also published two conventional papers.  However, all of this activity came to a grinding halt shortly after Great Britain declared war on Germany in 1939, whereupon Turing was asked by a British governmental office for help with breaking codes.  German scientists at the Lorenz engineering company, adept at mathematics and its applications, had built a machine called Enigma that automated the processes of coding and decoding messages.  Enigma required the work of only three people: an operator who typed the coded message, a wireless operator who tapped out the enciphered message in Morse code, and a receiving operator who typed the message and handed it to the intended target.  The German Luftwaffe sent thousands of such messages a day, some with top-level plans of action but others of a more mundane nature such as weather reports.

Figure 5. Slate statue of Alan Turing at Bletchley Park with the best-known image of Turing on the wall to the right.  The photographer reported, "Unfortunately, you can't see his coffee cup under his desk."  (Source: Photograph by Jon Callas, San Jose, California, USA. Licensed under CC BY 2.0 via Wikimedia Commons.)

Alan Turing worked in a unit at Bletchley Park called Hut 8, where he was one of four senior codebreakers.  This team soon broke the German code using mathematical and statistical ideas to build their own machine that enabled them to decipher German messages within hours of their transmission.  The British machine was called Bombe, after the name given by a Polish group of cryptanalysts who had first broken the German code.

In response, the German navy developed a highly secure form of Enigma for coordinating efforts by U-boats to locate and then attack convoys carrying food, oil, and other raw materials from the U.S. and Canada.  The resulting embargo was literally starving Britain and some inhabitants began to clamor for surrender.  However, the team-of-four attacked this problem with a vengeance and by June 1941 had decrypted this more difficult code as well.  Jack Copeland, director of the Turing Archive for the History of Computing in New Zealand, described the result of this breakthrough aptly: “The effect was immediate; convoy reroutings based on intelligence from Hut 8 were so successful that the North Atlantic U-boats did not sight a single convoy for 23 days following Turing’s first break” [5, pp. 1540-1541].

Shortly, the team at Bletchley became so overwhelmed with the volume of traffic that they appealed directly to Prime Minister Winston Churchill for permission to hire additional personnel.  The wartime leader immediately instructed his chief of staff, “Make sure they have all they want on extreme priority and report to me that this had been done” [Idem, p. 1540].  With all due speed and diligence a committee was formed to scour universities throughout the country for the most able mathematicians.  One of those recruited to Bletchley Park from Oxford University was 18-year-old Peter Hilton (1923-2010).  When he joined Turing’s group in January 1942 he had completed only a little more than a year of undergraduate studies but, under Turing’s tutelage, Hilton aided the war effort immensely.  Using what he called “cribs” (educated guesses for words), he was able to break a code even harder than the Naval Enigma, one called “Offizer” because the messages were so sensitive that only German officers were permitted to send and receive them instead of the normal operators.

Cat-and-mouse moves and counter-moves by the Lorenz engineering group in Germany and the British office at Bletchley Park continued.  The German firm produced Schlüsselzusatz SZ40, a state-of-the-art, 12-wheel cipher machine for encrypting messages.  The British group worked on this problem from June 1941 to January 1942, when William Tutte (1917-2002), using a method invented by Alan Turing, singlehandedly reconstructed the SZ40 without ever having seen it.  In February 1944 British engineers and mathematicians built the world’s first electrical digital computer, called the Colossus, for automating decryption and thus obviating the need for work to be done by hand.  By the end of the year ten colossi were operational.  One of these machines played a decisive role in the U.S. war effort by providing detailed knowledge of Germany’s preparations in advance of the Allied invasion at Normandy in 1944 that came to be called D-Day.

# Alan Turing in America – 1942–1943

Author(s):
David E. Zitarelli (Temple University)

Alan Turing returned to the U.S. during WWII as a liaison between the two communities of cryptanalysts for about four months, from November 1942 to March 1943.  He arrived in New York City on November 12, 1942, before heading to the headquarters of the U.S. Secret Service (now the CIA) in Washington, D.C.  By that time, officers in the U.S. Navy were concerned that Britain was not sharing details about decoding the Enigma machine.  Turing’s official role was to disclose details to American cryptanalysts but unofficially the British Secret Intelligence Service instructed him to reveal very little.  Commonly known as MI6, this unit’s existence was not officially acknowledged until 1994.  Back in late 1942, the MI6 was especially fearful of leaks by U.S. authorities, mainly because of intrigue between the U.S. Army and U.S. Navy.

So once again Alan Turing was caught in a web of secrecy.  And he played his part perfectly.  (A recent newspaper article contains a fascinating account of Turing’s four-month stay in the U.S. [6].)

Figure 6. Left: The British Secret Intelligence Service (MI6) building in Vauxhall, London (Source: Wikimedia Commons);
Right: American mathematician Claude Shannon (Source: MacTutor History of Mathematics Archive)

Ironically, Turing’s time in Washington inspired some of his best-known work on computers.  During that visit he engaged in a long conversation with Claude Shannon (1916-2001) about building an electronic brain.  This seems to have inspired Turing to engage in experiments on artificial intelligence in the early 1950s.

# Alan Turing in America – Conclusion

Author(s):
David Zitarelli (Temple University)

At the end of the war Alan Turing resumed work on computers, this time for the National Laboratory in London.  By March 1946 he completed a report proposing the design and implementation of an Automated Computing Engine (ACE) but it was regarded as impractical and hence not approved.  He was way ahead of his time!

Turing spent 1947-1948 at Cambridge studying neurology and physiology but at the end of the year accepted a position at Manchester U (the university, not the soccer club, though he himself was an outstanding athlete).  While there he published the paper “Computing machinery and intelligence,” in which he dealt with problems that are central to artificial intelligence today [13].

Sadly Turing’s life changed dramatically in 1952 when he reported an incident to police in which he mentioned his homosexuality.  The end result was that he was charged with violating British homosexuality laws, yet the crime he reported was never pursued.  At his trial he admitted his sexual preferences and stated that he saw nothing wrong with his actions.  Found guilty, he chose estrogen injections instead of prison.  After that he was labeled a security risk and his clearance withdrawn.  Despondent, Alan Turing allegedly bit into a potassium-cyanide laced apple and died just weeks before his 42nd birthday.

Alan Mathison Turing (what an appropriate middle name!) was not the first person in history to conceive of a machine that could perform calculations automatically.  The concept can be traced back to the 1670s, in fact, when the great cofounder of calculus, Gottfried Leibniz, built the so-called Leibniz wheel that could perform all four arithmetic operations.  Some 150 years later Charles Babbage envisioned, but was unable to construct, an “analytical engine” capable of performing operations that arise in mathematical analysis and algebra.  In the U.S. the father-and-son-and-daughter-in-law Lehmers, as well as Howard Aiken at Harvard, built electro-mechanical calculators.  (The Lehmer team consisted of Derrick Norman Lehmer ("DNL"), Derrick Henry "Dick" Lehmer ("DHL"), and Emma Markovna Trotskaia Lehmer.)

But it was Alan Turing, in his seminal paper written in 1936, who realized that a computer could perform tasks far removed from mere numerical computations, a conception way ahead of today’s word processors, spreadsheets, graphics, music, and video.  The main thesis of my account of Turing’s contributions above is that, as one biographer stated, “This generalized conception of the scope of computers is to be found in the vision of a computer as an engine of logic implicit in the abstract theory of computation developed by mathematical logicians” [7, p. 137].

We saw that Turing was involved in constructing a physical model of such a machine both before and after World War II.  Indeed, in 1953, a year before his unfortunate demise, he published a paper that developed abstract properties related to the Riemann Hypothesis and used them on a Mark 1 computer at Manchester to give “a very picturesque account of the first calculations of zeros of $$\zeta(s)$$ ever made by an electronic computer” [9, p. 28].  He harbored “an optimistic hope that a zero would be found off the critical line” $$\sigma = \frac12$$ [14, p. 99].  (See [1] for a description of the method and some recent developments setting this work in historical context.)

Figure 7. Turing statue in Sackville Park, Manchester, England, as photographed in 2004 (Source: Wikimedia Commons)

All along Turing was motivated to build a computer that would emulate, and possibly surpass, the human brain.  As a result of his groundbreaking accomplishments the Association for Computing Machinery (ACM) named its annual prize established in 1966 in his honor; generally the Turing Award is regarded as the Nobel Prize in computer science.  The photo in Figure 7 is of a statue of Turing seated on a bench with the putative ill-fated apple in his right hand.  Dennis A. Hejhal described this 2001 memorial of Turing as “a poignant, life-like, life-size, bronze sculpture [that resides] in a small public park” [9, p. 29] located between the University of Manchester and the nearby “Gay Village” in that city.

# Alan Turing in America – References and About the Author

Author(s):
David E. Zitarelli (Temple University)

### References

[1] Booker, Andrew R., Turing and the Riemann Hypothesis, Notices Amer. Math. Soc. 53 (2006), 1208-1211.

[2] Church, Alonzo, An unsolvable problem of elementary number theory, Amer. J. Math. 58 (1936), 345-363.

[3] Copeland, B. Jack (ed.), The Essential Turing, New York: Oxford Univ. Press, 2004.

[4] Copeland, B. Jack, Colossus: The Secrets of Bletchley Park’s Codebreaking Computers, New York: Oxford Univ. Press, 2006.

[5] Copeland, B. Jack, in Jean Pedersen (ed.), Peter Hilton: Codebreaker and mathematician (1923-2010), Notices Amer. Math. Soc. 58 (2011), 1538-1551.

[6] Cox, David, The imitation game: How Alan Turing played dumb to fool US intelligence, The Guardian, November 28, 2014.  http://www.theguardian.com/science/blog/2014/nov/28/imitation-game-alan-turing-us-intelligence-ian-fleming

[7] Davis, Martin, Mathematical logic and the origin of modern computers, in Esther R. Phillips (ed.), Studies in the History of Mathematics, Washington DC: Math. Assoc. America, 1987, pp. 137-165.

[8] Feferman, Solomon, Turing’s thesis, Notices Amer. Math. Soc. 53 (2006), 1200-1206.

[9] Hejhal, Dennis A., Turing: A bit off the beaten path, The Mathematical Intelligencer 29 (1) (2007), 27-35.

[10] Hodges, Andrew, Alan Turing: The Enigma, New York: Simon and Schuster, 1983.

[11] Leavitt, David, The Man Who Knew Too Much: Alan Turing and the Invention of the Computer, New York: Norton, 2005.

[12] Turing, Alan, On computable numbers with an application to the Entscheidungsproblem, Proc. London Math. Soc. 42 (1937), 230-267.

[13] Turing, A.M., Computing machinery and intelligence, Mind 49 (1950), 433-460.

[14] Turing, A.M., Some calculations on the Riemann zeta function, Proc. London Math. Soc. 3 (3) (1953), 99-117.