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

NE111 · miércoles 23/09/2026 · 16:00-17:15 · Sesión 13

Reducciones, indecidibilidad y el teorema de Rice

LA TÉCNICA

Demostrar indecidibilidad desde cero, como con HALT, es laborioso. Las reducciones permiten heredar el resultado: si un problema ya conocido como indecidible se reduce al nuevo, el nuevo también lo es.

REDUCCIÓN

A se reduce a B, escrito A ≤ B, si existe una función computable que transforma instancias de A en instancias de B preservando la respuesta.

• Si A ≤ B y B es decidible, entonces A es decidible.
• Contrapositiva, que es la que se usa: si A ≤ B y A es indecidible, entonces B es indecidible.

LA DIRECCIÓN CORRECTA

Se reduce lo conocido indecidible al problema nuevo, nunca al revés. Invertir la dirección produce una demostración vacía. Conviene decirlo en voz alta antes de escribir: «reduzco HALT a mi problema».

PROBLEMAS INDECIDIBLES

• ¿L(M) es vacío?
• ¿M acepta la cadena vacía?
• ¿L(M) es regular?
• ¿M₁ y M₂ reconocen el mismo lenguaje?
• ¿Una gramática libre de contexto dada es ambigua?
• El problema de correspondencia de Post.

TEOREMA DE RICE

Toda propiedad no trivial del lenguaje reconocido por una máquina de Turing es indecidible. Una propiedad es no trivial si algunas máquinas la cumplen y otras no.

LA DISTINCIÓN QUE HAY QUE RETENER

Rice habla de propiedades del lenguaje, no del texto de la máquina. «¿Este programa tiene más de cien líneas?» sí es decidible, porque es una propiedad sintáctica. «¿Este programa calcula la función identidad?» es indecidible, porque es una propiedad de lo que hace.

La consecuencia es fuerte: cualquier pregunta interesante sobre el comportamiento de un programa es indecidible en general.

QUÉ QUEDA ENTONCES

La verificación de programas sigue siendo posible bajo restricciones: lenguajes que no son Turing-completos, análisis conservador que acepta falsos positivos, o demostración asistida donde el humano aporta las invariantes. Saber qué es imposible orienta hacia lo que sí se puede.

EJERCICIO

Reducir HALT al problema de la cinta vacía; aplicar Rice a tres propiedades y encontrar una a la que no aplique.