Demostración de la no computabilidad -- Teorema de Rice

Question

Intento demostrar la imposibilidad de calcular la siguiente función: Sea $\varphi$ sea una numeración de Gödel de las funciones computables. Consideremos la siguiente función:

\begin{align*} f(x) = \left\{ \begin{array}{l l} \mathrm{min}\ n \text{ among } \varphi_x(n) \downarrow & \quad \text{if $\exists n\ \varphi_x(n) \downarrow$}\\ 0 & \quad \text{otherwise} \end{array} \De acuerdo. \Fin.

Ahora bien, es evidente que esta función no es computable. Mi pregunta ahora es si el siguiente argumento es correcto: Consideremos la siguiente función:

\begin{align*} g(x) = \left\{ \begin{array}{l l} 1 & \quad \text{if $f(x) \neq 0$}\\ 0 & \quad \text{otherwise} \end{array} \De acuerdo. \Fin.

Si $f$ era computable, $g$ también sería computable. Por lo tanto, el conjunto $\{x\,|\,g(x) = 1\}$ sería recursivo. ¿Es ésta una conclusión correcta y, en caso afirmativo, puedo entonces aplicar el teorema de Rice para obtener la no decidibilidad del conjunto y, por tanto, la no computabilidad de $f$ . O bien: ¿hay una manera mejor de obtener una prueba de la no computabilidad de $f$ ?

TIA

Trin

Answer 1

Sí, eso parece correcto.

Yo personalmente evitaría introducir $g$ que en realidad no hace mucho, y sólo escribir:

El valor de $f(x)$ depende claramente sólo en $\varphi_x$ (cada $x$ en la definición de $f(x)$ aparece como subíndice de $\varphi$ ), por lo que $\{x\mid f(x)=n\}$ es extensional para cada $n\ge 0$ . Puesto que también es obviamente no trivial para cada $n$ Rice dice que no puede ser computable. Pero sería fácilmente computable si $f$ era, así que $f$ no lo es.