01Overview
In 1936, answering Hilbert’s decision problem, Turing defined an abstract machine: the tape is divided into cells, a read/write head can read, write and move left or right, and the next action is fixed by the current state and the symbol read. Any function computable by such a machine counted as “computable”.
He also built the universal Turing machine: encode another machine’s description on the tape and it simulates it. That is precisely the theoretical prototype of the stored-program computer. Church gave an equivalent definition with the lambda calculus almost at the same time, and together they support the Church–Turing thesis: anything intuitively computable can be computed by a Turing machine.
02History
- 1936
On Computable Numbers
The Turing machine — and the universal Turing machine — are born.
- 1936
Church introduces the lambda calculus
An equivalent model of computability, built from function abstraction.
- 1945
von Neumann's EDVAC report
Turns the universal Turing machine into a stored-program architecture.
- 1950
The Turing test
Puts an operational definition of intelligence on the table.
03Core concepts
Tape and states
Finite state plus unbounded storage: the smallest model of computation.
Universal Turing machine
A machine that simulates any other — the theoretical prototype of an interpreter.
Church–Turing thesis
Every effectively computable function is computable by a Turing machine; a thesis, not a theorem.
04Hands-on
Do it once — it beats reading it ten times
Write a Turing-machine simulator in under 60 lines and have it add 1 to a binary number
05Self-check
Say it in your own words first, then open the answer. Whatever you cannot explain is what to review next.
Can you explain "Tape and states"?
Finite state plus unbounded storage: the smallest model of computation.
Can you explain "Universal Turing machine"?
A machine that simulates any other — the theoretical prototype of an interpreter.
Can you explain "Church–Turing thesis"?
Every effectively computable function is computable by a Turing machine; a thesis, not a theorem.
What problem did it solve, and why was there nothing better at the time?
Go back to the history section: how was this done before, and what did it cost?
If you had to build it today, how would you break it down?
Use the hands-on task above: write a plan of at most three steps before you start.
06Key people
Alan Turing
1912 – 1954
Turing machine, codebreaking and the Turing test.
Alonzo Church
1903 – 1995
Lambda calculus and computability theory.
07Further reading
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Computing Machinery and Intelligence