Problemas indecidibles y reducciones

El problema de la parada es el primero, y casi el único que se demuestra con un argumento diagonal. Todos los demás resultados de imposibilidad se prueban de otra forma, mucho más barata: mostrando que si ese problema se pudiera resolver, la parada también.

La mecánica de la reducción

La estructura del argumento es siempre la misma. Se supone que existe un decisor para el problema nuevo $X$, y se construye con él un decisor para la parada. Como la parada no es decidible, $X$ tampoco.

La dirección es la misma que en las reducciones de NP-completitud y se confunde igual de seguido: se reduce el problema conocido-imposible al nuevo, nunca al revés. Reducir $X$ a la parada no dice nada; sólo indica que $X$ no es peor.

Un ejemplo concreto, paso a paso

Un ejemplo concreto: decidir si un programa alguna vez imprime “hola”. Supongamos que existe imprime_hola(P).

Dado un programa $P$ y una entrada $x$, construyo un programa nuevo que ejecuta $P$ sobre $x$ y, si eso termina, imprime “hola”. Ese programa imprime “hola” exactamente cuando $P$ termina con $x$. Preguntándole a imprime_hola habría resuelto la parada. Contradicción: decidir si un programa imprime cierta cosa es indecidible.

El teorema de Rice ahorra todas esas demostraciones

El teorema de Rice ahorra todas esas demostraciones de un saque: cualquier propiedad no trivial del lenguaje que reconoce un programa —es decir, de lo que computa, no de cómo está escrito— es indecidible.

“No trivial” significa que algunos programas la cumplen y otros no. Así que decidir si un programa calcula la función constante cero, si termina para toda entrada, o si es equivalente a otro, son todos indecidibles sin necesidad de argumento propio. La contracara: propiedades sintácticas —cuántas líneas tiene, si usa cierta palabra clave— son perfectamente decidibles.

La indecidibilidad lejos de los programas

La indecidibilidad aparece lejos de los programas. El problema de correspondencia de Post, un rompecabezas de fichas con cadenas arriba y abajo, es indecidible, y se usa como base para reducir problemas sobre gramáticas: decidir si dos gramáticas libres de contexto generan el mismo lenguaje, por ejemplo.

El décimo problema de Hilbert —decidir si una ecuación polinómica con coeficientes enteros tiene solución entera— también resultó indecidible, después de setenta años. Y los teoremas de incompletitud de Gödel son el mismo fenómeno en lógica: ningún sistema formal consistente y suficientemente expresivo demuestra todas las verdades sobre los números.

No todo lo indecidible es igual

No todo lo indecidible es igual. Hay una escala: los lenguajes reconocibles —donde se puede confirmar un sí pero no descartar— son un escalón; su complemento, otro; y hay problemas que no son ni reconocibles ni co-reconocibles, como decidir si un programa termina para toda entrada.

Esa jerarquía se formaliza con oráculos: una máquina con acceso gratuito a un decisor de la parada resuelve más cosas, pero tiene su propio problema de la parada indecidible. La imposibilidad no se acaba agregando poder; se reproduce un nivel más arriba.

Cuando una herramienta promete demasiado

Esto no es sólo teoría de la carrera. Cada vez que una herramienta promete decidir algo sobre programas arbitrarios —detectar todo el código muerto, garantizar ausencia de bugs, identificar todo el malware— vale la pena preguntarse en qué lado de Rice cae la propiedad.

La respuesta casi siempre es que la herramienta aproxima, y saber eso cambia cómo se la evalúa: no por si acierta siempre, sino por su tasa de falsos positivos y falsos negativos, que es lo único que puede ofrecer.

El teorema de Rice, y lo que deja afuera

Cierre

Después de la parada, la indecidibilidad se propaga por reducción: si resolver $X$ resolvería la parada, $X$ tampoco se puede. El teorema de Rice extiende eso a toda propiedad no trivial de lo que un programa computa, y deja afuera sólo lo sintáctico.