Teoría
Esta es una variación de Teorema de Rice que dice que si $C$ es un no vacío y adecuado subclase de la clase de todas las funciones recursivas, entonces el conjunto $\{x : \phi_x\in C\}$ no es decidible. Por lo tanto, la función $$g(x)= \begin{cases} 1,\text{ if }\phi_x\in C\\ 0, \text{ else} \end{cases}$$ no es computable.
Una breve aplicación
Ponemos $C$ para ser la subclase de todas las funciones $\phi_x$ tal, que $h(x)\downarrow\Rightarrow \exists n.\phi_x(n)\downarrow$ . Toma $$k(x)= \begin{cases} 0,\text{ if } x>0\\ \uparrow,\text{ else } \end{cases}$$ Observamos que $k\in C$ porque $k(1)\downarrow$ Así que $C$ no está vacía. Además, es una subclase propia, ya que existe una función recursiva parcial que no pertenece a $C$ , es decir, la función no definida en ninguna parte $\Omega(x)=\uparrow$ .
Puede definir $$ g(x)= \begin{cases} 1,\text{ if }h(x)\downarrow\\ 0,\text{ else } \end{cases} = \begin{cases} 1,\text{ if }\phi_x\in C\\ 0,\text{ else } \end{cases} $$ Entonces, por el teorema de Rice, $g(x)$ no es computable. Entonces $h(x)$ tampoco es computable, porque si lo fuera, entonces $g$ también sería computable. Pero no lo es porque el teorema de Rice lo dice.
Una variante
Si no quieres usar el teorema de Rice, puedes usar una variación de su demostración. Aquí ponemos $C$ para ser la subclase de todas las funciones recursivas parciales para las que $\exists n.\phi_x(n)\downarrow$ . Así que en realidad $C$ es el mismo que el anterior y ya hemos encontrado un $k\in C$ .
Así que ahora, observamos que $$h(x)= \begin{cases} \mu y.\phi_x(y)\downarrow,\text{ if }\exists n.\phi_x(n)\downarrow\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.\phi_x(y)\downarrow,\text{ if }\phi_x\in C\\ \uparrow, \text{ else} \end{cases}$$ es bastante similar a $g$ definida anteriormente. Suponemos que es computable. La prueba del teorema de Rice utiliza una función computable $f(x,y)$ definidos con la ayuda de algunos computables $k\in C$ . A continuación, realiza algunas manipulaciones (que implican el teorema S-n-m) y concluye que $g$ compuesta con otra función decidible decide el problema de detención. Esto es una contradicción ya que el problema de detención no es decidible, por lo tanto $g$ no es computable. Utilizaremos un método similar para $h$ en lugar de $g$ .
Por lo tanto, dejemos que $$f(x,y)= \begin{cases} k(y), \text{ if }\phi_x(x)\downarrow\\ \uparrow,\text{ else} \end{cases} = \begin{cases} 0, \text{ if }y>0\text{ or }\phi_x(x)\downarrow\\ \uparrow,\text{ else} \end{cases}$$ Tenga en cuenta que esta es la función en su puesto y es computable. La función de $y>0$ es que necesitamos utilizar alguna función de la subclase $C$ . Y encontramos tal función $k\in C$ que utiliza el caso $y>0$ . Por el teorema S-n-m existe una función recursiva primitiva (es decir, computable) $l(x)$ tal, que $f(x,y)=\phi_{l(x)}(y)$ . Veamos qué ocurre al intentar calcular $h(l(x))$ que se supone que es computable. $$ h(l(x))= \begin{cases} \mu y.\phi_{l(x)}(y)\downarrow,\text{ if }\exists n.\phi_{l(x)}(n)\downarrow\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\exists n.f(x,n)\downarrow\\ \uparrow, \text{ else} \end{cases} =\\= \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\exists n.(f(x,n)=k(n))\\ \uparrow, \text{ else} \end{cases} = \begin{cases} \mu y.f(x,y)\downarrow,\text{ if }\phi_x(x)\downarrow\\ \uparrow, \text{ else} \end{cases} =\text{HP} $$ Así que tienes en tus manos una función que decide el problema de detención, a saber $h\circ l$ . Esto es una contradicción. Así que, $h\circ l$ no es computable. Pero usted sabe que $l$ es, por lo que la suposición errónea que te llevó a la contradicción fue que $h$ es computable.
