Siguiente: Codificación de secuencias Un nivel arriba: Función de Gödel Anterior: Definiciones básicas

Codificación con la función $\beta$

Lema 3.1   Los números 1+(i+1)n!, $i=0,\ldots,n-1$ son primos relativos a pares.

Demostración: Sean i,j tales que $0\leq i<j\leq n$. Para ver que

(1+(i+1)n!,1+(j+1)n!)=1

basta probar, por la proposición 3.3.4, que $\forall x:$

$$1+(j+1)n!\vert x(1+(i+1)n!)\ \Rightarrow\ 1+(j+1)n!\vert x.$$

Para esto, observamos primero que, naturalmente, (1+(j+1)n!,n!)=1, y j-i|n!. Las siguientes implicaciones son entonces todas verdaderas:

$$\begin{eqnarray*}&&1+(j+1)n!\vert x(1+(i+1)n!)=x(1+(j+1)n!)+x(i-j)n!\\ &\Right... ...htarrow& 1+(j+1)n!\vert xn! \\ &\Rightarrow& 1+(j+1)n!\vert x \end{eqnarray*}$$

quod erat demonstratum

Teorema 3.3   Para cada sucesión finita de enteros $\mbox{\bf x}=(x_0,\ldots,x_{k-1})\in N^*$ existen dos enteros x₀,y₀ tales que

$$\forall i: 0\leq i < k\ \Rightarrow\ \beta(x_0,y_0,i)=x_i.$$

Demostración: Sea

$$n=\mathop{\rm Max}\left[\{x_i\vert i=0,\ldots,k-1\}\cup\{k-1\}\right].$$

Para cualquier pareja de índices distintos i,j se tiene que los números 1+(i+1)n!,1+(j+1)n! son primos a pares. Por el Teorema Chino del Residuo resulta que

$$\exists z\ \forall i<n: z\equiv x_i\mbox{\rm mod }(1+(i+1)n!).$$

Tomamos pues x₀=z y y₀=n!.


La pareja (x₀,y₀) es el código mediante la función $\beta$ del vector $\mbox{\bf x}$. Escribiremos $(x_0,y_0)=\mbox{\it cod}_{\beta}(\mbox{\bf x})$. Ejemplo. En la tabla 3.5 mostramos la codificación de los primeros quince segmentos de los números naturales,

$$\mbox{\bf n}=\{0,\ldots,n-1\}.$$

  

Table: Codificación mediante la función $\beta$ de las sucesiones $\mbox{\bf n}$ con $n=2,\ldots,15$.

En la tabla 3.6 mostramos la decodificación de las parejas obtenidas en la tabla 3.5. El i-ésimo renglón corresponde a la i-ésima pareja (x_i,y_i) de la tabla 3.5. En la casilla correspondiente a la columna j-ésima aparece el valor $\beta(x_i,y_i)$, por tanto, en cada renglón n, aparece, hasta la posición n-1, la sucesión $\mbox{\bf n}$.

  

Table 3.6: Decodificación de las parejas obtenidas en la tabla 3.5.

Siguiente: Codificación de secuencias Un nivel arriba: Función de Gödel Anterior: Definiciones básicas