Turing machine, halting problem and Church-Turing thesis
Máquina de Turing, problema de la parada y tesis de Church-Turing
- Date
- 1936 · confidence high
- Place
- Cambridge, England
- Credited to
- Alan Turing (On Computable Numbers); Alonzo Church (lambda calculus, Princeton, 1936, independent)
- People
- 👤 Alan Turing1912–1954
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
A mathematical model of a machine that formalises the concept of algorithm, a proof that no procedure exists to decide whether a program halts, and a negative answer to Hilbert's Entscheidungsproblem. It contains the idea of a programmable universal machine.
Church had proved undecidability months earlier using the lambda calculus; the thesis that both models capture what is effectively computable bears both their names.
What it led to
- computability theory
- stored-program computer architecture
- complexity theory
- P versus NP
- artificial intelligence
Built on
- Russell paradox and Principia Mathematica1901
- Gödel incompleteness theorems1931
- Gödel's theorems
- Gödel-Herbrand-Kleene recursive functions
Made possible
- FORTRAN programming language1957
- stored-program digital computer
- compilers
- Bletchley Park cryptanalysis