Función recursiva que salidas de su propio código

Question

Este problema probablemente es bastante trivial, ya que tengo la impresión de que es un libro de texto al estilo de uno, pero, no obstante, de alguna manera no se le dará. Aquí está:

Tengo que demostrar que existe una (unario) función recursiva, que tiene el código $c$ y también se toma el valor constante $c$ (es decir, salidas de su propio código).

Estoy bastante seguro de que, tengo que usar Kleene (segundo) teorema de recursión, que dice que para un dado (total) función recursiva $f:\mathbb{N} \rightarrow \mathbb{N}$ hay un número de código/ $c$ tal que $\phi_c=\phi_{f(c)}$ (donde $\phi_a$ es el parcial recursiva de la función que tiene el código $a$), pero no puedo averiguar cómo...

Answer 1

Sólo deje que $f(x)$ ser una función que, de entrada $x$, crea y devuelve un % de programa $P_x$tal que $P_x$el % ignora su entrada y devuelve el número $x$.

Answer 2

Deje $T_i$ ser una Máquina de Turing con número de Gödel $i$ $\phi_i$ la función calculada por $T_i$.

Queremos demostrar que existe un número $n_0$ tal que $T_{n_0}$ imprime su propia codificación $n_0$. Deje $\phi_0, \phi_1, ...$ ser cualquier enumeración (la numeración de Gödel) de todas las funciones computables y deje $h$ ser totalmente cualquier función computable. Entonces, por el teorema de punto fijo (como usted tiene sospecha), existe un número $i_0$ tal que $\phi_{i_0} = \phi_{h(i_0)}$, es decir, $i_0$ es un punto fijo para $h$.

Vamos ahora a definir la función de $h$ a ser la función tal que para cada número natural $n$, $h(n)$ es igual a una máquina que imprime $n$ y se detiene, es decir, tal que $\phi_{h(n)} = n$. Deje $n_0$ ser un punto fijo para $h$. A continuación,$\phi_{n_0} = \phi_{h(n_0)} = n_0$.

Answer 3

Desea $\phi_c$ que "la función que $c$". Por lo tanto, desea $\phi_{f(c)}$ también al ser una función que salidas $c$. La diferencia es que puedes controlar $\phi_{f(c)}$ puesto que controlas $f(x)$.

Así que quieres definir $f(x)$ para ser el código de la función constante $x$ (es decir, devuelve $x$ para cada entrada). Ahora Teorema de Kleene da lo siguiente: existe $c$ tal que la función codificada por $c$ es exactamente la función constante $c$.