Siguiente: Algunas funciones de apareamiento Un nivel arriba: Funciones de apareamiento y Anterior: Funciones de apareamiento y

Funciones de apareamiento

Estas funciones asocian, de manera única, un número natural a una pareja de naturales. Pueden ser consideradas funciones de codificación de parejas por números. Diremos que una función $a:I\!\!N^2\rightarrow I\!\!N$ es de apareamiento si ella es inyectiva. Para una tal función sus proyecciones son funciones $\pi^a_1,\pi^a_2:I\!\!N\rightarrow I\!\!N$ tales que

$$\begin{eqnarray*}\forall i,j\in I\!\!N&:& \pi^a_1(a(i,j))=i\ \&\ \pi^a_2(a(i,j))=j \\ \forall z\in I\!\!N^2 &:& a(\pi^a_1(z),\pi^a_2(z))=z \end{eqnarray*}$$

Proposición 1.1   Si una función de apareamiento a es computable entonces sus proyecciones $\pi^a_1,\pi^a_2$ también lo son.

Demostración: Observemos que la proposición se cumple considerando, en particular, la enumeración de Cantor $c:(x,y)\mapsto \frac{1}{2}(x+y)(x+y+1)+x$ que, de hecho, es computable y de apareamiento. En efecto, sea $\mbox{\it diag}:I\!\!N\rightarrow I\!\!N$ la función que dado z indica ``entre cuáles sumas de primeros números naturales está z'',

$$\mbox{\it diag}:z\mapsto \mathop{\rm Min}\left\{d\vert\frac{1}{2}(d)(d+1)\leq z<\frac{1}{2}(d+1)(d+2)\right\}.$$

Es evidente que $\mbox{\it diag}$ es recursiva primitiva. Las proyecciones de la enumeración de Cantor son

$$\begin{eqnarray*}\pi^c_1:z &\mapsto& z-\frac{1}{2}\mbox{\it diag}(z)(\mbox{\it diag}(z)+1) \\ \pi^c_2:z &\mapsto& \mbox{\it diag}(z)-\pi^c_1(z) \end{eqnarray*}$$

Así pues, son también recursivas primitivas y, consecuentemente, computables. Ahora, dada a, cualquier función de apareamiento y computable, podemos calcular sus proyecciones de la siguiente forma: Dado $z\in I\!\!N$,

1.

Pruébese, siguiendo la enumeración de Cantor, para cada pareja $\mbox{\bf x}\in I\!\!N^2$ si acaso corresponde a z bajo a.

2.

La primera pareja hallada que cumpla con lo anterior determina a las proyecciones.

En símbolos:

quod erat demonstratum.

Siguiente: Algunas funciones de apareamiento Un nivel arriba: Funciones de apareamiento y Anterior: Funciones de apareamiento y