In 1936 a twenty-four-year-old English mathematician, Alan Turing, wrote a paper that did not talk about computers, because computers did not yet exist. It talked about a problem in mathematical logic. To solve it, Turing invented an imaginary machine so simple it looks like a toy, and so general that it describes everything a computer will ever be able to do. That machine now bears his name.
The starting problem
In the 1920s the German mathematician David Hilbert had posed a series of questions about the foundations of mathematics. One of them was the Entscheidungsproblem, the "decision problem": is there a mechanical procedure that, given any statement of mathematical logic, can determine in a finite number of steps whether it is provable?
To answer, one first had to clarify something everybody took for granted: what exactly does "mechanical procedure" mean? Turing tackled precisely this question in his paper On Computable Numbers, with an Application to the Entscheidungsproblem.
The Turing machine
Turing started from an observation: what does a person do when carrying out a calculation with pencil and paper, following precise rules? They read a symbol, decide what to do based on what they have read and what they remember, write something, move on. He reduced this behaviour to its essentials.
The components
- A tape, infinite and divided into cells, each of which can hold a symbol or be blank.
- A head that reads and writes one cell at a time and can move left or right.
- A finite number of internal states, representing what the machine "remembers".
- A table of rules: for each combination of current state and symbol read, it says what to write, which way to move and which state to enter.
Nothing else. There are no built-in arithmetic operations, no addressable memory, no complex instructions.
An example
A machine that adds 1 to a binary number written on the tape, starting from the rightmost digit, could have rules like these:
| State | Symbol read | Writes | Move | New state |
|---|---|---|---|---|
| carry | 1 | 0 | left | carry |
| carry | 0 | 1 | stay | done |
| carry | blank | 1 | stay | done |
Starting from 1011, the machine turns the last two 1s into 0s, finds a 0, turns it into a 1 and stops: the result is 1100. It seems like very little, but by combining rules of this kind any calculation can be built.
The universal machine
The deepest idea in the paper is another one. Turing showed that a machine's table of rules can itself be written on the tape as a sequence of symbols. There is therefore a universal machine: a single machine that, by reading on the tape the description of another machine and its data, simulates its behaviour.
Today we take this for granted: the same computer runs a spreadsheet, a browser and a video game, because programs are data loaded into memory. In 1936 it was a conceptual discovery. The distinction between "machine" and "program" became relative: a sufficiently general machine can become any other machine.
The limit: what cannot be computed
With this tool Turing answered Hilbert's question, and the answer was no. He proved that there are well-defined problems that no machine can solve. The best-known example, later formulated as the halting problem, is this: there is no program that, given any other program and its data, always correctly determines whether it will stop or run forever.
The argument is by contradiction. If such a program existed, you could build another one that asks it about itself and then does the opposite of what was predicted: it stops if it was predicted not to stop, and vice versa. The contradiction proves that the original program cannot exist.
Software developers run into the practical consequences of this result. No static analysis tool will ever be able to find with certainty all the infinite loops in an arbitrary program: it can only use approximations, flagging suspicious cases.
Turing and Church
In the same months the American logician Alonzo Church reached the same negative result using a different formalism, the lambda calculus. Turing proved that the two approaches define the same class of computable functions. He then went to Princeton, where he completed his doctorate under Church's supervision. The idea that these equivalent definitions truly capture the intuitive notion of computation is known as the Church-Turing thesis.
The legacy
After the war, during which he worked on codebreaking at Bletchley Park, Turing designed a real computer, the ACE, and in 1950 wrote a famous paper on machine intelligence. He died in 1954. Since 1966 the Association for Computing Machinery has awarded the Turing Award, regarded as the most important honour in computer science.
But his most lasting contribution remains the 1936 one. Whenever we say that a programming language is "Turing-complete", we mean that it can compute everything a Turing machine computes: that is, everything that is computable.
In short
- In 1936 Turing rigorously defined what a mechanical procedure is, using a machine made of tape, head, states and rules.
- The universal machine, which simulates any other machine by reading its description, anticipates the concept of the stored program.
- Turing proved that some problems cannot be solved by any machine, such as the one now known as the halting problem.
- Alonzo Church independently reached the same result with the lambda calculus.
