Qué es la Máquina de Turing: definición, historia y ejemplos

Máquina de Turing: definición, historia desde Alan Turing, ejemplos y su impacto en la computación. Explicación clara y accesible para estudiantes y curiosos.

Máquina de Turing es un término de la informática. Una máquina de Turing es un modelo abstracto de cálculo formado por un conjunto de reglas, estados y transiciones, más que una máquina real. Fue descrita por primera vez en 1936 por el matemático e informático inglés Alan Turing. Una máquina de Turing tiene dos objetivos fundamentales: decidir lenguajes formales y calcular o resolver funciones matemáticas. Las máquinas de Turing son uno de los modelos formales más importantes en el estudio de la informática teórica y de la computabilidad.

Definición informal

De forma intuitiva, una máquina de Turing consta de:

• Una cinta infinita dividida en celdas que actúan como memoria (cada celda contiene un símbolo de un alfabeto finito o un símbolo en blanco).
• Una cabeza lectora/escritora que puede moverse a la izquierda o a la derecha, leer el símbolo actual y escribir un nuevo símbolo.
• Un conjunto finito de estados y una función de transición que, según el estado actual y el símbolo leído, indica qué escribir, hacia dónde mover la cabeza y cuál será el siguiente estado.
• Estados especiales de inicio y de aceptación/rechazo que determinan si la máquina acepta una entrada o termina con un resultado.

Definición formal (resumen)

Formalmente se suele definir una máquina de Turing determinista como una 7-tupla (Q, Σ, Γ, δ, q0, q_accept, q_reject), donde:

• Q es el conjunto finito de estados.
• Σ es el alfabeto de entrada (símbolos permitidos en la entrada).
• Γ es el alfabeto de la cinta (incluye Σ y un símbolo en blanco).
• δ: Q × Γ → Q × Γ × {L, R} es la función de transición.
• q0 ∈ Q es el estado inicial.
• q_accept ∈ Q y q_reject ∈ Q son los estados de aceptación y rechazo (q_accept ≠ q_reject).

Cómo funciona (pasos básicos)

• Se coloca la cadena de entrada en la cinta y la cabeza se sitúa en la primera celda de la entrada.
• En cada paso la máquina lee el símbolo bajo la cabeza, consulta δ para decidir qué escribir, en qué dirección moverse (L o R) y cuál será el siguiente estado.
• Si la máquina llega a q_accept se dice que acepta la entrada; si llega a q_reject o nunca cambia de estado de forma que siga avanzando según las reglas, se rechaza o no termina según el caso.

Tipos importantes de máquinas de Turing

• Deterministas: la función de transición da a lo sumo una acción para cada par (estado, símbolo).
• No deterministas: pueden existir varias transiciones posibles; se acepta si alguna rama conduce a aceptación. Teóricamente pueden ser más compactas, pero en potencia calculadora son equivalentes a las deterministas.
• Multicinta: usan varias cintas independientes; son más prácticas para describir algoritmos, aunque no aumentan la clase de funciones computables (solo la eficiencia).
• Máquina de Turing Universal: puede simular cualquier otra máquina de Turing tomando la descripción de la máquina y su entrada como datos en la cinta. Es la idea formal de un ordenador programable.

Ejemplos sencillos

A continuación, dos ejemplos informales que ayudan a entender su uso:

• Reconocer el lenguaje a^n b^n (cadenas con n veces 'a' seguidas de n veces 'b'): una máquina de Turing puede marcar la primera 'a' sin marcar y buscar la última 'b' sin marcar, sustituirlas por un símbolo marcado, y repetir el proceso. Si al terminar todas las 'a' y 'b' han sido emparejadas y no hay símbolos extra, acepta; si encuentra un desajuste, rechaza.
• Suma en unary (añadir 1): si la entrada es "111" (representando el número 3), una máquina simple puede desplazarse al final de la cadena y escribir otro '1', devolviendo "1111" como resultado. Este ejemplo ilustra cómo una máquina puede calcular una función transformando la cinta.

Historia y contexto

Alan Turing presentó el modelo en 1936 en su artículo "On Computable Numbers, with an Application to the Entscheidungsproblem". Su objetivo era formalizar la noción de algoritmo y de cálculo efectivo para abordar problemas como el Entscheidungsproblem de Hilbert. El modelo de Turing resultó fundamental para la teoría de la computación y, junto con trabajos de Church y otros, llevó a la formulación de la Tesis de Church–Turing, que sostiene que cualquier cálculo que pueda realizarse por un procedimiento efectivo puede ser realizado por una máquina de Turing.

Importancia y consecuencias

• Las máquinas de Turing definen formalmente qué problemas son decidibles (existe una máquina que siempre termina y responde sí/no) y cuáles son indecidibles.
• El problema de la parada (halting problem) es indecidible: no existe una máquina de Turing que, dada la descripción de otra máquina y su entrada, determine en todos los casos si esa máquina se detendrá.
• Son la base teórica para la complejidad computacional (clases como P, NP, PSPACE se definen en relación con modelos tipo Turing) y para comprender límites y costes de cómputo.

Aplicaciones y límites

Aunque una máquina de Turing es un objeto abstracto y no un ordenador físico, el concepto sirve para:

• Probar la (in)decidibilidad de problemas matemáticos y lógicos.
• Formalizar algoritmos y estudiar su complejidad temporal y espacial.
• Modelar la idea de un ordenador programable mediante la máquina universal.

Como límite fundamental, existen problemas que ninguna máquina de Turing puede resolver en general (por ejemplo, el problema de la parada), lo que fija fronteras teóricas sobre lo que es computable.

Conclusión

Una Máquina de Turing no es una máquina física, sino un modelo formal esencial que captura la esencia del cálculo paso a paso. Gracias a ella se pueden clasificar problemas según su computabilidad, entender la noción de algoritmo y fundamentar gran parte de la teoría de la computación moderna.

Búsqueda por letra