Máquina de Turing, problema de la parada y tesis de Church-Turing
Turing machine, halting problem and Church-Turing thesis
- Fecha
- 1936 · fiabilidad alta
- Lugar
- Cambridge, Inglaterra
- Autoría
- Alan Turing (On Computable Numbers); Alonzo Church (cálculo lambda, Princeton, 1936, independiente)
- Personas
- 👤 Alan Turing1912–1954
- Ámbito
- Saber y símbolos
⚠️ Dato en discusión: las fuentes no coinciden.
Qué se descubrió
Modelo matemático de máquina que formaliza el concepto de algoritmo, demostración de que no existe procedimiento que decida si un programa se detiene y respuesta negativa al Entscheidungsproblem de Hilbert. Contiene la idea de máquina universal programable.
Church demostró la indecidibilidad meses antes con el cálculo lambda; la tesis de que ambos modelos capturan lo efectivamente calculable lleva el nombre de ambos.
A qué dio paso
- teoría de la computabilidad
- arquitectura de ordenadores de programa almacenado
- teoría de la complejidad
- P vs NP
- inteligencia artificial
Se apoya en
- Paradoja de Russell y Principia Mathematica1901
- Teoremas de incompletitud de Gödel1931
- teoremas de Gödel
- funciones recursivas de Gödel-Herbrand-Kleine
Hizo posible
- FORTRAN, primer lenguaje de alto nivel compilado1957
- ordenador digital de programa almacenado
- compiladores
- criptoanálisis de Bletchley Park