Alan Turing in America – Logic

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.