La Máquina Universal de Turing
La Máquina Universal de Turing es un dispositivo programable, es decir, puede operar todo algoritmo computable. Mientras Turing planteaba teóricamente esta máquina, el ingeniero alemán Konrad Zuse (en la imagen) construía su monstruosa máquina Z1, la que sería la primera computadora programable.
Descripción de la Máquina Universal de Turing
La Máquina Universal de Turing o máquina U es un concepto destinado a unificar todas las funciones matemáticas computables. U es una Máquina de Turing como cualquier otra, con sus instrucciones, su cabezal y su cinta. La novedad que aporta es que está especificada de forma que le es posible imitar cualquier otra Máquina de Turing, ofreciéndonos el mismo output que lo haría esa misma Máquina. En otras palabras, U es una máquina programable. Este artículo estará destinado a estudiar esta hipotética máquina universal y sus capacidades de cómputo. Veremos que la Máquina U es una realidad demostrada por Turing hasta el punto que los ordenadores modernos son sus legítimos descendientes.
Como hemos visto con anterioridad, el comportamiento de una Máquina de Turing estaba determinado por una tabla. Esa tabla son las instrucciones de T y las llamaremos “descripción de T ” o también d_{T}. Para especificar exactamente el comportamiento de T, además de d_{T} y, evidentemente, la cinta m que le serviría de input, deberemos especificar también en qué estado comienza la computación y sobre qué celda en concreto.
EL alfabeto de U
Toda esta información deberemos de proveerla a U para que imite exactamente el comportamiento de T. Es decir, U recibe como input la descripción completa de la Máquina T que procede a imitar. Para ello, deberemos utilizar un lenguaje que U pueda entender. Recordemos que toda Máquina de Turing opera con un alfabeto compuesto por varios signos. Es posible que U no use el mismo alfabeto que T. Esto no supondría ningún problema de principio. Debemos de codificar las instrucciones de manera que U pueda comprenderlas. Guiados por el espíritu didáctico que insufla este artículo, en nuestro ejemplo T y U comparten alfabeto: la numeración binaria.
Descripción de T
Tomemos de ejemplo el sencillo contador de paridad del anterior artículo. Recordemos la tabla donde vienen especificadas sus instrucciones.
Toda Máquina de Turing se puede describir como un conjunto de quíntuplas de la manera que sigue:
Como puede verse en la tabla, nuestro contador de paridad tiene seis de esas quíntuplas. La primera de ellas por ejemplo sería:
Para codificarlas de manera que U pueda comprenderlas, simplemente colocamos esas quíntuplas en la cinta, separadas por un signo. Aquí usaremos X.
Y con esto ya tendríamos nuestra descripción de la máquina d_{T} lista para introducirla en la cinta de U.
Tal y como hemos planteado aquí d_{T}, se espera que U sea capaz de operar con símbolos como X o P. Aun así, siempre podríamos codificar esos símbolos en lenguaje binario para que U solo opere con 1s y 0s, pero sería más engorroso de visualizar.
Espacio de Trabajo de U
El comportamiento de una Máquina de Turing está determinado por parámetros de la operación inmediatamente anterior. Esto dificulta la acción de la máquina, dado que, para imitar la operación de T sobre una celda, U debería «recordar» esos parámetros. Sin embargo, podremos reservar una sección de la cinta de U en la que hagamos que la máquina anote en qué estado Q_{iT} estaría y que signo S_{iT} habría leído la máquina T en cada operación con una celda. Esto es equivalente a las memorias RAM de los ordenadores modernos o incluso a nuestra propia Memoria a Corto Plazo: información necesaria para llevar a cabo una tarea y que se evoca en el momento de la ejecución haciéndola más accesible durante un periodo limitado de tiempo.
La cinta de U
Este espacio de memoria de trabajo estará reservado para toda cinta de U, sea cual sea la máquina T que se disponga a imitar. Del mismo modo, la posición del cabezal de U comenzará siempre en la misma posición sobre la cinta. De esta manera haremos que la computación que realice U sea una función determinada por solo dos parámetros, la cinta de T, que llamamos m, y la descripción d_{T}.
Con estas secciones ya podemos tener una idea clara de cómo sería la cinta de una máquina U que ejecuta un programa descrito por la máquina T. Como cualquier otra Máquina de Turing, la cinta de U es infinita (en la imagen, hacia el lado izquierdo), pero el input necesario para ejecutar la operación no.
La Máquina de Turing como función matemática
Para continuar con nuestra exploración de la Máquina de Turing convendrá que asociemos el concepto con la idea de función matemática. Una función es una regla que asocia un par de valores (x,y). A x la denominamos argumento, y tras aplicarle dicha regla, nos ofrece un valor y para cada valor de x, uno y solo un valor y. De la misma manera, una Máquina de Turing particular ofrece uno y solo un output cuando le introducimos un input. El resultado dependerá tanto del input introducido como de las instrucciones que defina la máquina. Una Máquina de Turing es pues equivalente a una función.
Denominamos T a una Máquina de Turing arbitraria, y m a la cinta. Simbolizaremos la acción de dicha máquina sobre esa cinta como la función T(m). Esta acción nos devolverá un resultado p.
Como en este caso nos devuelve un output, decimos que T(m) es equivalente a una función computable.
Como desarrollaremos más adelante, habrá ocasiones en las que un determinado input o una configuración de la máquina provoque que esta quede colgada en una rutina, repitiéndola una y otra vez. Bajo estas circunstancias, la máquina no acabará nunca por darnos un resultado p. En ese caso diremos que T(m) no es computable.
Funcionamiento de la Máquina Universal de Turing
El funcionamiento de U será bien simple. La máquina realizará esta operación para cada celda de m que registra. Una a una registrará las celdas como lo haría T. En cada operación, la celda que esté registrando estará marcada con un signo C para distinguirla.
La operación comienza con el cabezal posicionado en el símbolo X que da inicio a d_{T}. La máquina comienza buscando cual quíntupla coincide con el símbolo y estado que se encuentran en el espacio de trabajo y que indican el estado a partir del cual comienza a operar la máquina. Durante el recorrido, en dirección diestra, el cabezal cambia todos los 1s y 0s por As y Bs respectivamente. La máquina graba en el espacio de trabajo el nuevo estado que asumiría T y el nuevo signo que escribirá. También recordará la nueva dirección. Una vez hecho esto, retorna a la X inicial.
Después de esto se moverá, esta vez hacia la izquierda, cambiando todo por As y Bs, hasta toparse con la celda de C. Lo sustituye por un signo que registre la dirección de movimiento D_{jT} y retorna de nuevo al espacio para «recordar» qué nuevo signo debe escribir sobre C. Al volver a la celda, escribe el nuevo signo sobre C, se mueve en la dirección indicada, y graba una nueva C que indique a la máquina cual será la próxima celda a escanear.
Esta operación será larga y tediosa. Pero ya hemos dejado claro que eso no nos importa mientras la máquina pare en algún momento con un resultado.
Conclusión
Estas instrucciones que hemos perfilado aquí requerirán que la máquina U esté correctamente programada para imitar a cualquier T posible. Para los propósitos de esta serie de artículos, no nos interesará conocer sus especificaciones d_{U}. Pero numerosos autores han llegado a proponer su propia Máquina Universal de Turing, siempre buscando utilizar el lenguaje más elemental y el número de estados más reducido posible. Para el lector interesado, remito a la obra The Essencial Turing que recopila algunos de los escritos del matemático.
Para los objetivos de esta serie, deberíamos quedarnos con el hecho de que, resolver una función computable, o lo que es lo mismo, imitar cualquier computación efectiva de una Máquina de Turing, es en sí misma una función computable. En el artículo siguiente veremos que implicaciones tiene esto para los límites de lo que puede llegar a ser computable.
Lecturas Recomendadas
– Minsky, M. (1967) Computation. Finite and Infinite Machines.
– Feynman, R. P. (1996) Conferencias sobre computación.
– Turing, A., editado por Copeland, J. (2004) The Essencial Turing: Seminal Writings in Computing, Logic, Philosophy…,
