Siguiente: Función de Gödel Un nivel arriba: Funciones de apareamiento y Anterior: Codificación con primos

Reiteración de funciones de apareamiento

Sea $a:I\!\!N^2\rightarrow I\!\!N$ una función de apareamiento. Definimos inductivamente $a_n:I\!\!N^n\rightarrow I\!\!N$ como sigue

$$\begin{array}{lcrcl} a_1&:&x &\mapsto& x \\ a_{n+1}&:&(\mbox{\bf x},x) &\mapsto& a(a_{n}(\mbox{\bf x}),x) \end{array}$$

Para cada $j\leq n$ la j-ésima proyección $\pi_{nj}$ se define de manera que

$$\forall \mbox{\bf x}\in I\!\!N^n:\ \ \pi_{nj}(a_n(\mbox{\bf x}))=x_j.$$

Se ve fácilmente que $\forall z\in I\!\!N$:

$$\pi_{nj}(z)=\left\{\begin{array}{ll} \pi^a_2\left(\pi^a_1\ri... ...right)^{n-2}(z) &\mbox{\rm si $j=1$ . } \end{array}\right.$$ (11)

También podemos definir $a_*:I\!\!N^*\rightarrow I\!\!N$ como $\mbox{\bf x}\mapsto a\left(L(\mbox{\bf x}),a_{L(\mbox{\bf x})}(\mbox{\bf x})\right)$, donde $L(\mbox{\bf x})$ es la longitud de la secuencia $\mbox{\bf x}$. La inversa de a_* se calcula de manera inmediata: Dado $z\in I\!\!N$, $l=\pi^a_1(z)$ es la longitud del vector $\mbox{\bf x}$ el cual es, precisamente, $\mbox{\bf x}=\left(a_l\right)^{-1}(\pi^a_2(z))$. También, la función

$$\pi_{*j}:z\mapsto \left\{\begin{array}{ll} x_j &\mbox{\rm ... ...} \\ \perp &\mbox{\rm en otro caso. } \end{array}\right.$$ (12)

en términos de las funciones $\pi_{nj}$ puede escribirse como $\pi_{*j}(z)=\pi_{nj}(\pi^a_2(z))$, donde $n=\pi^a_2(z)$.

Para concluir esta sección, utilizando funciones de apareamiento computables, veremos que todas las funciones computables pueden ser calculadas poniendo cotas al número de variables que aparezcan en los programas-while que calculen a las funciones computables. Observemos primeramente que se cumple la

Proposición 2.1   Si la función de apareamiento a fuese computable por un programa-while con a lo sumo m variables entonces su reiteración a_n ha de ser computable por un programa-while con a lo sumo m+n variables.

En efecto, supongamos que P_a es un programa-while con m variables, de las cuales las dos primeras X,Y son de entrada y la última Z es de salida, que calcula z=a(x,y) dada la pareja (x,y). Entonces la reiteración a_n se calcula por el programa siguiente con n+m variables:

Observamos que las n variables suplementarias se utilizan tan solo como almacenamiento de la ``entrada'' del programa descrito.

Por otro lado, se tiene la

Proposición 2.2   Se puede construir programas que calculen a las proyecciones con una cota uniforme para el número de variables utilizadas. Es decir: Existe $p\in I\!\!N$ tal que para cualesquiera j,n que cumplan con la restricción $1\leq j\leq n$, la j-ésima proyección $\pi_{nj}$ se calcula por un programa-while con a lo sumo p variables.

En efecto, de acuerdo con 3.1, la j-ésima proyección $\pi_{nj}$ es una ``reiteración'' de a lo sumo n-j+1 proyecciones de a. Supongamos que Q_1a y Q_2a sean sendos programas-while que calculan a las proyecciones $\pi^a_1$ y $\pi^a_2$. Para el cálculo de las proyecciones podemos proceder según el seudoprograma siguiente:

p ha de ser el número de variables que resultan al escribir ese seudoprograma como un verdadero programa-while .

De manera similar, puede verse que, si a es computable, entonces la función a_* también lo es.

Proposición 2.3 (Arreglos de variables)   Se puede dotar a las programas-while de arreglos de variables.

De la definición de a_* y de sus respectivas proyecciones en 3.2, tenemos que existe un programa-while Q_* tal que dados j,z calcula la j-ésima proyección $\pi_{*j}(z)$ como en 3.2. Así pues, a un arreglo de variables X[1:k] lo podemos representar por una variable X1 y asignaciones de la forma X[j]:=Z o Z:=X[j] quedarán como macros de los sendos seudoprogramas:

(en ambos seudoprogramas marcamos con un asterisco la instrucción ``clave''.)

De aquí se tiene

Proposición 2.4   Existe un entero $p\in I\!\!N$ tal que toda función computable $f:I\!\!N^n\rightarrow I\!\!N$ es calculada por un programa-while con a lo sumo (n+p) variables.

Demostración: Se puede utilizar funciones de apareamiento para ``almacenar'' los valores de las variables que excedan de n+p, donde p es como en la proposición anterior. En efecto, a una variable se la puede considerar como un arreglo de todas las variables que hagan que el número n+p se exceda.
Siguiente: Función de Gödel Un nivel arriba: Funciones de apareamiento y Anterior: Codificación con primos