La máquina de Turing es uno de los conceptos más importantes de la informática teórica. Sin embargo, casi no se parece a un ordenador moderno: no tiene pantalla, procesador ni teclado y, en su forma teórica, ni siquiera existe un límite práctico para su memoria.
Imaginada por Alan Turing en 1936, responde a una pregunta mucho más fundamental: ¿qué es la computación?
Para responderla, Turing ideó una máquina deliberadamente mínima, capaz de leer y escribir símbolos en una cinta siguiendo una serie de reglas precisas.
A pesar de su extrema sencillez, el modelo es lo bastante potente como para representar cualquier cálculo que pueda realizarse mediante un algoritmo, según la teoría clásica de la computabilidad.
Por tanto, la máquina de Turing es mucho más que una curiosidad histórica. Permite comprender qué es un algoritmo, qué puede calcular teóricamente un ordenador y, sobre todo, por qué algunos problemas seguirán siendo imposibles de resolver automáticamente, por muy potentes que lleguen a ser las máquinas del futuro.
¿Por qué era necesario definir la computación?
A comienzos del siglo XX, los matemáticos intentaban formalizar los fundamentos de su disciplina.
Una cuestión importante era la existencia de procedimientos sistemáticos capaces de resolver problemas matemáticos.
El matemático alemán David Hilbert formuló, entre otros, el Entscheidungsproblem, o «problema de decisión».
De forma simplificada, la pregunta era: ¿puede concebirse un procedimiento mecánico que permita determinar, para cualquier proposición formulada en un sistema lógico determinado, si puede demostrarse?
Pero esta pregunta esconde otra.
¿Qué significa exactamente «seguir un procedimiento mecánico»?
Hoy hablaríamos naturalmente de un algoritmo ejecutado por un ordenador.
En 1936, sin embargo, el ordenador electrónico programable todavía no existía.
Era necesario, por tanto, definir matemáticamente qué es un procedimiento de cálculo independientemente de cualquier máquina real.
Eso es precisamente lo que hizo Alan Turing.
Para situar este descubrimiento dentro de su trayectoria, la biografía de Alan Turing repasa sus trabajos sobre lógica, su papel durante la Segunda Guerra Mundial y sus contribuciones a los primeros ordenadores.
Una máquina deliberadamente muy sencilla
Una máquina de Turing clásica posee solo unos pocos elementos:
una cinta dividida en casillas;
un conjunto limitado de símbolos;
un cabezal de lectura y escritura;
un conjunto finito de estados;
una tabla de reglas de transición.
En cada etapa, la máquina observa el símbolo situado bajo su cabezal.
Según ese símbolo y su estado actual, una regla le indica qué debe hacer.
Puede:
escribir un símbolo en la casilla actual;
desplazar el cabezal una casilla hacia la izquierda o hacia la derecha;
cambiar de estado;
eventualmente detenerse.
Después, el proceso vuelve a empezar.
Una sucesión de acciones elementales extremadamente simples puede producir así un cálculo complejo.
La cinta: una memoria teóricamente ilimitada
La cinta suele representarse como una larga sucesión de casillas.
Cada casilla puede contener un símbolo perteneciente a un alfabeto definido previamente.
En el modelo teórico clásico, se considera que la cinta es suficientemente grande —a menudo idealmente ilimitada— para que la máquina nunca se quede sin memoria durante el cálculo estudiado.
Esto no significa, evidentemente, que un ordenador real pueda disponer de memoria infinita.
La hipótesis permite separar dos preguntas distintas:
¿es un problema teóricamente computable?
¿disponemos de suficientes recursos físicos para realizar realmente el cálculo?
La máquina de Turing se ocupa principalmente de la primera.
El cabezal de lectura y escritura
El cabezal es la parte activa de la máquina.
Solo examina una casilla de la cinta cada vez.
Puede leer el símbolo presente, sustituirlo eventualmente por otro y después desplazarse.
Esta limitación es deliberada.
La máquina no necesita observar toda la cinta simultáneamente.
Trabaja mediante una sucesión de operaciones locales extremadamente simples.
Precisamente este minimalismo hace que el modelo sea tan interesante: si una máquina tan elemental puede representar cálculos muy complejos, es posible estudiar la computación en sí misma sin depender de la tecnología utilizada para construir un ordenador.
Los estados: la memoria interna de la máquina
Además del contenido de la cinta, la máquina posee un estado actual.
Podemos imaginar estados llamados:
q0, q1, q2, etc.
El estado indica en qué fase del procesamiento se encuentra la máquina.
Una regla podría decir:
Si la máquina está en el estado q0 y lee el símbolo 1, escribe 0, se desplaza hacia la derecha y pasa al estado q1.
Otra regla describirá qué debe hacer cuando se encuentre en q1.
El comportamiento completo de la máquina queda determinado, por tanto, por tres elementos:
estado actual + símbolo leído + regla de transición.
Un ejemplo sencillo: sumar 1 a un número
Utilicemos una representación deliberadamente simple.
Supongamos que un número entero está escrito en unario: el número 4 se representa mediante cuatro símbolos 1.
1111
Queremos construir una máquina que sume 1.
El programa puede ser extremadamente sencillo:
mientras el cabezal lea 1, se desplaza hacia la derecha;
cuando encuentre una casilla vacía, escribe 1;
se detiene.
La cinta pasa a ser:
11111
La máquina acaba de calcular:
4 + 1 = 5
Evidentemente, ningún ordenador moderno realizaría una suma de esta manera.
La eficiencia no es el objetivo.
El ejemplo demuestra que un cálculo puede descomponerse en una sucesión de reglas mecánicas perfectamente determinadas.
¿Es una máquina de Turing un ordenador real?
No en el sentido habitual.
La máquina de Turing es ante todo un objeto matemático.
En 1936, Turing no intentaba proponer el plano industrial de un ordenador que pudiera fabricarse.
Quería disponer de un modelo suficientemente preciso para razonar sobre los procedimientos computables.
Se pueden construir máquinas físicas inspiradas en el modelo con fines pedagógicos, pero ese no era el objetivo original del concepto.
Esta es una diferencia importante respecto a proyectos históricos como la máquina analítica de Charles Babbage, concebida como una verdadera máquina mecánica programable.
De Babbage a Turing: dos maneras de pensar una máquina general
En el siglo XIX, Charles Babbage imaginó con su máquina analítica un dispositivo capaz de realizar distintos cálculos según las instrucciones que recibiera.
Las tarjetas perforadas debían permitir, entre otras cosas, representar operaciones y datos.
Babbage abordaba el problema principalmente como ingeniero e inventor: ¿cómo construir una máquina general capaz de ejecutar distintos cálculos?
Turing planteó una cuestión más abstracta:
¿qué puede hacer, en principio, una máquina de cálculo?
Los dos enfoques son diferentes, pero forman parte de una misma evolución intelectual: separar progresivamente la máquina física de las instrucciones que determinan su comportamiento.
La máquina universal
Una de las ideas más poderosas de Turing es la máquina universal.
Imaginemos varias máquinas de Turing.
La primera realiza una suma.
Una segunda compara dos números.
Una tercera ejecuta otro procedimiento.
A primera vista, cada tarea podría requerir su propia máquina y su propia tabla de reglas.
Sin embargo, Turing demostró que una máquina particular puede recibir en su cinta:
la descripción de otra máquina;
los datos sobre los que debe trabajar esa máquina.
A continuación puede simular el funcionamiento de la máquina descrita.
Esta es la máquina universal de Turing.
Una máquina, muchos programas
Esta idea parece hoy natural porque utilizamos ordenadores de propósito general a diario.
Un mismo ordenador puede:
mostrar una página web;
modificar una fotografía;
ejecutar un videojuego;
procesar un archivo CSV;
compilar código;
reproducir un vídeo.
No reconstruimos físicamente el ordenador para cada tarea.
Cambiamos el programa.
La idea de máquina universal formaliza precisamente esta separación entre el dispositivo capaz de realizar cálculos y la descripción del cálculo que debe ejecutar.
Esta es una de las razones por las que los trabajos de Turing ocupan un lugar tan importante en la historia conceptual del ordenador.
Máquina universal y arquitectura de von Neumann: no son lo mismo
A veces se identifica directamente la máquina universal de Turing con la arquitectura de los ordenadores modernos.
Hay que matizarlo.
La máquina universal de Turing es un modelo matemático que demuestra que una máquina puede simular otras máquinas cuando recibe sus descripciones.
La arquitectura de von Neumann, por su parte, describe una organización práctica de los ordenadores electrónicos en la que instrucciones y datos pueden almacenarse en memoria.
Las dos ideas tienen una evidente relación intelectual: en ambos casos, una misma máquina física puede ejecutar programas diferentes.
Pero responden a objetivos distintos.
Turing estudia la computabilidad.
Von Neumann y los equipos que desarrollaron los primeros ordenadores electrónicos se interesaron, entre otras cuestiones, por su arquitectura y realización práctica.
¿Qué es un problema computable?
Gracias a su modelo, Turing pudo dar un significado preciso a la noción de cálculo.
De forma simplificada, un problema se considera computable si existe una máquina de Turing capaz de producir el resultado esperado siguiendo un número finito de pasos para las entradas correspondientes.
Esta definición transforma una intuición —«seguro que existe un método para resolver este problema»— en una cuestión matemática.
¿Puede construirse un procedimiento preciso?
¿Puede describirse mediante reglas mecánicas?
¿Terminará la máquina produciendo una respuesta?
Estas preguntas están en el centro de la teoría de la computabilidad.
No todos los problemas son computables
Una de las enseñanzas más importantes de Turing resulta contraintuitiva:
existen problemas que ningún algoritmo puede resolver en todos los casos.
No es una limitación temporal debida a los ordenadores de los años treinta.
Tampoco es un problema que vaya a desaparecer simplemente gracias a procesadores más rápidos o a una mayor cantidad de memoria.
Algunas imposibilidades son inherentes a la propia lógica de la computación.
El ejemplo más conocido es el problema de la parada.
El problema de la parada
Imaginemos que queremos crear un programa llamado HALT.
Le proporcionamos:
un programa cualquiera;
los datos suministrados a ese programa.
HALT debe responder a una pregunta:
¿terminará este programa deteniéndose o continuará ejecutándose indefinidamente?
Para algunos programas, la respuesta es sencilla.
mostrar("Hola")terminar
Este se detiene.
Para otro:
mientras verdadero: continuar
este entra deliberadamente en un bucle infinito.
Pero queremos que HALT funcione para absolutamente todos los programas posibles y todas sus entradas.
Turing demostró que tal algoritmo universal no puede existir.
¿Por qué es tan importante el problema de la parada?
El resultado revela un límite fundamental de la automatización.
Podríamos imaginar que, con suficiente potencia informática, una herramienta sería capaz de analizar cualquier programa y predecir perfectamente su comportamiento.
En el caso general, eso es imposible.
Esto no significa que las herramientas de análisis de código sean inútiles.
Pueden detectar muchísimos problemas, reconocer determinados tipos de bucles o demostrar propiedades para categorías concretas de programas.
Pero ninguna herramienta puede resolver perfectamente el problema de la parada para todos los programas posibles.
La diferencia entre «extremadamente difícil» e «imposible en general» es fundamental.
Un límite independiente de la potencia del hardware
Supongamos que los ordenadores se vuelven mil millones de veces más rápidos.
El problema de la parada sigue siendo indecidible.
Supongamos que disponemos de una cantidad gigantesca de memoria.
Sigue siendo indecidible.
Supongamos incluso que contamos con un ordenador ideal sin las limitaciones tecnológicas de nuestras máquinas actuales.
El resultado sigue siendo el mismo.
La teoría de la computabilidad muestra, por tanto, al menos tres tipos de límites en informática:
límites de tiempo;
límites de memoria;
límites de computabilidad.
Los dos primeros se refieren a los recursos necesarios.
El tercero se refiere a la existencia misma de un algoritmo capaz de resolver el problema.
Computabilidad y complejidad: dos preguntas distintas
Estos conceptos se confunden a veces.
La computabilidad pregunta:
¿Existe un algoritmo capaz de resolver este problema?
La complejidad computacional pregunta, en cambio:
Si ese algoritmo existe, ¿cuánto tiempo o memoria necesita?
Por tanto, un problema puede ser perfectamente computable pero extremadamente costoso de resolver.
A la inversa, un problema indecidible simplemente no dispone de un algoritmo general que proporcione siempre la respuesta correcta.
Esta distinción sigue estructurando una gran parte de la informática teórica.
Alonzo Church y el cálculo lambda
Turing no fue el único investigador que trabajó sobre estas cuestiones.
El lógico estadounidense Alonzo Church desarrolló el cálculo lambda, otro formalismo capaz de representar cálculos.
Los enfoques de Church y Turing parecen muy diferentes.
Sin embargo, caracterizan la misma clase de funciones computables.
Esta convergencia es especialmente importante.
Dos modelos desarrollados de manera independiente y basados en principios diferentes conducen a una noción equivalente de lo que puede calcularse.
La tesis de Church-Turing
Esta convergencia dio lugar a lo que hoy se conoce como tesis de Church-Turing.
En forma simplificada:
Todo cálculo realizable mediante un procedimiento efectivo puede ser efectuado por una máquina de Turing.
Conviene ser precisos: se trata de una tesis, no de un teorema matemático ordinario.
¿Por qué?
Porque la expresión «procedimiento efectivo» designa originalmente un concepto intuitivo.
No podemos demostrar matemáticamente que un concepto formal corresponde a todos los métodos intuitivamente imaginables sin haber definido antes formalmente ese concepto intuitivo.
La fuerza de la tesis procede, entre otras cosas, de que numerosos modelos de cálculo desarrollados posteriormente han resultado equivalentes en potencia computacional.
¿Es un ordenador moderno una máquina de Turing?
Un ordenador real no es literalmente una máquina de Turing.
Su memoria es finita.
Su arquitectura es mucho más compleja.
Ejecuta varias capas de software, utiliza procesadores, cachés, periféricos y, en ocasiones, varios núcleos en paralelo.
Sin embargo, para estudiar qué es computable en principio, los ordenadores clásicos de propósito general suelen considerarse equivalentes al modelo de Turing, siempre que dispongan de los recursos necesarios.
En otras palabras, cambiar de procesador o de lenguaje de programación puede hacer que un cálculo sea muchísimo más rápido, pero no permite de repente resolver una clase de problemas que una máquina de Turing no pudiera calcular.
¿Cambia el lenguaje de programación lo que puede calcularse?
Python, Java, C, JavaScript o C++ ofrecen sintaxis y abstracciones muy diferentes.
Algunos lenguajes resultan mucho más prácticos para determinadas tareas.
Pero un lenguaje de programación generalista considerado Turing-completo puede, en teoría y con recursos suficientes, expresar cualquier cálculo realizable por una máquina de Turing.
Eso no significa que todos los lenguajes sean equivalentes en la práctica.
La legibilidad, el rendimiento, las bibliotecas, la seguridad y los ecosistemas cambian enormemente.
La potencia teórica de cálculo es solo una dimensión entre muchas otras.
¿Qué es la completitud de Turing?
Se dice generalmente que un sistema es Turing-completo cuando posee capacidades suficientes para simular una máquina universal de Turing bajo las hipótesis teóricas habituales sobre la memoria disponible.
La expresión aparece a menudo al hablar de:
lenguajes de programación;
determinadas máquinas virtuales;
sistemas de reescritura;
incluso programas o videojuegos en los que los usuarios consiguen construir mecanismos de cálculo.
Ser Turing-completo no significa que un sistema sea rápido, práctico o haya sido diseñado para programar.
Significa esencialmente que posee suficiente capacidad expresiva para representar cálculos generales.
Una máquina extremadamente sencilla puede ser universal
Este es probablemente uno de los aspectos más fascinantes del modelo.
No es necesario disponer de cientos de instrucciones diferentes para obtener una máquina universal.
Variantes extremadamente sencillas de las máquinas de Turing pueden ser suficientes.
Esta observación influyó profundamente en nuestra manera de pensar los ordenadores.
La complejidad del software moderno no procede necesariamente de una infinidad de operaciones fundamentales.
Comportamientos extremadamente sofisticados pueden surgir de la combinación repetida de un pequeño conjunto de operaciones elementales.
Los datos y las instrucciones se convierten en información
En una máquina universal, la descripción de la máquina que debe simularse está representada a su vez mediante símbolos.
En otras palabras, las instrucciones se convierten en datos que la máquina puede leer.
Esta idea es extremadamente importante en la historia de la informática.
También refleja una transformación más general: textos, números, imágenes, programas e instrucciones pueden representarse de formas manipulables por una máquina.
El artículo dedicado a la teoría de la información explora otra faceta de esta abstracción, especialmente la forma en que la información puede medirse y codificarse.
La máquina de Turing no describe el rendimiento de un ordenador
Una confusión frecuente consiste en pensar que el modelo permite comparar directamente el rendimiento de las máquinas.
Ese no es su objetivo principal.
Una máquina de Turing puede realizar un cálculo de forma increíblemente lenta en comparación con un ordenador real.
El modelo trata principalmente de responder a la pregunta:
¿puede este cálculo realizarse mediante un procedimiento algorítmico?
Para saber si una solución es utilizable en la práctica, hay que estudiar después su complejidad, los algoritmos disponibles y la arquitectura real de la máquina.
Computabilidad y rendimiento son, por tanto, dos niveles de análisis diferentes.
¿Y los ordenadores cuánticos?
La informática cuántica se presenta a veces como una tecnología capaz de superar los límites de Turing.
Los ordenadores cuánticos pueden ofrecer ventajas considerables para determinadas categorías de problemas.
Utilizan principios físicos muy diferentes de los ordenadores clásicos.
Pero, dentro del marco teórico estándar, no convierten en computables los problemas que son fundamentalmente no computables en el sentido de Turing.
Pueden cambiar la eficiencia con la que se realizan ciertos cálculos, pero no necesariamente la frontera fundamental entre lo computable y lo no computable.
Esta distinción es esencial cuando se habla de los límites futuros de la informática.
¿Por qué se sigue enseñando la máquina de Turing?
A primera vista, aprender cómo funciona una cinta abstracta en 2026 puede parecer muy alejado del desarrollo de software moderno.
Sin embargo, el modelo permite comprender varias ideas fundamentales:
qué es realmente un algoritmo;
la diferencia entre programa y máquina;
la noción de computación universal;
la existencia de problemas indecidibles;
la diferencia entre computabilidad y complejidad;
los fundamentos teóricos de los lenguajes de programación.
La máquina de Turing desempeña en informática un papel comparable al de ciertos modelos idealizados en física.
Simplifica deliberadamente la realidad para hacer visibles los principios fundamentales.
De la máquina de Turing a los ordenadores modernos
La máquina de Turing de 1936 no es directamente la arquitectura de nuestros ordenadores.
Pero forma parte de una importante evolución intelectual.
En el siglo XIX, Babbage imaginó una máquina mecánica programable.
Las tarjetas perforadas mostraron que instrucciones y datos podían representarse en un soporte externo.
Turing formalizó después la idea de una máquina universal capaz de ejecutar cualquier cálculo algorítmico convenientemente descrito.
En la década de 1940, los primeros ordenadores electrónicos de programa almacenado transformaron progresivamente ideas relacionadas en sistemas físicos.
La arquitectura de von Neumann se convirtió entonces en uno de los modelos más influyentes para organizar de forma práctica procesador, memoria, datos e instrucciones.
Estas etapas no forman una línea recta sencilla y numerosos investigadores contribuyeron a ellas, pero muestran cómo una pregunta abstracta sobre la naturaleza de la computación terminó encontrándose con la construcción de ordenadores.
Un legado todavía presente
Casi noventa años después del artículo de Turing, su modelo sigue ocupando un lugar central en la informática teórica.
Cada vez que nos preguntamos:
si un problema puede automatizarse;
si un programa puede analizar perfectamente todos los demás programas;
si un lenguaje puede expresar cálculos generales;
cuáles son los límites intrínsecos de los algoritmos;
nos encontramos, directa o indirectamente, con las preguntas planteadas por la teoría de la computabilidad.
Los ordenadores han cambiado de manera espectacular.
Los transistores sustituyeron a los dispositivos electromecánicos.
Las memorias contienen miles de millones de bytes.
Las redes conectan miles de millones de máquinas.
Los sistemas de inteligencia artificial procesan volúmenes de datos inimaginables en la época de Turing.
Pero una mayor potencia no elimina los límites matemáticos de la computación.
Ese es quizá el legado más profundo de la máquina de Turing.
Lo esencial
La máquina de Turing es un modelo matemático de la computación propuesto por Alan Turing en 1936.
Se basa en unos pocos elementos sencillos: una cinta, un cabezal de lectura y escritura, símbolos, estados y reglas de transición.
Su sencillez permite aislar lo esencial: un procedimiento algorítmico puede describirse como una sucesión de operaciones mecánicas precisas.
La idea de máquina universal demuestra que una sola máquina puede simular muchas otras cuando recibe sus descripciones como datos. Conceptualmente, esta noción anticipa la separación moderna entre hardware y software.
Pero Turing también demostró que la potencia del cálculo tiene límites fundamentales.
El problema de la parada demuestra que no existe un algoritmo universal capaz de determinar, para todos los programas, si acabarán deteniéndose.
La máquina de Turing nos enseña, por tanto, dos cosas aparentemente opuestas:
una máquina muy sencilla puede realizar una inmensa variedad de cálculos, pero ninguna máquina algorítmica puede calcularlo todo.
Este doble descubrimiento explica por qué sigue siendo uno de los conceptos fundamentales de la informática.
Preguntas frecuentes
¿Quién inventó la máquina de Turing?
El modelo fue propuesto por el matemático británico Alan Turing en su artículo de 1936 On Computable Numbers, with an Application to the Entscheidungsproblem.
¿Llegó a construirse realmente una máquina de Turing?
El concepto original es un modelo matemático, no el plano de un ordenador destinado a fabricarse. Desde entonces se han construido versiones físicas con fines pedagógicos o experimentales.
¿Para qué sirve una máquina de Turing?
Se utiliza principalmente para formalizar la noción de algoritmo y estudiar qué problemas son computables y cuáles no.
¿Qué es una máquina universal de Turing?
Es una máquina de Turing capaz de simular cualquier otra máquina de Turing cuando recibe su descripción y sus datos en una forma adecuada.
¿Qué es el problema de la parada?
Consiste en determinar si un programa dado terminará deteniéndose o continuará indefinidamente. Turing demostró que no existe un algoritmo general capaz de responder correctamente a esta pregunta para todos los programas y todas las entradas.
¿Es un ordenador moderno una máquina de Turing?
No literalmente. Un ordenador real tiene memoria finita y una arquitectura mucho más compleja. Pero, para estudiar la computabilidad, los ordenadores clásicos de propósito general se modelan como sistemas con una potencia de cálculo equivalente a la de una máquina de Turing.
¿Qué significa «Turing-completo»?
Un sistema Turing-completo posee, en teoría, los mecanismos necesarios para simular una máquina universal de Turing, siempre que disponga de suficiente tiempo y memoria.
¿Puede un ordenador cuántico resolver el problema de la parada?
No, dentro de la teoría estándar de la computabilidad. La informática cuántica puede acelerar determinados cálculos, pero no convierte automáticamente en computables los problemas indecidibles según Turing.
Descubre el trabajo de Alan Turing sobre la computabilidad, su papel en Bletchley Park, sus diseños de ordenadores y su contribución fundacional a la inteligencia artificial.
