Siguiente: Primera lista de ejercicios Un nivel arriba: Codificación de programas-while Anterior: Codificación de programas y

Observaciones sobre la codificación

Denotemos por $\mbox{\it Alf}^*$ al conjunto de tiras sobre el alfabeto de los programas-while .

1.

$\lceil\cdot\rceil:\mbox{\it Alf}^*\rightarrow N$ es una función

(a)

efectivamente calculable, es decir, dada una tira cualquiera $P\in\mbox{\it Alf}^*$ se obtiene de manera procedimental su código $\lceil P\rceil$,

(b)

inyectiva, pues para que $\lceil P_1\rceil=\lceil P_2\rceil$ es necesario que P₁=P₂, cualesquiera que sean las tiras $P_1,P_2\in\mbox{\it Alf}^*$, y

(c)

que no es suprayectiva, pues la representación binaria de cualquier número en la imagen de $\lceil\cdot\rceil$ ha de tener una longitud que es un múltiplo de 5 y en cada posición múltiplo de 5, contada de derecha a izquierda, ha de estar ``prendido'' el bit correspondiente. En otras palabras, un número está en la imagen de $\lceil\cdot\rceil$ si y sólo si al escribir a ese número en base 32=2⁵, sólo aparecen los dígitos que, en decimal, están entre 16 y 26 inclusive.

2.

Puesto que la clase de los programas-while es un subconjunto propio de $\mbox{\it Alf}^*$ tenemos que el conjunto de códigos de programas-while , $N\subset I\!\!N$, es un subconjunto propio de la imagen de $\lceil\cdot\rceil$.

3.

Sin embargo, dado $n\in I\!\!N$ es algorítmicamente decidible si acaso existe un programa-while P tal que $n=\lceil P\rceil$. En efecto, dado n se puede calcular, mediante la ``división larga'' de enteros, la representación en base 32 de n y, obtenida ésta, hacer la conversión a una palabra $p_n\in\mbox{\it Alf}^*$ mediante la codificación descrita en la tabla 1.6. Luego, mediante un autómata de pila, se puede ver si acaso p_n se ajusta a la gramática de los programas-while .

4.

El procedimiento descrito en el punto anterior para obtener $p_n\in\mbox{\it Alf}^*$ dado $n\in I\!\!N$ es un procedimiento efectivo para calcular la inversa de la codificación $\lceil\cdot\rceil$.

5.

La codificación $\Phi$ mencionada inmediatamente después de la observación 1.9.1 es, precisamente, la codificación $\lceil\cdot\rceil$ restringida a la clase de programas-while .

Para cada programa-while P, el número $i_P=\lceil P\rceil$ es el índice del programa P. Consecuentemente, P se dice ser el i_P-ésimo programa-while P=P_iP. Ahora bien, las funciones computables son las que se calculan mediante programas-while . Por tanto, podemos generalizar la noción de índice a las funciones computables como sigue: $\forall n\geq 0$ y para cada $i\in N$, el i-ésimo programa-while P_i calcula a la función

$$\begin{eqnarray*}f^{(n)}_i:I\!\!N^n &\rightarrow& I\!\!N\\ (x_1,\ldots,x_n) &\mapsto& y=f^{(n)}_i(x_1,\ldots,x_n) \end{eqnarray*}$$

donde y es el valor obtenido como sigue:

1.

Si $X_1,\ldots,X_k$ es la lista de variables de P_i, la instanciamos con $\mbox{\bf x}$, donde, en función de cómo se compare a n con k, la instanciación se hace como sigue:

$$\begin{array}{l} k\leq n:\forall j\leq k(X_j:=x_j) \vspace{2... ...X_j:=x_j)]\land[\forall j\in]\!]n,k]\!] (X_j:=0)]. \end{array}$$

2.

El valor que queda en la última variable X_k cuando termina P_i, si acaso terminare, es el asignado a y.

Si $f:I\!\!N^n\rightarrow I\!\!N$ es computable y f=f⁽ⁿ⁾_i entonces i se dice ser un índice de f.

Proposición 9.1   Toda función computable tiene una infinidad de índices.

En efecto, sin entrar en minucias, tenemos que dos programas-while calculan a una misma función si, por ejemplo, uno posee variables ``mudas'', es decir, irrelevantes para el cálculo, que no aparecen en el otro, o bien si uno posee ``instrucciones ociosas'', digamos (x++;x-;)^* y, en lo demás, coincide con el otro programa.
Siguiente: Primera lista de ejercicios Un nivel arriba: Codificación de programas-while Anterior: Codificación de programas y