Alan Turing

Alan Turing

Alan Mathison Turing (1912–1954)
Personal details
Born	23 June 1912, Maida Vale, London
Died	7 June 1954 (aged 41), Wilmslow, Cheshire
Education	King's College, Cambridge; Princeton University
Work
Fields	Mathematics, logic, cryptanalysis, computing, mathematical biology
Known for	Turing machine, Turing test, Bombe, halting problem
Doctoral advisor	Alonzo Church

Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English mathematician and logician whose work founded theoretical computer science. He gave the first precise definition of what it means for a problem to be computable, led the section at Bletchley Park that broke German naval Enigma traffic during the Second World War, and framed the question of machine intelligence in the form still argued about today.

Turing was born in Maida Vale, London, and read mathematics at King's College, Cambridge, graduating with first-class honours in 1934. He was elected a fellow of King's the following year, at twenty-two, on the strength of a dissertation proving a version of the central limit theorem — unaware that it had already been proved a dozen years earlier.

In 1936 Turing published "On Computable Numbers, with an Application to the Entscheidungsproblem".^[1] David Hilbert had asked whether there exists a definite procedure that, given any mathematical statement, decides whether it follows from the axioms. Answering required a formal account of what a "definite procedure" is.

Turing's answer was a machine, described precisely enough to reason about and simply enough to be obviously mechanical: an endless tape divided into squares, a head that reads and writes one square at a time, and a finite table of rules saying what to do given the current symbol and state. Anything a human clerk could compute by following fixed rules, he argued, such a machine could compute.

Two consequences followed. First, a universal machine can be built: one whose tape holds a description of any other machine, which it then simulates. This is the stored-program principle on which every computer since is built — the recognition that a program is just another kind of data. Second, the halting problem is undecidable: no machine can take an arbitrary program and input and determine in general whether it will eventually stop. The Entscheidungsproblem therefore has no solution.

Alonzo Church had reached an equivalent result months earlier by a different route, the lambda calculus. That two such unlike formalisms define exactly the same class of computable functions is the main evidence for the Church–Turing thesis.

From September 1939 Turing worked at the Government Code and Cypher School at Bletchley Park, heading Hut 8, responsible for German naval cryptanalysis. Building on Polish work, he and Gordon Welchman designed the Bombe, an electromechanical machine that searched Enigma rotor settings for a contradiction, eliminating vast numbers of possibilities at once rather than testing each in turn. The method depended on cribs — guessed fragments of plaintext, such as predictable weather reports.

Naval Enigma was the hardest variant and the one that mattered most for the Battle of the Atlantic. Estimates of the war's shortening by Bletchley's work vary from months to years; the historian Harry Hinsley's estimate of two years is the most frequently cited.^[2] The work stayed secret for three decades, so Turing received no public recognition for it in his lifetime.

In "Computing Machinery and Intelligence" (1950), Turing set aside the question "can machines think?" as too ill-defined to answer, and replaced it with an operational test.^[3] In what he called the imitation game, an interrogator exchanges written messages with a human and a machine, and tries to tell which is which. If the machine cannot reliably be identified, the question of whether it "really" thinks, Turing suggested, has no further content worth arguing about.

I believe that at the end of the century the use of words and general educated opinion will have altered so much that one will be able to speak of machines thinking without expecting to be contradicted.

— Alan Turing, 1950

The paper also answers, in advance, most of the standard objections to machine intelligence, and proposes machine learning — a child machine, educated rather than fully programmed — as the practical route.

Turing's last published work opened an unrelated field. "The Chemical Basis of Morphogenesis" (1952) showed that two chemicals diffusing through a uniform tissue at different rates, while reacting with each other, will spontaneously settle into a stable pattern of stripes or spots. The result explains how an initially uniform embryo can develop structure without any pre-existing map, and reaction–diffusion systems of this kind are still called Turing patterns.

In 1952 Turing was prosecuted for homosexual acts, then criminal in the United Kingdom. He was convicted of gross indecency and, to avoid prison, accepted hormone treatment intended to reduce libido. His security clearance was withdrawn. He died at his home in Wilmslow on 7 June 1954 from cyanide poisoning; the inquest recorded suicide, though the evidence has been disputed since.

The British government issued a formal apology in 2009, and a royal pardon followed in 2013. The 2017 Policing and Crime Act, informally the Alan Turing law, extended pardons to others convicted under the repealed legislation. Turing has appeared on the Bank of England fifty-pound note since 2021.

• Ada Lovelace
• Computer
• Cryptography

1. ^ Turing, A. M. "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society, 1936.
2. ^ Hinsley, F. H. and Stripp, Alan (eds.). Codebreakers: The Inside Story of Bletchley Park. Oxford University Press, 1993.
3. ^ Turing, A. M. "Computing Machinery and Intelligence". Mind, vol. 59, 1950.

• Hodges, Andrew (1983). Alan Turing: The Enigma. Burnett Books.