GUÍA 26-08-26 Teoría de la Computación

NE111 · miércoles 26/08/2026 · 16:00-17:15 · Sesión 6

Variantes de máquinas de Turing · La máquina universal

VARIANTES

• Multicinta — varias cintas con cabezas independientes.
• Cinta infinita en ambas direcciones.
• No determinista — δ devuelve un conjunto de transiciones posibles.
• Multidimensional — la cinta es un plano en lugar de una línea.
• Con varias cabezas sobre la misma cinta.

TODAS SON EQUIVALENTES EN PODER

Cada variante se puede simular con la máquina básica. Ninguna reconoce más lenguajes. Lo que cambia es la eficiencia, no lo computable.

• Una MT de k cintas que corre en tiempo t se simula en una sola cinta en O(t²).
• Una MT no determinista que corre en tiempo t se simula deterministamente en tiempo exponencial. Esa brecha es exactamente el problema P contra NP que veremos en el siguiente bloque.

POR QUÉ IMPORTA LA ROBUSTEZ DEL MODELO

Que tantas variantes distintas resulten equivalentes es evidencia fuerte de que el modelo capta algo real y no un accidente de su definición. Es el argumento principal a favor de la tesis de Church-Turing.

CODIFICACIÓN DE UNA MÁQUINA

Toda MT se puede describir con una cadena finita: se numeran estados y símbolos y se escribe la tabla de transiciones. Esa cadena es la codificación ⟨M⟩ de la máquina.

Aquí ocurre el salto conceptual del curso: una máquina es un dato. Puede escribirse en la cinta de otra máquina, y por lo tanto puede ser la entrada de un programa.

LA MÁQUINA UNIVERSAL

Existe una máquina de Turing U que recibe ⟨M, w⟩ —la codificación de una máquina y una entrada— y simula la ejecución de M sobre w. Hace lo que M haría: acepta si M acepta, rechaza si M rechaza, y no para si M no para.

LO QUE ESTO SIGNIFICA

La máquina universal es el concepto de computadora de programa almacenado: una sola máquina que ejecuta cualquier programa que se le dé como dato. Turing la formuló en 1936, nueve años antes de que Von Neumann describiera la arquitectura y casi una década antes de que existiera una computadora electrónica.

También es la semilla de la indecidibilidad. Si una máquina puede recibir máquinas como entrada, se puede preguntar qué pasa cuando recibe su propia codificación. Esa pregunta destruye el programa de Hilbert, y la veremos en la sesión 12.

EJERCICIO

Proponer una codificación concreta para máquinas de Turing y escribir la codificación de una máquina de tres estados.