Siguiente: Universalidad en programas-while Un nivel arriba: Universalidad Anterior: La noción de ``Universalidad''

Máquina Universal de Turing

Las máquinas de Turing constituyen el ejemplo por antonomasia de un sistema autorrepresentable. En la sección 3.4.2 vimos una codificación de máquinas de Turing. Esa la utilizaremos en esta sección. Si la cinta de una máquina de Turing tiene inscrita la cadena $x\in\mbox{\rm Dos}^*$, a ese contenido lo podemos codificar mediante la cadena $c(x)\in\mbox{\rm Dos}^*$, donde c es la transformación descrita en la misma sección 3.4.2. Así pues una pareja (M,x), donde M es una máquina de Turing y x es el contenido inicial de la cinta de M (que es propiamente el dato sobre el cual se aplica la máquina M), puede codificarse mediante la cadena $\lceil(M,x)\rceil=\lceil M \rceil\cdot 11111\cdot c(x).$ Una máquina de Turing $\mbox{\it MU}$ se dice ser universal si su efecto es tal que

$$\mbox{\it MU}:\lceil(M,x)\rceil\mapsto\left\{\begin{array}{ll... ...ow$,} \\ \perp & \mbox{\rm en otro caso} \end{array}\right.$$

en otras palabras, si $\mbox{\it MU}$ ``hace correr a la máquina M sobre el contenido x''.

Proposición 4.2   Existe una máquina universal de Turing.

En efecto, es claro que la aplicación de quintuplas sobre la cadena x, o sus transformaciones sucesivas, es un procedimiento completamente descriptible dentro del paradigma de Turing. Por supuesto que es menester probar esta afirmación, y la manera de hacerlo es describiendo a la máquina universal. Sin embargo, dejamos al lector esta tarea como un ejercicio. Como mera guía mostramos a grandes pasos la construccción de una máquina universal de Turing, $\mbox{\it MUT}$. $\mbox{\it MUT}$ posee una cinta semi-infinita. En su primera parte ha de escribir el código de cualquier máquina M que ha de simular, llamemos a esta parte área de programa. Aparece luego el área de trabajo. Aunque esta porción de la cinta de $\mbox{\it MUT}$ es semi-infinita, se puede suponer que se tiene la cinta infinita a ambos lados módulo la reducción de máquinas de Turing a máquinas con cinta semi-infinita vista en el primer capítulo. Así que cualesquiera movimientos en $\mbox{\it MUT}$ han de interpretarse como movimientos módulo aquella reducción. Incorporemos en $\mbox{\it MUT}$ a las quíntuplas necesarias para hacer corrimientos a la derecha y a la izquierda, y para sustituir una cadena por otra. Acaso en este punto será necesario introducir algunos ``apuntadores'' de corrimientos. Además introduciremos símbolos especiales para utilizarlos como delimitador izquierdo del contenido del área de trabajo, delimitador derecho de ese contenido, ``cabeza lectora'' de la máquina M y apuntador a la ``quintupla activa'' en el código de M. Cuando comienza funcionar $\mbox{\it MUT}$, en su área de programa se encuentra el código de una máquina M y en el área de trabajo se encuentra el código de los datos $\mbox{\bf x}$ sobre los que $\mbox{\it MUT}$ ha de aplicar el efecto de M. El funcionamiento de $\mbox{\it MUT}$ se resume más abajo. Reiteramos aquí que $\mbox{\it MUT}$ trabaja sobre códigos. Aunque en la presentación nos referiremos a los símbolos originales, el lector ha de tener en cuenta que, en realidad, son los códigos de esos símbolos los objetos de los que se está hablando.

1.

Al inicio se coloca la pareja $q_0\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)$ a la izquierda de $\mbox{\bf x}$. Tenemos pues una configuración del tipo $q_0\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)x_1\mbox{\bf x}'$ en el área de trabajo, donde x₁ es el primer símbolo de $\mbox{\bf x}$ por la izquierda.

2.

Mientras el área de trabajo sea de la forma $\mbox{\bf x}_{\mbox{\scriptsize\it Izq}}\cdot q\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)s\cdot\mbox{\bf x}_{\mbox{\scriptsize\it Der}}$ y q no sea final, hágase lo siguiente,

(a)

Búsquese en el área de programa la quíntupla que comience con la pareja qs, digamos qsptm, la cual ha de ser la ``quíntupla activa''.

(b)

Sustitúyase la partícula $s_I\cdot q\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)s\cdot s_D$, donde s_I es el primer símbolo de $\mbox{\bf x}_{\mbox{\scriptsize\it Izq}}$ por la derecha y s_D es el primer símbolo de $\mbox{\bf x}_{\mbox{\scriptsize\it Der}}$ por la izquierda, en el área de trabajo por la partícula $s_I\cdot p\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)t\cdot s_D$.

(c)

Cámbiese esa última partícula por $p\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)s_I\cdot t\cdot s_D$ o por $s_I\cdot t\cdot p\cdot\bigl\langle \mbox{\it CabLect}\bigr\rangle(M)s_D$, según $m=\mbox{\rm Izqu}$ o $m=\mbox{\rm Dere}$, o bien declárese a q ``final'' si acaso $m=\mbox{\rm Alto}$.

Como un ejemplo, que no tiene aquí justificación alguna, hay una máquina universal de Turing, reportada en el excelente libro de Penrose, que tiene como índice al número que se muestra en las tablas 3.7 y 3.8, correspondientemente en decimal y en binario (Cfr. [27]).

  

Table 3.7: Código decimal de la máquina universal de Turing.

  

Table 3.8: Código binario de la máquina universal de Turing.

Así pues la clase de máquinas de Turing es un sistema que se autorrepresenta, en el sentido definido en la sección 3.4.3.


Ahora, resulta evidente que la construcción bosquejada en la proposición 3.4.2, puede calcarse para construir una ``máquina universal'' con varias cintas que corra varios procesos en tiempo compartido. Es decir, consideremos m+1 cintas: En la primera, se recibe los códigos de m máquinas de Turing $M_1,\ldots,M_m$ seguidos del código de una lista de datos $\mbox{\bf x}$. Primero, en cada una de las cintas restantes, digamos la i, escribe $M_i\bigl\langle \mbox{\it DelimM\'aq}\bigr\rangle\mbox{\bf x}$. Luego, actúa como la m-ésima potencia cartesiana de la máquina universal, $\mbox{\it MUT}^m$, la cual, a grandes rasgos, tiene como conjunto de estados al producto $Q^m=\underbrace{Q\times \cdots\times Q}_{\mbox{\scriptsize$m$\space veces}}$ y ante cualquier vector $(s_1,\ldots,s_m)$ leído de las cintas, si está en el estado $(q_1,\ldots,q_m)$ entonces actuará pasando al estado $(p_1,\ldots,p_m)$, y, para cada $i\leq m$ sustituye en la cinta i a s_i por t_i y hace el movimiento m_i, siempre que (q_is_ip_it_im_i) sea una quíntupla en $\mbox{\it MUT}$. Ahora, la simulación anterior, puede realizarse con una máquina de Turing de una sola cinta, según se vió en el primer capítulo. Resulta entonces que se cumplen las siguientes dos proposiciones,

Proposición 4.3 (Tiempo compartido)   Para cada $m\geq 0$, existe una máquina de Turing $\mbox{\it MTC}$ tal que para cualesquiera m máquinas de Turing $M_1,\ldots,M_m$ y para cualquier entrada $\mbox{\bf x}$ se tiene

$$\mbox{\it MTC}(\mbox{\bf x})=\left(M_1(\mbox{\bf x}),\ldots,M_m(\mbox{\bf x})\right).$$

Proposición 4.4 (Operando ``inter'' de máquinas)   Para cada $m\geq 0$, existe una máquina de Turing $\mbox{\it MI}$ tal que para cualesquiera m máquinas de Turing $M_1,\ldots,M_m$ y para cualquier entrada $\mbox{\bf x}$ se tiene que $\mbox{\it MTC}(\mbox{\bf x})$ asume el valor asumido por la máquina M_i0 en $\mbox{\bf x}$, si es que esa máquina es la primera, de entre todas las M_i's, en detenerse al actuar sobre la entrada $\mbox{\bf x}$, o bien queda indefinida, $\mbox{\it MTC}(\mbox{\bf x})=\perp$, si todas las M_i's lo quedan con $\mbox{\bf x}$. La máquina $\mbox{\it MI}$ se dice ser el inter de las M_i's y escribiremos $\mbox{\it MI}={\displaystyle\bigwedge_{i=1}^m M_i}$.

Siguiente: Universalidad en programas-while Un nivel arriba: Universalidad Anterior: La noción de ``Universalidad''