Teorema de recursión de Kleene

La demostración utiliza una función computable total particular.${\displaystyle h}$, definido de la siguiente manera. Dado un número natural${\displaystyle x}$, la función${\displaystyle h}$Devuelve el índice de la función computable parcial que realiza el siguiente cálculo:

Dado un input${\displaystyle y}$, primer intento de calcular${\displaystyle \varphi _{x}(x)}$. Si ese cálculo devuelve una salida${\displaystyle e}$, luego calcular${\displaystyle \varphi _ {e}(y)}$y devolver su valor, si lo hay. Por lo tanto, para todos los índices${\displaystyle x}$de funciones computables parciales, si${\displaystyle \varphi _{x}(x)}$se define, entonces${\displaystyle \varphi _{h(x)}\simeq \varphi _{\varphi _{x}(x)}}$. Si${\displaystyle \varphi _{x}(x)}$no está definido, entonces${\displaystyle \varphi _{h(x)}}$es una función que no está definida en ninguna parte. La función${\displaystyle h}$puede construirse a partir de la función computable parcial${\displaystyle g(x,y)}$descrito anteriormente y el teorema S m n   : para cada${\displaystyle x}$, el número${\displaystyle h(x)}$es el índice de un programa que calcula la función${\displaystyle y\mapsto g(x,y)}$.

Para completar la demostración, dejemos${\displaystyle F}$sea ​​cualquier función computable total y construya${\displaystyle h}$como arriba. Deje${\displaystyle e}$ser un índice de la composición${\displaystyle F\circ h}$, que es una función totalmente computable, por lo tanto${\displaystyle \varphi _ {e}(e)}$está definido. Entonces${\displaystyle \varphi _{h(e)}\simeq \varphi _{\varphi _{e}(e)}}$por definición de${\displaystyle h}$Pero, porque${\displaystyle e}$es un índice de${\displaystyle F\circ h}$,${\displaystyle \varphi _ {e}(e)=(F\circ h)(e)=F(h(e))}$y por lo tanto${\displaystyle \varphi _{h(e)}\simeq \varphi _{F(h(e))}}$. Por eso${\displaystyle \varphi _{n}\simeq \varphi _{F(n)}}$para${\displaystyle n=h(e)}$.

Esta demostración es una construcción de una función recursiva parcial que implementa el combinador Y.

Una función${\displaystyle F}$de tal manera que${\displaystyle \varphi _{e}\not \simeq \varphi _{F(e)}}$a pesar de${\displaystyle e}$Se denomina libre de punto fijo . El teorema del punto fijo muestra que ninguna función totalmente computable es libre de punto fijo, pero existen muchas funciones no computables libres de punto fijo. El criterio de completitud de Arslanov establece que el único grado de Turing recursivamente enumerable que computa una función libre de punto fijo es 0 ′ , el grado del problema de la parada . ^{[ 5 ]}

El segundo teorema de recursión de Kleene y el teorema de Rogers pueden demostrarse, de forma bastante sencilla, uno a partir del otro. ^{[ 6 ]} Sin embargo, una demostración directa del teorema de Kleene ^{[ 7 ]} no utiliza un programa universal, lo que significa que el teorema se cumple para ciertos sistemas de programación subrecursiva que no poseen un programa universal.

Un ejemplo clásico que utiliza el segundo teorema de recursión es la función${\displaystyle Q(x,y)=x}$. El índice correspondiente${\displaystyle p}$En este caso, produce una función computable que genera su propio índice cuando se aplica a cualquier valor. ^{[ 8 ]} Cuando se expresan como programas informáticos, dichos índices se conocen como quines .

El siguiente ejemplo en Lisp ilustra cómo el${\displaystyle p}$en el corolario se puede producir eficazmente a partir de la función${\displaystyle Q}$. La función s11en el código es la función de ese nombre producida por el teorema S m n   .

Qpuede cambiarse a cualquier función de dos argumentos.

( setq Q ' ( lambda ( x y ) x )) ( setq s11 ' ( lambda ( f x ) ( list 'lambda ' ( y ) ( list f x 'y )))) ( setq n ( list 'lambda ' ( x y ) ( list Q ( list s11 'x 'x ) 'y ))) ( setq p ( eval ( list s11 n n )))

Los resultados de las siguientes expresiones deberían ser los mismos.${\displaystyle \varphi }$p(nil)

( eval ( list p nil ))

Q(p, nil)

( eval ( list Q p nil ))

Supongamos que${\displaystyle g}$y${\displaystyle h}$son funciones computables totales que se utilizan en una definición recursiva para una función${\displaystyle f}$:

${\displaystyle f(0,y)\simeq g(y),}$

${\displaystyle f(x+1,y)\simeq h(f(x,y),x,y),}$

El segundo teorema de recursión puede utilizarse para demostrar que dichas ecuaciones definen una función computable, donde la noción de computabilidad no tiene por qué permitir, a primera vista, definiciones recursivas (por ejemplo, puede definirse mediante μ -recursión o mediante máquinas de Turing ). Esta definición recursiva puede convertirse en una función computable.${\displaystyle \varphi _{F}(e,x,y)}$eso supone${\displaystyle e}$es un índice de sí mismo, para simular la recursión:

${\displaystyle \varphi _{F}(e,0,y)\simeq g(y),}$

${\displaystyle \varphi _{F}(e,x+1,y)\simeq h(\varphi _{e}(x,y),x,y).}$

El teorema de recursión establece la existencia de una función computable.${\displaystyle \varphi _{f}}$de tal manera que${\displaystyle \varphi _{f}(x,y)\simeq \varphi _{F}(f,x,y)}$. De este modo ${\displaystyle f}$Satisface la definición recursiva dada.

La programación reflexiva se refiere al uso de la autorreferencia en los programas. Jones presenta una visión del segundo teorema de recursión basada en un lenguaje reflexivo. ^{[ 9 ]} Se demuestra que el lenguaje reflexivo definido no es más fuerte que un lenguaje sin reflexión (porque se puede implementar un intérprete para el lenguaje reflexivo sin usar reflexión); luego, se demuestra que el teorema de recursión es casi trivial en el lenguaje reflexivo.

Al igual que el segundo teorema de recursión, el primer teorema de recursión puede utilizarse para obtener funciones que satisfacen sistemas de ecuaciones de recursión. Para aplicar el primer teorema de recursión, las ecuaciones de recursión deben reformularse primero como un operador recursivo.

Consideremos las ecuaciones de recurrencia para la función factorial f :$${\displaystyle {\begin{aligned}&f(0)=1\\&f(n+1)=(n+1)\cdot f(n)\end{aligned}}}$$El operador recursivo correspondiente Φ tendrá información que indica cómo llegar al siguiente valor de f desde el valor anterior. Sin embargo, el operador recursivo definirá en realidad la gráfica de f . Primero, Φ contendrá el par${\displaystyle (\varnothing ,(0,1))}$. Esto indica que f (0) es inequívocamente 1, y por lo tanto el par (0,1) está en la gráfica de f .

A continuación, para cada n y m , Φ contendrá el par${\displaystyle (\{(n,m)\},(n+1,(n+1)\cdot m))}$Esto indica que, si f ( n ) es m , entonces f ( n + 1) es ( n + 1) m , de modo que el par ( n + 1, ( n + 1) m ) está en la gráfica de f . A diferencia del caso base f (0) = 1 , el operador recursivo requiere cierta información sobre f ( n ) antes de definir un valor de f ( n + 1) .

El primer teorema de recursión (en particular, la parte 1) establece que existe un conjunto F tal que Φ( F ) = F . El conjunto F estará compuesto enteramente por pares ordenados de números naturales y será la gráfica de la función factorial f , como se deseaba.

La restricción a ecuaciones de recursión que pueden reformularse como operadores recursivos garantiza que las ecuaciones de recursión definan realmente un punto fijo mínimo . Por ejemplo, consideremos el conjunto de ecuaciones de recursión:$${\displaystyle {\begin{aligned}&g(0)=1\\&g(n+1)=1\\&g(2n)=0\end{aligned}}}$$No existe ninguna función g que satisfaga estas ecuaciones, ya que implican tanto g (2) = 1 como g (2) = 0. Por lo tanto, no existe ningún punto fijo g que satisfaga estas ecuaciones de recurrencia. Es posible crear un operador de enumeración que corresponda a estas ecuaciones, pero no será un operador recursivo.

La demostración de la parte 1 del primer teorema de recursión se obtiene iterando el operador de enumeración Φ comenzando con el conjunto vacío . Primero, se construye una secuencia F _k , para${\displaystyle k=0,1,\ldots }$. Sea F ₀ el conjunto vacío. Procediendo inductivamente, para cada k , sea F k _{+ 1}${\displaystyle F_{k}\cup \Phi (F_{k})}$. Finalmente, se toma F como${\textstyle \bigcup F_{k}}$El resto de la demostración consiste en verificar que F es recursivamente enumerable y es el punto fijo más pequeño de Φ. La secuencia F _k utilizada en esta demostración corresponde a la cadena de Kleene en la demostración del teorema del punto fijo de Kleene .

La segunda parte del primer teorema de recursión se deduce de la primera. Se utiliza la suposición de que Φ es un operador recursivo para demostrar que el punto fijo de Φ es la gráfica de una función parcial. El punto clave es que si el punto fijo F no es la gráfica de una función , entonces existe algún k tal que F _k no es la gráfica de una función.

En comparación con el segundo teorema de recursión, el primer teorema de recursión produce una conclusión más sólida, pero solo cuando se cumplen hipótesis más restrictivas. Rogers utiliza el término teorema de recursión débil para el primer teorema de recursión y teorema de recursión fuerte para el segundo. ^{[ 3 ]}

Una diferencia entre el primer y el segundo teorema de recursión es que los puntos fijos obtenidos mediante el primer teorema de recursión están garantizados como puntos fijos mínimos, mientras que los obtenidos mediante el segundo teorema de recursión pueden no ser puntos fijos mínimos.

Una segunda diferencia radica en que el primer teorema de recursión solo se aplica a sistemas de ecuaciones que pueden reformularse como operadores recursivos. Esta restricción es similar a la que se aplica a operadores continuos en el teorema de punto fijo de Kleene de la teoría del orden . El segundo teorema de recursión puede aplicarse a cualquier función recursiva total.