Turing machine (universal computation)
Máquina de Turing (concepto de computación universal)
- Date
- 1936 · confidence high
- Place
- Cambridge, England (King's College)
- Credited to
- Alan Turing ('On Computable Numbers', 1936); Alonzo Church (lambda calculus, Princeton, 1936)
- People
- 👤 Alan Turing1912–1954
- Field
- Knowledge & symbols
What was discovered
Abstract mathematical model of a machine that reads and writes symbols on a tape according to a table of rules, and proof that there exists a universal machine capable of simulating any other. It defined what is computable.
What it led to
- Theoretical foundation of the stored-program computer
- Computer science as a discipline
- Artificial intelligence (Turing test, 1950)
Built on
- Boolean algebra1847-1854
- Hilbert 23 problems8 de agosto de 1900
- Gödel incompleteness theorems1931
- Hilbert's decision problem
Made possible
- Colossus computer1943–1944
- Stored-program (von Neumann) architecture1945
- Automatic Computing Engine1945
- Cybernetics1948
- Turing test and the idea of machine intelligence1950
- Regular expression1951
- Chomsky hierarchy1956
- Kolmogorov complexity1965
- NP-completeness (Cook-Levin) and P vs NP1971
- Von Neumann architecture
- ACE (Turing, 1945)
- Complexity theory