Máquina de Turing (concepto de computación universal)
Turing machine (universal computation)
- Fecha
- 1936 · fiabilidad alta
- Lugar
- Cambridge, Inglaterra (King's College)
- Autoría
- Alan Turing ('On Computable Numbers', 1936); Alonzo Church (cálculo lambda, Princeton, 1936)
- Personas
- 👤 Alan Turing1912–1954
- Ámbito
- Saber y símbolos
Qué se descubrió
Modelo matemático abstracto de una máquina que lee y escribe símbolos en una cinta según una tabla de reglas, y prueba de que existe una máquina universal capaz de simular a cualquier otra. Definió qué es computable.
A qué dio paso
- Fundamento teórico de la computadora de programa almacenado
- Ciencia de la computación como disciplina
- Inteligencia artificial (test de Turing, 1950)
Se apoya en
- Álgebra de Boole1847-1854
- Los 23 problemas de Hilbert8 de agosto de 1900
- Teoremas de incompletitud de Gödel1931
- Problema de la decisión de Hilbert
Hizo posible
- Colossus1943–1944
- Arquitectura de programa almacenado (von Neumann)1945
- Automatic Computing Engine1945
- Cibernética1948
- Test de Turing y la idea de la inteligencia artificial1950
- Expresión regular1951
- Jerarquía de Chomsky1956
- Complejidad algorítmica (Kolmogórov-Solomonoff-Chaitin)1965
- NP-completitud (teorema de Cook-Levin) y problema P vs NP1971
- Arquitectura von Neumann
- ACE (Turing, 1945)
- Teoría de la complejidad