##  [Teorema de Rice](/es/node/58847) 

 Definición

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

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

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

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

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

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

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 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

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.