The story
In 1936 Alan Turing, a young mathematician at King's College, Cambridge, published a paper called 'On Computable Numbers, with an Application to the Entscheidungsproblem'. To answer a question in pure logic, he imagined a simple machine: an endless tape divided into squares, a head that can read and write one symbol at a time and move left or right, and a short table of rules telling it what to do next depending on the symbol it sees and its current state. Turing argued that anything a human clerk could calculate by following fixed rules, such a machine could also calculate.
The question came from the German mathematician David Hilbert, who in 1928 asked whether there was a mechanical procedure that could decide, for any mathematical statement, whether it could be proved. Kurt Gödel had shown in 1931 that any consistent system of arithmetic contains true statements it cannot prove. Turing went further by defining precisely what a mechanical procedure is. He then showed that no machine could decide in general whether another machine would ever halt, so Hilbert's dream was impossible. In America Alonzo Church reached the same answer slightly earlier using a different method, and Turing went to Princeton to study with him.
The paper's deepest idea was the universal machine. Turing showed that a single machine could imitate any other if given a description of that machine on its tape. In other words, the instructions could be treated as data. That is the principle behind every general-purpose computer: one piece of hardware that becomes a word processor, a game or a calculator depending on the program loaded into it.
The Turing machine was never meant to be built, but it gave computer science its foundation. The claim that it captures everything that can be computed, known as the Church-Turing thesis, is still accepted. Computer scientists say a programming language or device is 'Turing complete' if it can do whatever a Turing machine can. Turing himself went on to break German codes at Bletchley Park, design an early computer and pose the question of whether machines can think.
Why it mattered
- Turing's understanding of mechanical procedures fed into codebreaking at Bletchley Park during World War II.
- The universal machine anticipated the stored-program computer design used in nearly all computers.
- Questions about what machines can compute led to the field of artificial intelligence.
- The theory of computation that grew from it produced famous open problems such as P versus NP.
Sources
- Turing Machines Stanford Encyclopedia of Philosophy
- The Church-Turing Thesis Stanford Encyclopedia of Philosophy
- The Rise and Fall of the Entscheidungsproblem Stanford Encyclopedia of Philosophy
- Alan Turing Publishes "On Computable Numbers," Describing What Came to be Called the "Turing Machine" History of Information
Drafted by AI (Claude) from the sources above and checked against them by AI; no historian has reviewed this page. Spot a mistake? Suggest a correction. How pages are made
Community notes
Loading notes…