The Idea of a Programmable Computer
Turing in 1936: What Can Be Computed?
Explain universal computation and recognize that not every problem has an algorithmic solution.
In this lesson
Lesson goals
Explain universal computation and recognize that not every problem has an algorithmic solution.
The idea explained
Turing’s paper models computation through a machine that reads and writes symbols according to rules and internal state. It is a mathematical model, not a specific electronic product. A universal machine can simulate such machines when given their descriptions, making an encoded procedure itself processable. Turing used this framework to investigate the limits of computation, not to promise a solution to every question.
Dates and milestones
- 1936–1937: The original “On Computable Numbers” paper, conventionally associated with 1936.
Why was this a turning point?
Computation and its limits could be studied independently of a particular physical mechanism.
Activity: try before reading the answer
Apply this rule: read 0, write 1, move right, stop at a blank. What happens to 000?
Answer and explanation
It becomes 111 and the process stops. This practices precise procedural description; it does not itself establish universality.