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

NE111 · lunes 24/08/2026 · 16:00-17:15 · Sesión 5

Diseño de máquinas de Turing

CÓMO SE DISEÑA UNA MT

La pregunta guía es qué necesita recordar la máquina y qué puede marcar sobre la cinta. A diferencia de un autómata, aquí la cinta sirve como memoria de trabajo: se pueden dejar marcas y volver a leerlas.

TÉCNICAS HABITUALES

• Marcar símbolos ya procesados con un carácter especial del alfabeto de cinta.
• Ir y venir entre extremos, emparejando símbolos de uno y otro lado.
• Usar el estado para recordar el símbolo que se acaba de leer.
• Reservar zonas de la cinta como área de trabajo separada de la entrada.

EJEMPLO: RECONOCER 0ⁿ1ⁿ

1. Marcar el primer 0 sin marcar y recordar en el estado que se buscó un 0.

2. Avanzar a la derecha hasta el primer 1 sin marcar y marcarlo.

3. Regresar a la izquierda hasta el primer símbolo sin marcar.

4. Repetir hasta que no queden ceros sin marcar.

5. Verificar que tampoco queden unos sin marcar. Si es así, aceptar.

Nota que no hizo falta una pila: bastó marcar sobre la cinta e ir y venir. Esa capacidad de escribir es lo que le da a la MT su potencia.

EJEMPLO: RECONOCER AⁿBⁿCⁿ

La misma técnica funciona con tres bloques: se marca una a, una b y una c en cada pasada. Conviene retener este resultado, porque más adelante veremos que ni los autómatas finitos ni los de pila pueden reconocer este lenguaje. La MT sí, sin esfuerzo adicional.

MT COMO CALCULADORA DE FUNCIONES

Además de aceptar o rechazar, una MT puede dejar un resultado en la cinta. Con esa lectura calcula funciones: la entrada se escribe al inicio y lo que quede al detenerse es la salida. Así se define qué significa que una función sea computable.

EJERCICIO

Diseñar máquinas de Turing que reconozcan palíndromos sobre {a,b} y que sumen uno a un número en binario.