Siguiente: La noción de ``Universalidad'' Un nivel arriba: Universalidad Anterior: Codificación de programas por

  
Numerabilidad de la clase de máquinas de Turing

En el primer capítulo vimos que las funciones computables también pueden presentarse como funciones computables por máquinas de Turing. En este sección veremos que las máquinas de Turing conforman una clase efectivamente numerable e introduciremos en términos de ellas el concepto de universal. Sin pérdida de generalidad supondremos de aquí en adelante que el alfabeto de las máquinas de Turing es $A=\{0,1\}=:\mbox{\rm Dos}.$ Al enumerar al conjunto de estados $E=\{q_i\}_{0\leq i\leq n-1}$, cada pareja de la forma $pt\in\mbox{\rm EA}$, donde p es un estado y t es un símbolo en S, se identifica con la cadena $it\in\mbox{\rm Dos}^*$, donde i es el índice del estado p escrito en binario. Recodifiquemos una cadena $x\in\mbox{\rm Dos}^*$ de símbolos 0,1 aplicando la sustitución

$$\begin{array}{rclcrcl} 0 &\rightarrow& 0 &;& 1 &\rightarrow& 10 \end{array}$$ (13)

y denotemos por c(x) al resultado de la sustitución. Así por ejemplo $c((9)_2\cdot 1)=c(1001\cdot 1)=10001010$. Codifiquemos a los símbolos de movimiento mediante la correspondencia

$$\begin{array}{rclcrclcrcl} \mbox{\rm Izqu} &\rightarrow& 110... ...& 1110 &;& \mbox{\rm Alto} &\rightarrow& 11110 \end{array}$$ (14)

En 3.3 y en 3.4 hemos codificado 5 símbolos ``originales'', a saber $0,1,\mbox{\rm Izqu},\mbox{\rm Dere},\mbox{\rm Alto}$, respectivamente por las cadenas 1^k0, k=0,1,2,3,4. Conforme surja la necesidad de aumentar símbolos originales, los codificaremos por cadenas 1^k0 incrementando k según proceda. Cada quíntupla de la forma qsptm queda codificada por la yuxtaposición de c(qspt), el código de m y de un separador de quíntuplas 1⁵0. Una máquina de Turing $M=\left\{qs\rightarrow ptm\right\}_{qs\in\mbox{\rm EA}}$ queda entonces codificada por la concatenación de los códigos de las quíntuplas qsptm que la describen, seguida de un separador de códigos de máquinas 1⁶0. Denotemos a este código por $\lceil M\rceil\in\mbox{\rm Dos}^*$, el cual puede ser visto como la representación en binario de un número natural. Llamemos a este número el código de la máquina M. La codificación que hemos bosquejado es algorítmicamente reversible: Dado un número natural $i\in I\!\!N$,

1.

lo escribimos en binario,

2.

si aparecen más de seis 1's consecutivos el número no representa una máquina de Turing, le podemos asociar la máquina vacía, $\mbox{\rm\sc nil}$, i.e. la que no tiene quintupla alguna. En otro caso

3.

decodificamos a las quíntuplas según el procedimiento inverso al arriba descrito. Si apareciese una inconsistencia, por ejemplo si apareciesen más quíntuplas que las necesarias, le asociamos la máquina vacía.

Tenemos así una enumeración $\{\mbox{\rm m\'aquinas de Turing}\}\rightarrow I\!\!N$ tal que para cualesquiera máquinas de Turing M₁ y M₂, que no sean $\mbox{\rm\sc nil}$, se cumple la equivalencia lógica:

$$c(M_1)=c(M_2)\ \Leftrightarrow\ M_1=M_2.$$

El conjunto imagen de las máquinas de Turing no-vacías bajo la codificación que hemos construído, y que denotamos por $N_{\mbox{\scriptsize\it MT}}=c(\{\mbox{\rm m\'aquinas de Turing}\}-\{$NIL $\})\subset I\!\!N$, consta de los códigos ``legales'' de máquinas de Turing. Como un subconjunto de los números naturales, $N_{\mbox{\scriptsize\it MT}}$ es numerable y, consecuentemente, la clase de máquinas de Turing también lo es. Sea $\Psi_1:I\!\!N\rightarrow N_{\mbox{\scriptsize\it MT}}$ definido como

$$\begin{eqnarray*}\Psi_1(0) &=& \mathop{\rm Min}\{m\vert m\in N_{\mbox{\scriptsiz... ...box{\scriptsize\it MT}}-\{\Psi_1(0),\ldots,\Psi_1(n)\}\right\} \end{eqnarray*}$$

Entonces $\Psi:M\mapsto\Psi_1^{-1}\circ c^{-1}(M)+1$ es una biyección $(\{\mbox{\rm m\'aquinas de Turing}\}-\{$NIL $\})\rightarrow (I\!\!N-\{0\})$, la cual, haciendo $\Psi:\mbox{\rm\sc nil}\mapsto 0$, se extiende a una enumeración de todas las máquinas de Turing. Si $i=\Psi(M)$ diremos que i es el índice de la máquina M y escribiremos M=M_i, así como también, redefiniendo operadores, $i=\lceil M\rceil$ y $M=\lfloor i \rfloor$.
Siguiente: La noción de ``Universalidad'' Un nivel arriba: Universalidad Anterior: Codificación de programas por