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

NE111 · lunes 14/09/2026 · 16:00-17:15 · Sesión 11

Lenguajes recursivos y recursivamente enumerables · Decidibilidad

PROBLEMAS DE DECISIÓN

Un problema de decisión es una pregunta con respuesta sí o no. Se codifica como el lenguaje de las entradas cuya respuesta es sí. Con eso, estudiar problemas equivale a estudiar lenguajes, que es lo que permite aplicar toda la maquinaria del curso.

LAS DOS CLASES

• Recursivo, o decidible — existe una MT que siempre se detiene, aceptando o rechazando.
• Recursivamente enumerable — existe una MT que acepta toda cadena del lenguaje, pero sobre las que no están puede rechazar o no parar nunca.

LA DIFERENCIA EN UNA FRASE

Decidible significa que hay un algoritmo que siempre responde. Recursivamente enumerable significa que hay un procedimiento que responde sí cuando la respuesta es sí, pero que puede quedarse callado para siempre cuando es no.

RELACIONES

• Todo recursivo es recursivamente enumerable. La inclusión es estricta.
• Si L y su complemento son ambos recursivamente enumerables, entonces L es recursivo.
• Los recursivos son cerrados bajo complemento; los recursivamente enumerables no.

LA DEMOSTRACIÓN DEL SEGUNDO PUNTO

Si M₁ acepta L y M₂ acepta su complemento, se ejecutan ambas en paralelo alternando pasos. Toda cadena está en uno de los dos, así que alguna acepta en tiempo finito. Esa simulación siempre para, luego L es decidible.

EXISTEN LENGUAJES QUE NINGUNA MÁQUINA RECONOCE

Es un argumento de conteo. Hay una cantidad numerable de máquinas de Turing, porque cada una se codifica como una cadena finita. Pero hay una cantidad no numerable de lenguajes, porque son subconjuntos de un conjunto infinito.

Al haber estrictamente más lenguajes que máquinas, la mayoría de los lenguajes no tiene máquina que los reconozca. Y se concluye sin exhibir ninguno: es conteo puro, al estilo de Cantor.

ENUMERADORES

Un lenguaje es recursivamente enumerable si y solo si existe una MT que imprime todas sus cadenas, en cualquier orden y sin detenerse. De ahí viene el nombre de la clase.

EJERCICIO

Demostrar que los recursivos son cerrados bajo unión, intersección y complemento, y explicar dónde falla el argumento del complemento para los recursivamente enumerables.