Siguiente: Construcción de virus Un nivel arriba: Virus en programas-while Anterior: Matrices infinitas

Teoremas de recursión

Una función $g:I\!\!N\rightarrow I\!\!N$ se dice ser extensional si $\forall i,j:\ \ [f_i=f_j\ \Rightarrow\ f_{g(i)}=f_{g(j)}].$

Ejemplos 1. Cualquier función constante es extensional. 2. Sea g la función construída como sigue: Dado i, calculamos el i-ésimo programa

$$P_i=P_i(X_0, X_1, X_2, X_3,X_4, X_5,X_6, X_7, \ldots).$$

g(i) será el código del programa obtenido al ``instanciar'' las primeras tres variables por los valores consecutivos 1,2,3 y renombrar las demás variables:

$$g(i)=\lceil P_i(X_0\leftarrow 1, X_1\leftarrow 2, X_2\leftarrow 3, X_0\leftarrow X_3,X_1\leftarrow X_4, \ldots)\rceil.$$

Es evidente que g es extensional. 3. La función sucesor no es extensional: Si P_i y P_j son dos programas que calculan una misma función, no necesariamente P_i+1 y P_j+1 han de calcular una misma función.

Observación 6.1   Toda función extensional g define un operador entre funciones recursivas:

$$\begin{eqnarray*}\Gamma_g:\{\mbox{\rm recursivas}\} &\rightarrow& \{\mbox{\rm recursivas}\} \\ f_i&\mapsto& \Gamma_g(f_i)=f_{g(i)} \end{eqnarray*}$$

Teorema 6.1 (Débil de Recursión)   Si g es extensional entonces $\Gamma_g$ posee un punto fijo.

Demostración: Sea M la siguiente matriz consistente de funciones recursivas, $\forall i,j:\ \ m_{ij}=f_{f_i(j)}.$ Si $f_i(j)=\perp$ entonces la función f_fi(j) coincidirá con la función divergente en todo punto: $\perp:x\mapsto \perp$. M es efectivamente computable. De hecho, dados i,j procedamos como sigue:

1.

con Rep calculamos P_i,

2.

con eval calculamos k=P_i(j),

3.

tras calcular k, con Rep calculamos P_k.

Sea P^M el programa-while que implementa el procedimiento anterior. Entonces P^M(i,j)=m_ij. M es diagonalmente completa: Sea Q tal que Q(j)=P^M(j,j). Q es evidentemente ``realizable'' como un programa-while y consecuentemente $\exists i_d:P_{i_d}=Q$. Así pues

m_idj=P_id(j)=Q(j)=P^M(j,j)=m_jj.

M es cerrado por renglones bajo $\Gamma_g$: Dado i sea P^M,i;g el programa tal que $\forall j: P^{M,i;g}(j)=P^M(g(i),j)$. Existe entonces $h(i)\in I\!\!N$ tal que P_h(i)=P^M,i;g. Entonces para cualquier j se tiene

$$m_{h(i)j}=P_{h(i)}(j)=P^{M,i;g}(j)=P^M(g(i),j)=m_{g(i),j}=\Gamma_g(m_{ij}).$$

Del Lema Diagonal de Punto Fijo se sigue que $\Gamma_g$ posee un punto fijo.

Teorema 6.2 (De Recursión)   Si g es cualquier función recursiva entonces $\Gamma_g$ posee un punto fijo, es decir $\exists k:\ f_k=f_{g(k)}.$

Demostración: Dados i₁,i₂ diremos que f_i1 se relaciona con f_i2 según g, $f_{i_1}\stackrel{g}{\leadsto}f_{i_2}$, si existe k tal que

$$\begin{array}{ccc} f_k=f_{i_1} &\& & f_{g(k)}=f_{i_2}. \end{array}$$

Se tiene que $\forall i_1\exists i_2:f_{i_1}\stackrel{g}{\leadsto}f_{i_2}$. Como M es además diagonalmente completa tenemos que algún elemento en su diagonal m_ii se relaciona consigo mismo. Así pues existe k tal que f_k=m_ii=f_g(k).
Siguiente: Construcción de virus Un nivel arriba: Virus en programas-while Anterior: Matrices infinitas