Un teorema de la teoría de la computabilidad que afirma que toda propiedad semántica no trivial del lenguaje reconocido por una máquina de Turing es indecidible: no existe un algoritmo que, dada una máquina de Turing arbitraria, decida si el lenguaje que acepta posee esa propiedad, siempre que la propiedad dependa solo del lenguaje y no sea trivial.

Principio

Las propiedades semánticas de los lenguajes reconocidos (propiedades que dependen únicamente del conjunto de cadenas aceptadas) son o bien triviales (verdaderas para todas o ninguna máquina) o bien indecidibles; no hay procedimiento general para propiedades lingüísticas no triviales.

Demostración

Ejemplo concreto: la propiedad «el lenguaje reconocido por la máquina es regular» es una propiedad semántica no trivial y, según el teorema de Rice, es indecidible: no se puede escribir un algoritmo que, dada cualquier máquina de Turing, determine correctamente si su lenguaje aceptado es regular.

Aplicación incorrecta

Aplicar Rice a propiedades sintácticas o de recursos (por ejemplo, «¿tiene la máquina menos de 10 estados?» o «¿funciona en tiempo lineal?»), que no son propiedades semánticas puras y pueden ser decidibles; o concluir erróneamente que todo análisis de programas es imposible en la práctica.

Consecuencia

Explica por qué muchas propiedades no triviales de programas (terminación para todas las entradas, equivalencia con una especificación, propiedades no triviales de corrección) son indecidibles en general, y orienta la práctica de análisis estático hacia técnicas aproximadas, conservadoras o limitadas por dominio.

Inversión

El caso inverso es que las propiedades sintácticas o las propiedades semánticas triviales son decidibles; restringir la clase de máquinas o lenguajes (por ejemplo, a autómatas finitos) puede restaurar la decidibilidad.

Límite

Se aplica solo a propiedades semánticas de lenguajes reconocibles por máquinas de Turing que sean no triviales y extensionales (dependen únicamente del lenguaje); no cubre rasgos sintácticos, límites de recursos, garantías probabilísticas ni propiedades definidas respecto a una clase restringida de máquinas.

Tensión semántica

Tensión entre la indecidibilidad semántica (qué es un lenguaje) y el análisis práctico de programas, que se basa en patrones sintácticos, heurísticas, dominios restringidos o aproximaciones conservadoras para evitar el caso general indecidible.

Síntesis

Rice formaliza una limitación amplia: cualquier pregunta no trivial que solo trate sobre el conjunto de cadenas que acepta una máquina de Turing es indecidible, obligando al análisis de programas a apoyarse en aproximaciones, restricciones o información no extensional.