Siguiente: Teoremas de autorreproducción Un nivel arriba: Teoría de la recursividad Anterior: Problema de la parada

Teoremas de recursión

Pese a que los sistemas autorrepresentables adolecen de las incompletitudes antes vistas, ellos poseen propiedades de suma relevancia en la Teoría de la Computabilidad. Veremos que en ellos

• la ``transmisión de parámetros'' es un procedimiento programable,
• en cualquier reenumeración algorítmica de programas habrá un n-ésimo programa que es equivalente al n-ésimo programa de la enumeración canónica. En otras palabras, toda sucesión computable de programas poseee un ``punto fijo'', y
• existe un programa cuya única función es escribir su propio código. Dícese de tal programa que él ``se autorreproduce''.

Supondremos dada una función de codificación $\lceil\cdot\rceil:\{\mbox{\rm programas}\}\rightarrow I\!\!N$ con inversa $\lfloor\cdot\rfloor:I\!\!N\rightarrow \{\mbox{\rm programas}\}$. Dos funciones f,g son equivalentes, $f\equiv g$, si ambas dan mismos resultados ante mismas instancias, es decir,

$$\forall \mbox{\bf x}:\left([f(\mbox{\bf x})\downarrow\Leftrig... ...)\downarrow\Rightarrow f(\mbox{\bf x})=g(\mbox{\bf x})]\right).$$

Teorema 4.1 (de Parametrización)   Existe una función programable h tal que

$$\forall k\in N, \mbox{\bf x}\in N^n, \mbox{\bf y}\in N^m:\hsp... ...\mbox{\bf y})\equiv\lfloor k\rfloor(\mbox{\bf x},\mbox{\bf y}).$$

En otras palabras, dado un programa g, cuyo índice es k, de dos listas de argumentos $\mbox{\bf x}$ y $\mbox{\bf y}$, entonces cuando se deja fijos a los valores de $\mbox{\bf x}$, es decir, cuando a éstos se les ve como parámetros, entonces la función resultante, con $\mbox{\bf y}$ como sola lista de argumentos, posee un índice que es función de k y de $\mbox{\bf x}$. Este teorema también se conoce como Teorema s-m-n de Kleene pues el matemático norteamericano Stephen Cole Kleene lo formuló llamando función s_mⁿ a la que aquí hemos llamado h.


La demostración del teorema consiste únicamente en ver que la expresión de la derecha es algorítmica: Dados k y $\mbox{\bf x}$

1.

decodificamos al programa $\lfloor k\rfloor$,

2.

en él ``instanciamos'' los valores de las variables x's con los dados $\mbox{\bf x}$ y

3.

codificamos el programa resultante.

4.

El índice de ese programa se lo asignamos a $h(k,\mbox{\bf x})$.

Corolario 4.1   Existe una función programable h₀ tal que $\lfloor h_0(x,y)\rfloor \equiv \lfloor \lfloor x\rfloor(y)\rfloor.$

En efecto, consideremos la función $H:(x,y,z)\mapsto \lfloor\lfloor x\rfloor(y)\rfloor(z)$. Aquí, para hacer empatar a H con el teorema de paramatrización, hemos de considerar n=m=1 (k=x, $\mbox{\bf x}=y$ y $\mbox{\bf y}=z$). El corolario se desprende inmediatamente del teorema de paramatrización.

Teorema 4.2 (de la Recursión)   Para cada $g\in\mbox{\rm\rm Programas-{\bf while }}$ existe $k_g\in N$ tal que $\lfloor g(k_g)\rfloor \equiv \lfloor k_g\rfloor.$

En efecto, sea h₀ tal que $\lfloor h_0(x,y)\rfloor=\lfloor \lfloor x\rfloor(y)\rfloor.$ Sea $h_1:x\mapsto h_1(x)=g(h_0(x,x))$. Hagamos $k_1=\lceil h_1\rceil$ y k_g=h₀(k₁,k₁). Se tiene la cadena de programas equivalentes siguiente:

$$\lfloor k_g\rfloor \equiv \lfloor h_0(k_1,k_1)\rfloor % \equi... ...lfloor g(h_0(k_1,n_1))\rfloor % \equiv \lfloor g(k_0)\rfloor$$

Siguiente: Teoremas de autorreproducción Un nivel arriba: Teoría de la recursividad Anterior: Problema de la parada