Recientemente he leído un artículo titulado "Teorías de la complejidad computacional". En el artículo se afirma que con el teorema de Rice se puede demostrar que, por ejemplo, { $i[\mathbb N:\phi_i$ es una función constante}, no es recursiva, pero no veo cómo. Ya conozco el teorema, pero no entiendo muy bien cómo puedo utilizarlo. Gracias por tu respuesta.
Respuesta
¿Demasiados anuncios?
El teorema de Rice dice que para cualquier subconjunto $F$ de la clase $T$ de funciones parcialmente computables, el conjunto $\{i\mid \phi_i\in F\}$ es recursivo si $F=\emptyset$ o $F=T$ .
Sea $F$ sea el conjunto de funciones parcialmente computables que son constantes en su dominio. $F$ es ciertamente no vacía, ya que la función que siempre toma el valor 0 es ciertamente computable. $F$ tampoco es toda la clase $T$ ya que la función $\phi$ con $\phi(0)=0$ , $\phi(n)=1$ para $n>0$ es ciertamente computable y no constante.
De ello se deduce que el conjunto que te interesa no es recursivo.
Si su confusión radica en cómo traducir el enunciado habitual del teorema de Rice (en términos de problemas de decisión) a la versión que yo escribí, simplemente recuerde que formalmente un problema de decisión es un conjunto $D\subseteq{\mathbb N}$ y el problema es decidible si $D$ es recursivo. Por supuesto, esto se suele afirmar diciendo que existe una máquina de Turing que, dada $n$ decide si $n\in D$ o no. Pero esto es ciertamente lo mismo que decir que la máquina calcula la función característica de $D$ que es (la definición de) ser recursivo.
