Alan Turing's contributions to computer science

Alan Turing's contributions to computer science fit into five ideas: a precise definition of computing, a proof that some things can never be computed, code breaking at war, an early plan for a stored-program computer, and a test for machine intelligence. The Stanford Encyclopedia of Philosophy says his work "can be regarded as the foundation of computer science and of the artificial intelligence program". This guide takes each idea in plain words, gives you a machine you can run on paper, and notes where people still disagree.

Who Alan Turing was

Alan Mathison Turing was born in London on 23 June 1912. According to the Stanford Encyclopedia's entry on Turing, he studied mathematics at King's College, Cambridge, and became a Fellow there in 1935. That year he learnt of a famous open problem in logic, and by April 1936, working alone, he had an answer. The rest of his short life moved between pure mathematics, wartime code breaking, building computers and, near the end, the mathematics of how living things form patterns.

He died on 7 June 1954 at his home in Wilmslow, aged 41. In 1952 he had been arrested over a relationship with a man and, to avoid prison, made to undergo hormone injections. The Stanford entry says his death was by cyanide poisoning and most likely by his own hand, while noting that some commentators have argued otherwise.

1. The Turing machine: what "computing" means

The problem Turing took on in 1935 was the "decision problem" posed by Hilbert: is there a definite method that can decide, for any mathematical statement, whether it can be proved? To answer, Turing first had to say exactly what a "definite method" is.

His answer was an imaginary machine. The Stanford entry says it was modelled on the teleprinter, with a paper tape that moves both ways and a head that can read, erase and print symbols, and that his analysis began with "a child's exercise book marked off in squares". Each machine follows a fixed table of rules, which the entry calls its "table of behaviour". In modern terms, it says, that table "is equivalent to a computer program".

Then came the big step: a universal machine, one that can read the table of any other machine and do what that machine would do. That is the idea behind every computer you use. Programs are themselves data that other programs can handle.

Five ideas, 1936 to 1950, as the Stanford entry sets them out.

2. The limits: what no machine can do

With a precise idea of computing, Turing could prove a limit on it. Using a "diagonal" argument, he showed there can be no machine that decides, for every machine, whether it will keep printing digits as it should. So the answer to Hilbert's decision problem was no: no general method exists.

The Stanford entry puts the result this way: his 1936 paper gave "a definition of computation and an absolute limitation on what computation could achieve, which makes it the founding work of modern computer science". It also showed that a number can be defined exactly and still be impossible to compute.

3. Enigma and Bletchley Park

After time at Princeton, Turing returned to Britain in 1938. From 1939 to 1945, the entry says, he was "almost totally engaged" in breaking the German Enigma cipher machine and other codes at Bletchley Park. He made "a unique logical contribution" to reading Enigma and became the chief scientific figure there, with particular responsibility for German U-boat messages.

His wartime achievements remained secret, which, the entry says, left him at a disadvantage when he turned to building computers after the war.

4. The stored-program computer and software

From 1945, Turing set out to build his universal machine in electronics. For the National Physical Laboratory in London he wrote a detailed plan for a stored-program computer, in which data and instructions are stored and handled alike. His report of 1946 came after John von Neumann's better-known EDVAC report of 1945; the Stanford entry notes that one writer, Davis, argues von Neumann drew his key insight from Turing's earlier logic.

Turing was also early on software, which he called the "construction of instruction tables". In 1946 he wrote that they "will have to be made up by mathematicians with computing experiences and perhaps a certain puzzle-solving ability". His plans were overshadowed by better-funded American projects, and in 1948 he moved to Manchester University.

5. The imitation game: can machines think?

In October 1950 the journal Mind published his paper "Computing Machinery and Intelligence". In the test it describes, as the Stanford entry summarises it, "A human being and a programmed computer compete to convince an impartial judge, using textual messages alone, as to which is the human being." If the computer wins, it must be credited with intelligence.

Turing's reason was fairness: we judge that other people think only from the outside, so the same should go for machines. He also made a prediction: "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."

The paper is debated to this day. The entry says it "has attracted many critiques", and that Turing's loose wording about a party game has led some writers to read the test in a different way from the one the entry gives.

A worked example: Alan Turing's contributions on paper

The Stanford entry gives the simplest case: a machine that prints the digit 1, moves right, and repeats for ever, so it "computes" the number .1111... Try a slightly bigger one yourself. Draw a row of empty squares and follow this table of behaviour:

1. State A: print 0, move one square right, switch to state B.
2. State B: print 1, move one square right, switch to state A.

Start in state A on the first square. After six steps your tape reads 010101. You have just been the machine: a person following a table with no thought needed, which is exactly what Turing set out to capture. Now ask the question his 1936 paper answers. Could you write one table that looks at any other table and always says whether it will run properly for ever? Turing proved you cannot.

To keep the five ideas and their dates in your head, try the methods in how to remember historical figures and what they did.

Frequently asked questions

What is Alan Turing best known for?

The Turing machine and his 1936 proof of the limits of computing, his code breaking work on Enigma at Bletchley Park, and the imitation game, now often called the Turing test.

Did Alan Turing invent the computer?

Not on his own. His 1936 universal machine is the idea behind the modern computer, and his 1946 plan for a stored-program computer was detailed, but American projects were better funded and von Neumann's EDVAC report came first.

What is the Turing test?

A test from his 1950 paper: a person and a computer each try to convince a judge, by text messages alone, that they are the human. If the computer wins, it must be credited with intelligence.

When was Turing's work recognised?

His 1936 work earned him election as a Fellow of the Royal Society in 1951, while his wartime work remained secret.

Get started

Turing is in Connecting the World, an Advanced course on Learn 100 Influential People, with Zheng He, Columbus, Ada Lovelace and Tim Berners-Lee. Advanced courses cover "modern power, modern physics and the debates still running today". Lessons take about 9 minutes, with questions where you choose, put in order, match, sort and estimate a number, and every lesson lists its sources, as the about page says, "so you can read the original work". You sign in with your email and an emailed sign-in code.