Alan Turing
Is there anything a machine cannot compute?
That time, that place
Even after Gödel dismantled Hilbert's program, one question remained.
Is there a procedure that decides whether a mathematical statement is true or false by following rules alone, without thinking? Hilbert called it the decision problem.
Why this question
To answer it, something had to be settled first: what is a rule-following procedure?
Turing watched how a person computes with paper and pencil and stripped it to the bone. A long tape divided into squares. A device that reads and writes one square and moves one square left or right. A finite table of rules. And a marker for the current state.
That is all.
What was found
This simple machine can perform any calculation a person can do with paper and pencil.
And here is the decisive step: the machine's own table of rules can be encoded as symbols on the tape. Then a machine can read that table and imitate the machine it describes. One machine that can become any machine — the concept of what we now call a computer.
Then he exhibited a problem this machine cannot solve: no program can decide, in advance, whether an arbitrary program will eventually halt or run forever. The same self-reference Gödel had used.
The answer to Hilbert's question was no.
A clever enough procedure could decide anything
The halting proof, driving a contradiction out of self-reference
During the war he broke German ciphers at Bletchley Park. In 1952 he was convicted for homosexuality and chemically castrated, and died two years later. The British government apologized in 2009; a royal pardon came in 2013