Turing, Alan Mathison

views updated

TURING, ALAN MATHISON

(b. London, England, 23 June 1912; d. Wilmslow, England, 7 June 1954)

mathematics, mathematical logic, computer technology.

Turing was the son of Julius Mathias Turing and Ethel Sara Stoney. After attending Sherborne School he entered King’s College, Cambridge, in 1931. He was elected a fellow of the college in 1935 for his dissertation “On the Gaussian Error Function,” which won a Smith’s prize in the following year. From 1936 until 1938 Turing worked at Princeton University with Alonzo Church.

While at Princeton Turing published one of his most important contributions to mathematical logic, his 1937 paper “On Computable Numbers, With an Application to the Entscheidungsproblem,” which immediately attracted general attention. In it he analyzed the processes that can be carried out in computing a number to arrive at a concept of a theoretical “universal” computing machine (the “Turing machine”), capable of operating upon any “computable” sequence–that is, any sequence of zeros and ones. The paper included Turing’s proof that Hilbert’s Entscheidungsproblem is not solvable by these means. Church had, somewhat earlier, solved Hilbert’s problem by employing a ? -definable function as a precise form of the intuitive notion of effectively calculable function, while in 1936, S. C. Kleene had proved the equivalence of ? -definability and the Herbrand-Gödel theory of general recursiveness. In his “Computability and ?-Definability” of 1937, Turing demonstrated that his and Church’s of 1937, Turing demonstrated that his and Church’s ides were equivalent.

In 1939 Turing published “Systems of Logic Based on Ordinals,” in which he examined the question of constructing to any ordinal number ? a logic L?, such that any problem could be solved within some L?. This paper had a far-reaching influence; in 1942 E. L. Post drew upon it for one of his theories for classifying unsolvable problems, while in 1958 G. Kreisel suggested the use of ordinal logics in characterizing informal methods of proof. In the latter year S. Feferman also adapted Turing’s ideas to use ordinal logics in predicative mathematics.

In 1939 Turing returned to King’s College, where his fellowship was renewed. His research was interrupted by World War II, however, and from the latter part of 1939 until 1948 he was employed in the communications department of the Foreign Office; he was awarded the O.B.E. for his work there. After the war, he declined the offer of a lectureship at Cambridge and, in autumn of 1945, joined the staff of the National Physical Laboratory to work on the design of an automatic computing engine (ACE).

In 1948 Turing became a reader in the University of Manchester and assistant director of the Manchester automatic digital machine (MADAM). He also continued to work in mathematical theory, and improved E. L. Post’s demonstration of the existence of a semigroup with unsolvable word problem by exhibiting a semigroup with cancellation for which the word problem is (recursively) unsolvable. He made further contributions to group theory and performed calculations on the Riemann zeta-function in which he incorporated his practical work on computing machines.

In 1950 Turing took up the question of the ability of a machine to think, a subject that had gained general interest with the increasing application of mechanical computing devices to more and more complex tasks. His “Computing Machinery and Intelligence“was addressed to a broad audience and marked by a lively style. The Programmer’s Handbook for the Manchester Electronic Computer, Produced under his direction, was published in the same year.

Throughout his life Turing was also interested in applying mathematical and mechanical theory to the biological problem of life forms. He made a promising approach to this question in his 1952 publication “The Chemical Basis of Morphogenesis.” In this work he exploited the mathematical demonstration that small variations in the initial conditions of first-order systems of differential equations may result in appreciable deviations in the asymptotic behavior of their solutions to posit that unknown functions might function biologically as form-producers; he was thus able to account for asymmetry in both mathematical and biological form. He was at work on a general theory when he died of perhaps accidental poisoning.

BIBLIOGRAPHY

I. Original Works. An edition of Turing’s collected works is in preparation by Professor Dr. R. O. Gandy. See especially Turing’s “On Computable Numbers, With an Application to the Entscheidungsproblem,“in Proceedings of the London Mathematical Society, 42 (1937), 230–265; “On Computable Numbers, With an Application to the Entscheidungsproblem. A Correction,“ibid43 (1937), 544–547; “Computability and ?-Definability,“in Journal of Symbolic Logic, 2 (1937), 153–163; “Systems of Logic Based on Ordinals,“in Proceedings of the London Mathematical Society, 45 (1939), 161–228; “The Word Problem in Semigroups With Cancellation,“in Annals of Mathematics, 52 (1950), 491-505; “Computing Machinery and Intelligence,“in Mind, 59 (1950), 433–460, repr. as “Can a Machine Think?“in J. R. Newman, The World of Mathematics, IV (New York, 1956), 2099–2133; and “The Chemical Basis of Morphogenesis,“in Philosophical Transactions of the Royal Society237 (1952), 37–72.

II. Secondary Literature. S. Turing, Alan M. Turing (Cambridge 1959), includes a bibliography of works by and about Turing. See also M. Davis, Computability and Unsolvability (New York, 1958); S. Feferman, “Ordinal Logics Re-examined,” in Journal of Symbolic Logic, 23 (1958), 105; “On the Strength of Oridinal Logics,” ibid., 105–106: “Transfinite Recursive Progressions of Axiomatic Theories,“ibid., 27 (1962), 259-316; and “Autonomous Transfinite Transfinite Progressions and the Extent of Predicative Mathematics,” in B. van Rootselaar and J. F. Staal, eds., Logic, Methodology and Philosophy of Science, III (Amsterdam, 1968), 121–135; S. C. Kleene, Introduction to Metamathematics (Amsterdam–Groningen, 1952); and Mathematical Logic (New York, 1967); G. Kreisel, “Ordinal Logics and the Characterization of Informal Concepts of Proof,” in Proceedigns of the International Congress of Mathematicians, 1958 (Cambridge, 1960), 289–299; and M. H. A. Newman, “Alan Mathison Turing,” in Biographical Memoris of Fellows of the Royal Society 1955, I (London, 1955), 253–263, which also has a bibliography.

B. van Rootselaar

More From encyclopedia.com