Cobra Effect · Computing and information
The question no machine can answer
How Alan Turing imagined the computer, and proved some questions have no answer.
7 cards, read aloud in 2:31, with a test and sources.
In the 1930s, mathematicians asked whether every question of logic could be settled by rule.
David Hilbert had posed the challenge, known as the decision problem. Was there a step by step method that could decide, for any statement of logic, whether it could be proved? At Cambridge, a young mathematician named Alan Turing took up the question.
To answer it, Turing imagined the simplest possible computing machine.
It had a long tape divided into squares, and a head that could read and write one symbol at a time. At each step, it followed a short table of rules. He argued that any calculation a person could do by following rules could be done by such a machine.
He also imagined a single machine that could imitate any other.
Given a description of another machine written on its tape, it would do whatever that machine would do. This universal machine is the idea behind every computer that runs many different programs.
Then Turing proved that some questions about machines cannot be answered by any machine.
There is no general method for telling whether a machine will keep producing its digits forever. If there were, it could be turned against itself, leading to a contradiction. So the decision problem had no solution.
His paper was received in May 1936, but he had been beaten into print.
At Princeton, Alonzo Church had just reached the same answer by a different route. Turing added a section showing that their two approaches were equivalent. He then went to Princeton to study with Church.
Later mathematicians recast his result as the halting problem.
Can a program decide, for any program and input, whether it will ever stop? The answer is no, and the name became standard in the 1950s. Turing himself had framed the question differently, and never used the phrase.
So when a problem seems hard, ask whether it might be impossible in principle.
Turing did not just fail to find a method. He proved that no such method could exist. Knowing a limit for certain can be as valuable as solving a problem.
Sources
- Turing Machines, Stanford Encyclopedia of Philosophy. What Turing’s 1936 paper actually proved.
- The Origin of the Turing Halting Problem, Charles Petzold. Why the name halting problem came later.
- On Computable Numbers, with an Application to the Entscheidungsproblem, Alan Turing, 1936. A facsimile of the original paper.
Nearby ideas
- The notes that imagined a computer. How Ada Lovelace's notes on an unbuilt machine imagined what computers could do.
- The man who measured information. How Claude Shannon turned information into something that could be measured in bits.
- The codebreakers who read Enigma. How Polish mathematicians and Bletchley Park broke Germany's Enigma machine.
- The codes that fix their own mistakes. How a frustrated mathematician invented codes that find and fix their own errors.
- The tiny switch that replaced the valve. How a slab of germanium at Bell Labs gave rise to every modern chip.