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

NE111 · lunes 21/09/2026 · 16:00-17:15 · Sesión 12

El problema de Halting

QUÉ SÍ ES DECIDIBLE

Antes del resultado negativo conviene ver qué sí se puede decidir, para que el contraste quede claro.

• ¿Un autómata finito acepta una cadena? Decidible: se simula y siempre termina.
• ¿El lenguaje de un autómata finito es vacío? Decidible.
• ¿Dos autómatas finitos son equivalentes? Decidible.
• ¿Una gramática libre de contexto genera una cadena? Decidible.

EL PROBLEMA DE LA PARADA

HALT = {⟨M, w⟩ | la máquina M se detiene con la entrada w}. En palabras: ¿existe un algoritmo que, dado cualquier programa y cualquier entrada, decida si ese programa terminará?

EL TEOREMA

HALT no es decidible. No existe tal algoritmo, y no por falta de ingenio: se demuestra que es imposible.

LA DEMOSTRACIÓN POR DIAGONALIZACIÓN

1. Supón que existe H que decide si M se detiene con w.

2. Construye D que, con entrada ⟨M⟩, ejecuta H sobre ⟨M, ⟨M⟩⟩.

3. Si H dice que M se detiene, D entra en un ciclo infinito. Si H dice que no se detiene, D se detiene.

4. Ejecuta ahora D con su propia codificación ⟨D⟩.

5. Si D se detiene con ⟨D⟩, entonces por construcción cicla. Si cicla, entonces se detiene.

Ambos casos son contradictorios, luego H no puede existir. La contradicción no viene de D, que es perfectamente construible: viene del supuesto de que H existe.

DE DÓNDE SALE LA FUERZA DEL ARGUMENTO

De la máquina universal. Como una máquina puede recibir máquinas como entrada, se le puede dar la suya propia, y ahí se arma la autorreferencia. Es el mismo mecanismo de los teoremas de Gödel y de la paradoja del mentiroso.

HALT SÍ ES RECURSIVAMENTE ENUMERABLE

Se simula M sobre w: si se detiene, se acepta. Si no se detiene, la simulación tampoco, así que nunca se rechaza. Es el ejemplo canónico de lenguaje recursivamente enumerable que no es recursivo, y prueba que la inclusión de la sesión anterior es estricta.

CONSECUENCIAS PRÁCTICAS

• No existe un detector perfecto de ciclos infinitos.
• No existe un verificador de programas totalmente general.
• No existe un antivirus perfecto, por reducción a este mismo problema.
• Los analizadores estáticos reales son aproximaciones: o dan falsos positivos, o falsos negativos, o no siempre terminan.

EJERCICIO

Reconstruir la diagonalización sin apuntes y explicar por qué el complemento de HALT no es recursivamente enumerable.