Siguiente: Universalidad Un nivel arriba: Función de Gödel Anterior: Codificación con la función

Codificación de secuencias

Consideremos la función $B_{*2}:I\!\!N^*\rightarrow I\!\!N^2$, $\mbox{\bf x}\mapsto B_{*2}(\mbox{\bf x})=\mbox{\it cod}_{\beta}(\{L(\mbox{\bf x})\}*\mbox{\bf x})$ donde $\{L(\mbox{\bf x})\}*\mbox{\bf x}$ es el vector que se obtiene de anteponer al vector $\mbox{\bf x}$ su propia longitud, es decir,

$$\mbox{\bf x}=(x_1,\ldots,x_n)\in I\!\!N^n\ \Rightarrow\ \{L(\mbox{\bf x})\}*\mbox{\bf x}=(n,x_1,\ldots,x_n)\in I\!\!N^{n+1},$$

y consideremos también la función $B_{2*}:I\!\!N^2\rightarrow I\!\!N^*$, $(x,y)\mapsto B_{2*}(x,y)=\mbox{\bf x}\in I\!\!N^n$ donde $n=\beta(x,y,0)$ y $\forall i=1,\ldots,n:\ x_i=\beta(x,y,i)$. El lector se convencerá de inmediato de que se cumplen las relaciones siguientes:

1.

B_*2 es inyectiva, es decir: $B_{*2}(\mbox{\bf x}_1)=B_{*2}(\mbox{\bf x}_2)\Leftrightarrow\mbox{\bf x}_1=\mbox{\bf x}_2$.

2.

B_*2 no es suprayectiva. En efecto, de acuerdo con la demostración del teorema 3.3.3, una pareja está en la imagen de $\mbox{\it cod}_{\beta}$ sólo si su ordenada, es decir, su segunda componente, es el factorial de un número.

3.

B_2* no es inyectiva. En efecto, de las tablas 3.5 y 3.6, vemos que las 14 parejas obtenidas en 3.5 son tales que bajo B_2* corresponden a la secuencia vacía, pues ésta es la única de longitud 0.

4.

B_2* es suprayectiva, en consecuencia con el teorema 3.3.3.

5.

$B_{2*}\circ B_{*2}=\mbox{\it Id}_{I\!\!N^*}:\mbox{\bf x}\mapsto\mbox{\bf x}$.

6.

$B_{*2}\circ B_{2*}=\mbox{\it Id}_{A}:(x,y)\mapsto (x,y)$, donde $A\subset I\!\!N^2$ es la imagen, bajo la función $\mbox{\it cod}_{\beta}$, de $I\!\!N^*$.

7.

Si $a:I\!\!N^2\rightarrow I\!\!N$ es cualquier función de apareamiento (computable) entonces $a\circ B_{*2}:I\!\!N^*\rightarrow I\!\!N$ es una enumeración (computable), que no será suprayectiva, del conjunto de secuencias de números naturales.

Siguiente: Universalidad Un nivel arriba: Función de Gödel Anterior: Codificación con la función