La historia de la IA

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.

La máquina lee una casilla, consulta su tabla de reglas según el estado en que está, escribe, se mueve y cambia de estado.

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

Tres definiciones de cálculo mecánico (1936)
RasgoChurchTuringPost
ModeloFunciones del cálculo lambdaMáquina con cinta, cabezal y estadosTrabajador que marca casillas
PublicaciónAmerican Journal of Mathematics, abrilProceedings of the London Mathematical Society, noviembre y diciembreJournal of Symbolic Logic, septiembre
LugarPrincetonCambridgeNueva York
Respuesta al problema de la decisiónNo tiene soluciónNo tiene soluciónSin 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

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í

Bibliografía

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.

Abrir en la cronología interactiva