Alan Turing

Overview

Turing's 1936 paper introduced an abstract machine that reads and writes symbols on a tape according to a finite table of rules, and argued that anything a human could compute by following a fixed procedure could be computed by such a machine. He then showed that no machine can decide, for an arbitrary machine and input, whether it will eventually halt, and used this to answer Hilbert's decision problem in the negative: there is no algorithm that settles which statements of first-order logic are provable. The same paper describes a universal machine that can simulate any other given its description, which is the idea behind the stored-program computer. During the war he worked on breaking German ciphers at Bletchley Park. In 1950 he proposed replacing the question of whether machines think with a test based on imitation. He was prosecuted in 1952 for homosexual acts and died in 1954. Start with the first three sections of the 1936 paper, then the 1950 essay, which needs no mathematics.

Where to start reading

• On Computable Numbers, with an Application to the Entscheidungsproblem 1936

  Defines the Turing machine, proves the halting problem undecidable, and settles the decision problem for first-order logic in the negative.

• Computing Machinery and Intelligence 1950

  Proposes the imitation game as a replacement for the question of whether machines can think, and answers the standard objections one by one.

Part of

• Formalism and the Hilbert programme

Sources

1. Alan Turing MacTutor History of Mathematics
2. Alan Turing Wikipedia
3. Turing Machines Stanford Encyclopedia of Philosophy