VI.94 Alan Turing

b. London, 1912; d. Wilmslow, England, 1954

Logic; computing; cryptography; mathematical biology

In 1936, as a young Fellow of King’s College, Cambridge, Alan Turing made a crucial contribution to mathematical logic: he defined “computability” with what is now called the TURING MACHINES [IV.20 §1.1]. Although mathematically equivalent to a definition of effective calculability earlier given by CHURCH [VI.89], Turing’s concept was compelling because of his entirely original philosophical analysis. It won the endorsement of Church, and indeed also of GÖDEL [VI.92], whose 1931 INCOMPLETENESS THEOREM [V.15] underlay Turing’s investigation. Using his definition, Turing showed that first-order logic was undecidable, and thus dealt the final death blow to HILBERT’s [VI.63] formalist program. (See LOGIC AND MODEL THEORY [IV.23 §2] for more details.)

Computability is now fundamental in mathematics, in that it gives an exact meaning to the question of whether a method exists to solve a problem. As an illustration, HILBERT’S TENTH PROBLEM [V.20], on the general solubility of Diophantine equations, was completely resolved in 1970 by methods connected with Turing’s ideas. Turing himself pioneered extensions of his definition in mathematical logic, and applications of it in algebra. However, he was unusual as a mathematician in that he explored not only the mathematical uses of his ideas (in questions of decidability in algebra) but also the wider implications for philosophy, science, and engineering.

One factor in Turing’s breakthrough was his fascination with the problem of mind and matter. Turing’s analysis of mental states and operations has since become a point of departure for the cognitive sciences. Turing himself blazed this trail later by his advocacy of the possibility of artificial intelligence. His famous 1950 “Turing test” was part of an extensive range of research proposals in this field.

A more immediately applicable aspect of his 1936 work lay in his observation that a single “universal” machine could do the work of any Turing machine, by reading the description of that machine as a table of instructions. This is the essential principle of the modern digital computer, whose programs are themselves data structures. In 1945 Turing used this insight to plan a first electronic computer and its programming. He was preempted by VON NEUMANN [VI.91], but it can be argued that von Neumann had used Turing’s insight that computing must be primarily an application of logic. Thus, Turing laid the foundations of modern computer science.

Turing was able to bridge theory and practice because between 1938 and 1945 he was the chief scientific figure in British cryptography, with particular responsibility for decrypting German naval signals. His main contributions lay in a brilliant logical solution of the Enigma cipher, and in Bayesian information theory. The advanced electronics employed in British code breaking gave him the experience to become a pioneer of practical computing as well.

Turing had less success in postwar computer engineering, and increasingly withdrew from attempts to influence the course of computer development. Instead, at Manchester University after 1949 he concentrated on a theory of nonlinear partial differential equations applied to biological development. Like his 1936 work, this opened an entirely new field. It also illustrated his broad mathematical scope, which included important work on the RIEMANN ZETA FUNCTION [IV.2 §3]. He was busy working on biological theory and new ideas in physics at the time of his sudden death.

Turing’s short life combined the purest mathematics and the most practical applications. It was also marked by other contrasts. Although he promoted the theme of computer-based artificial intelligence, there was nothing mechanical about his thought or life. The wit and drama of the “Turing test” have made him a lasting figure in the popularization of mathematical ideas. The dramatization of his life, drawing on the extraordinary secrecy of his war work, and his subsequent persecution as a homosexual, have also attracted great public interest.

Further Reading

Hodges, A. 1983. Alan Turing: The Enigma. New York: Simon & Schuster.

Turing, A. M. 1992–2001. The Collected Works of A. M. Turing. Amsterdam: Elsevier.

Andrew Hodges