On Computable Numbers
Etapa 1 · Los fundamentos (1763–1942) › Computabilidad
- Linaje
- Símbolos y lógica
- Tipo
- Publicación
Quién
King's College de Cambridge
Qué ocurrió
Alan Turing, de 24 años, publica «On Computable Numbers, with an Application to the Entscheidungsproblem» en los Proceedings of the London Mathematical Society, en dos fascículos fechados el 30 de noviembre y el 23 de diciembre de 1936.
Qué aportó
La máquina de Turing y la máquina universal, que ejecuta cualquier otra a partir de su descripción: el modelo teórico del computador de programa almacenado. Llega al mismo resultado que Church por otro camino.
Desarrollo
Alan Turing tenía 22 años cuando, en 1935, oyó en Cambridge las clases de Max Newman sobre los fundamentos de las matemáticas. Newman describió el problema de la decisión como la búsqueda de un «proceso mecánico». Turing se tomó la expresión al pie de la letra y se preguntó qué hace exactamente una persona cuando calcula siguiendo reglas.
Su respuesta es una máquina imaginaria. Lee y escribe símbolos en una cinta dividida en casillas, de uno en uno, y en cada paso decide qué escribir, hacia dónde moverse y en qué estado quedar según el símbolo que ve y su estado actual. Turing argumentó que cualquier cálculo que haga una persona con lápiz y papel lo puede hacer una de estas máquinas. Después mostró algo más sorprendente: una sola máquina, la universal, puede imitar a cualquier otra si recibe en la cinta la descripción de esa otra. Programa y datos son la misma clase de cosa.
Con ese modelo demostró que ninguna máquina puede decidir, para cualquier otra, si seguirá escribiendo cifras sin fin, y de ahí que el problema de la decisión de Hilbert no tiene solución. Hoy el resultado se enseña como el problema de la parada, un nombre que le dio Martin Davis en los años cincuenta. Mientras preparaba el artículo supo que Church había llegado a lo mismo con el cálculo lambda, y añadió un apéndice que prueba que las dos definiciones son equivalentes.
Ese otoño, en Nueva York, Emil Post publicó por su cuenta un modelo casi idéntico. Church, en su reseña de 1937, llamó al de Turing «máquina de Turing». Turing pasó de 1936 a 1938 en Princeton estudiando con él. Su máquina universal, que guarda en la misma cinta el programa y los datos, es el modelo teórico del computador de programa almacenado.
Una fila de casillas con ceros y unos; debajo de una de ellas, un cabezal en el estado q₁; abajo, una regla de ejemplo de la tabla.
Nivel técnico
Una máquina de Turing tiene una cinta dividida en casillas, un cabezal que lee una casilla cada vez y un número finito de estados. Su tabla dice, para cada estado y cada símbolo leído, qué escribir, si moverse a la izquierda o a la derecha y a qué estado pasar.
La máquina universal recibe en la cinta la tabla de otra máquina, escrita como una cadena de símbolos, y la imita paso a paso. Para demostrar que el problema de la decisión no tiene solución, Turing supone que existe una máquina que decide si cualquier otra se comporta bien y construye, con ella, una máquina que se contradice: un argumento diagonal como el de Cantor.
En comparación
| Rasgo | Church | Turing | Post |
|---|---|---|---|
| Modelo | Funciones del cálculo lambda | Máquina con cinta, cabezal y estados | Trabajador que marca casillas |
| Publicación | American Journal of Mathematics, abril | Proceedings of the London Mathematical Society, noviembre y diciembre | Journal of Symbolic Logic, septiembre |
| Lugar | Princeton | Cambridge | Nueva York |
| Respuesta al problema de la decisión | No tiene solución | No tiene solución | Sin aplicación en el artículo |
Malentendidos frecuentes
Se suele decir: La máquina de Turing es un aparato que Turing construyó.
En realidad: Es un modelo matemático, una máquina imaginaria para definir qué es calcular. Turing no la construyó, aunque después diseñó computadores reales, como el ACE.
Vídeos
- 1966: Alan Turing's Machines | Mathematics in Action | BBC Archive (se abre en una pestaña nueva) (BBC Archive · en inglés)
Viene de
El Entscheidungsproblem (1928)
Influencia directa documentada
Ambos artículos responden al Entscheidungsproblem; el de Turing lo nombra en el título
Cálculo lambda y problema irresoluble (abril de 1936)
Convergencia independiente
Mismo resultado por vías independientes
Teoremas de incompletitud (1931)
Influencia directa documentada
Turing compara su resultado con el teorema de Gödel y explica en qué se diferencia (apartado 8)
Finite Combinatory Processes (septiembre de 1936)
Convergencia independiente
Dos modelos casi idénticos de cálculo mecánico, escritos por separado; una nota del artículo de Post invita a compararlo con el de Turing y aclara que se escribió de forma independiente
Lleva a
Neurona de McCulloch y Pitts (diciembre de 1943)
Influencia directa documentada
El artículo sostiene que una red con cinta y medios para leerla y escribirla calcula lo mismo que una máquina de Turing
Hilos que pasan por aquí
- De la pregunta de Hilbert a la máquina universal (paso 7 de 7)
Bibliografía
Fuente original
- On Computable Numbers, with an Application to the Entscheidungsproblem (Proceedings of the London Mathematical Society, serie 2, vol. 42, págs. 230-265) (se abre en una pestaña nueva). Alan M. Turing, 1936
- Finite Combinatory Processes. Formulation 1 (The Journal of Symbolic Logic, vol. 1, n.º 3, págs. 103-105) (se abre en una pestaña nueva). Emil L. Post, 1936
Estudios y contexto
Cómo citar
«On Computable Numbers». En La historia de la IA, revisión del 13 de noviembre de 2026. https://thehistoryofai.com/es/hito/turing-numeros-computables
Última revisión de esta ficha: 13 de noviembre de 2026.