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

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

Máquinas de Turing: definición

EL MODELO

Una máquina de Turing tiene una cinta infinita dividida en celdas y una cabeza que lee, escribe y se mueve una posición a la izquierda o a la derecha. Con eso basta para capturar todo lo que cualquier computadora puede calcular.

DEFINICIÓN FORMAL

MT = (Q, Σ, Γ, δ, q₀, B, F).

• Q — conjunto finito de estados.
• Σ — alfabeto de entrada.
• Γ — alfabeto de cinta, con Σ ⊂ Γ.
• B ∈ Γ − Σ — el símbolo blanco, que llena el resto de la cinta.
• δ: Q × Γ → Q × Γ × {L, R} — la función de transición.
• q₀ — estado inicial. F — estados de aceptación.

UN PASO DE CÓMPUTO

Leer el símbolo bajo la cabeza, escribir uno nuevo en su lugar, mover la cabeza a izquierda o derecha, y cambiar de estado. Eso es todo. La sorpresa del curso es que con esas cuatro acciones se puede calcular cualquier cosa calculable.

DIFERENCIAS CON UNA COMPUTADORA REAL

• Memoria ilimitada, frente a la memoria finita de una máquina real.
• Acceso secuencial: para llegar a la celda 1000 hay que pasar por las 999 anteriores.
• Sin registros, sin instrucciones aritméticas, sin nada más que leer y escribir símbolos.

Es deliberadamente pobre. Si algo se puede calcular con este modelo mínimo, se puede calcular con cualquier máquina más rica; y si no se puede aquí, tampoco allá.

DESCRIPCIÓN INSTANTÁNEA

Se escribe α q β: α es lo que hay a la izquierda de la cabeza, q el estado, y β lo que hay desde la cabeza hacia la derecha. Un cómputo es una sucesión de descripciones instantáneas.

LOS TRES FINALES POSIBLES

• Aceptar — llega a un estado de aceptación.
• Rechazar — se detiene sin aceptar.
• No parar nunca — sigue trabajando indefinidamente.

El tercer caso es la diferencia decisiva con cualquier modelo anterior y de él nace todo el bloque de computabilidad. Vale la pena anotarlo hoy: una máquina de Turing puede no detenerse, y eso no es un defecto, es una propiedad.

EJERCICIO

Trazar a mano las descripciones instantáneas de una MT sencilla que reconozca cadenas que terminan en cero.