La Máquina de Turing
Es común en matemáticas que ideas en un principio simples, despliegen progresivamente su riqueza con el paso del tiempo. Sin duda, el concepto de Máquina de Turing es uno de esas ideas. El planteamiento de Alan Turing formaliza nuestra idea intuitiva de procedimiento mecánico que a día de hoy sustenta el comportamiento de un ordenador.
La era de la Computación
A finales del siglo XIX la matemática avanzaba en sus intentos de formalización. Muchos matemáticos buscaban desligar los dominios de la matemática, como la Geometría o la Aritmética, de la intuición y limitaciones de la mente humana. Estaba formalización implicaba la creación de una suerte de lenguaje artificial que permitiese expresar teoremas matemáticos y, en última instancia, cualquier sentencia del lenguaje humano. Tal lenguaje estaría formado por un conjunto de símbolos libres de interpretación contextual, quedando dispuesta la formación de nuevas expresiones según un conjunto de reglas para la manipulación de estos símbolos. Así, no cabría la posibilidad de errores de interpretación ni desavenencias en perspectivas: el símbolos es todo lo que hay.
Un sistema así de generación de expresiones resultaría en un cálculo ciego y mecánico. ¿Qué mejor manera de hacer esto que dejarlo en manos de una máquina?
Contexto histórico
La Máquina de Turing respondía a un intento de alcanzar una solución para uno de los problemas matemáticos más importantes a principios del siglo XX: el Entscheidungsproblem o Problema de Decisión.
A pesar del nombre, cuando Alan Turing propuso su máquina en 1936, nunca pensó en una implementación física de la misma. Simplemente era un ejercicio mental destinado a explorar los límites de lo que podía llegar a ser computado, o lo que es lo mismo, los problemas que pueden resolverse mediante manipulación de signos, tal y como hemos visto en la entrada anterior. Sin embargo, la máquina ha pasado a la historia pues, de entre las formalizaciones matemáticas de lo computable como el Cálculo Lambda de Church o el Sistema de Post, la Máquina de Turing es la más conocida y puede que la más intuitiva de ver. Turing pretendía mostrar con su máquina cuáles son los límites del formalismo matemático, pues, a pesar de la potencia de su maquina ideal, habría problemas irresolubles para ella. Estos problemas serán el tema sobre el que versarán próximas entradas.
El legado de Turing
Aunque la idea de Turing va más allá de la implementación mecánica, es evidente el impacto que ha tenido en el desarrollo de computadores modernos. El comportamiento de un ordenador moderno no deja de ser el de una Máquina de Turing “dopada” (su versión “universal” que veremos más adelante). Mucho más rápido en su cómputo, pero equivalente en sus principios. Eso significa que toda computadora lleva consigo la potencia de cálculo de la máquina y con ello, también sus limitaciones. Ambas propiedades ya fueron vislumbradas por Turing en los años 30, antes de que cualquier ordenador fuese construido.
La Máquina de Turing como modelo teórico
Como ya se ha dicho, la Máquina de Turing es una suerte de experimento mental. Al desatendernos de su implementación, nuestra aproximación a la máquina dejará a un lado los problemas prácticos como la capacidad de memoria o la velocidad de procesamiento. Nos interesa saber lo que la Máquina puede hacer, aunque para ello tarde la edad del Universo. Los problemas que una máquina de Turing puede y no puede resolver serán los mismos aunque usemos muchas de estas máquinas computando de forma paralela.
Al lector que desconozca el tema le sorprenderá la simpleza de la Máquina de Turing. A primera vista, su sencillez no parece hacerla muy útil. Pero, siendo el concepto sencillo, su potencial de desarrollo es inmenso y muy complejo. La Máquina de Turing está pensada para computar cualquier algoritmo, por complejo que este sea. De la misma manera que un algoritmo, la máquina recibirá una información en forma de input, la procesará, y dará un resultado u output.
Descripción de la Máquina de Turing
El dispositivo consta de dos partes: un cabezal lector y una cinta dividida en celdas. Antes de que la máquina comience con su actividad, un número finito de estas celdas ya estarán marcadas con algún signo interpretable por el cabezal. Estos signos iniciales actuarán como el input del dispositivo. Por simplificar el modelo, el alfabeto de signos utilizado será la numeración binaria, 0 y 1, además de un símbolo F que diga a la máquina cuando detenerse. Restringir el número de signos a solo dos no limita las capacidades computacionales del dispositivo, aunque si puede enlentecerlo. Pero como hemos dicho, eso será irrelevante. También hemos dicho que toda computación se realiza en un número discreto de pasos finitos.
La computación se realiza repitiendo una y otra vez este esquema de dos pasos, una celda de cada vez:
– Paso _{i}: el cabezal lee el signo de la celda “escaneada”.
– Paso _{j}: el cabezal escribe un nuevo signo en dicha celda (puede ser el mismo que ya estaba) y se desplaza a una nueva celda, a derecha o izquierda. Solo puede avanzar una celda de cada vez.
El funcionamiento de la Máquina de Turing
Tenemos un alfabeto entendible por la máquina (en este ejemplo la numeración binaria); ahora nos hace falta unas reglas para manipularlo. Ese papel lo asume los estados de la máquina, que funcionan como instrucciones. El cabezal puede asumir un estado de entre un conjunto posible de estados. El papel de este estado q_{i} es determinar qué nuevo símbolo escribir s_{j} y hacía que lado d_{j} desplazarse cuando el cabezal haya leído el signo s_{i} de la celda. También determina que nuevo estado q_{j} adoptará ahora la máquina. Toda esta información está descrita por medio de tres funciones: la función β indica el nuevo estado, la función ς el nuevo signo escrito y la función ρ la dirección a la que se moverá el cabezal.
Vemos que el nuevo estado, el nuevo signo y la dirección de movimiento dependen de los mismos parámetros: el estado previo y el signo leído. El conjunto de signos que deje el dispositivo en la cinta una vez que se haya parado es el resultado de la computación, es decir, el output.
Con esta descripción y el input inicial en la cinta, la Máquina de Turing tiene todo lo necesario para ponerse a trabajar. Describir una computación completa, es decir, conocer de ante mano todos y cada uno de los signos que leerá y escribirá la máquina, los estados que asumirá y el output resultante, será posible si conocemos el input de entrada, las reglas de manipulación, así como el estado inicial de la máquina y la celda leída en el momento de comenzar la computación. El comportamiento futuro de la máquina está así determinado de forma estricta.
La memoria
Las funciones que hemos apuntado nos indican que, el comportamiento de la máquina esta completamente determinado por el estado y el signo leído inmediatamente anteriores. Y esto es así, por muchos pasos que ya haya dado el dispositivo. El dispositivo no retiene ningún tipo de información.
Sin embargo, la cinta actúa como un registro de su actividad. Gracias al movimiento bidireccional de la máquina, la cinta sirve como un suerte de memoria externa a la que acudir en cualquier momento durante la computación. La cinta actúa como el contexto de la máquina que, no solo es útil como medio de implementación del input y el output, sino que también ejerce un papel en el proceso mismo de la computación. A pesar de que el input inicial debe ser finito, el modelo supone que la cinta es infinita. Esto significa que la memoria potencial de la máquina no tiene límite alguno.
Esta memoria ilimitada diferencia a la Máquina de Turing de otros autómatas menos potentes. Si prescindiéramos de la cinta (o hiciéramos que el cabezal solo pudiera moverse en una dirección), la Máquina de Turing sería un simple Autómata de Estado Finito como son, por ejemplo, las neuronas de McCulloch-Pitts. Estos autómatas operan también bajo el esquema input-output, pero son incapaces de guardar registro alguno de su actividad.
Ejemplos de Máquina de Turing
Descrita la máquina, podemos pasar ahora a ofrecer algunos ejemplos que muestren de lo que es capaz. Los ejemplos siguientes están extraídos de la obra de Marvin Minsky Computation: Finite and Infinite Machines.
Contador de Paridad
Empezaremos por una operación sencilla, un contador de paridad. Suministraremos a la Máquina un input que será una cadena de 1s y 0s. La máquina deberá averiguar si el número de 1s es par o impar. Responderá con un 1 si es impar, y un 0 si es par. Solo necesitaremos dos estados q_{0} y q_{1}. Una máquina como esta quedará descrita por una tabla como la que sigue:
Hemos utilizado también 1s y 0s para representar la dirección del movimiento, derecha e izquierda respectivamente. El símbolo F indica a la máquina cuando pararse (P). Recordemos que, para que se trate de una computación efectiva, la máquina debe pararse en algún momento.
En el momento de comenzar la computación, el dispositivo se encontrará en el estado q_{0} y sobre la cinta de la manera que se detalla en la imagen. A partir de ahí la computación continuará de forma autónoma:
El último signo escrito, en este caso 0, es el resultado final de la computación.
La Máquina de Turing y las subrutinas
Ahora plantearemos una tarea mucho más interesante. Se trata de comprobar cuando una fórmula con paréntesis está bien formada, es decir, que todo paréntesis de abertura tenga su pareja de cierre. Por ejemplo ((())()) es una fórmula bien formada, mientras que (() no lo es.
Esta tarea supone un verdadero reto pues realmente se compone de otras subtareas. Cada vez que abre un paréntesis es una nueva tarea. Pero habrá ocasiones en que su pareja de cierre no le suceda inmediatamente. De alguna forma esa tarea debe quedar «en suspensión», pasando a una nueva subrutina con otro paréntesis. Gracias a la cinta, la máquina puede retomar la rutina superior en pasos siguientes. Y esto es así independientemente del nivel de «profundidad» que alcance la anidación de la fórmula.
Comprobador de Paréntesis
Veámoslo con un ejemplo. No será necesario más que tres estados: q_{0}, q_{1} y q_{2}, además de la parada. El alfabeto usado por la cinta será (, ), A y X. La A la usaremos para indicar el inicio y el final de la fórmula. La X será una suerte de marcador que servirá para hacer saber a la máquina que celdas ha registrado ya. La tabla quedará tal que así:
El cabezal comienza en q_{0} sobre un (. A partir de ahí avanza hacia la derecha sin cambiar nada hasta toparse con un ). Entonces lo cambia por X y pasa al estado q_{1}. En ese estado el cabezal avanza ahora hacia la izquierda buscando un (. Cuando lo encuentra, los sustituye por X y vuelve al estado q_{0}, moviéndose hacia la derecha buscando de nuevo un ). El cabezal continua alternando esos dos estados, hacia la derecha con el estado q_{0} y hacia la izquierda con el estado q_{1}.
Esto es así hasta que ocurre una de dos posibilidades. Si en el estado q_{1} vuelve hacia la izquierda y llega hasta el A inicial sin toparse con ningún (, significa que la fórmula no está bien formada, sustituye el A por 0 y se para. En cambio, si en el estado q_{0} avanza hacia la derecha hasta el A del final sin encontrarse con más ), entonces la máquina pasa al estado q_{2} para comprobar si queda algún ( por cerrar. Si llega al A inicial sin encontrarlo, escribe 0 y se para: la fórmula está mal formada. Si se topa con el ( entonces marca 1 y la máquina se para: la fórmula está bien formada.
Turing frente a las Máquinas de Estado Finito
Como hemos dicho, las Máquinas de Estado Finito no tienen una cinta que les sirva de memoria externa. Eso significa que tareas como la de la comprobación de paréntesis no pueden realizarse por uno de estos autómatas. Y cuando decimos que no pueden, nos referimos al ejercicio en general. Podemos diseñar una Máquina de Estado Finito que compruebe un fórmula de paréntesis en particular con éxito. Pero no funcionará para el resto. Solo la Máquina de Turing, capaz de registrar sus pasos y volver sobre ellos es capaz de resolver el problema de los paréntesis sin importar la fórmula que sea.
La Máquina de Turing es el autómata de mayor poder computacional ya que es capaz de resolver este tipo de tareas con subrutinas anidadas unas dentro de otras. Esta facultad tiene también su lado oscuro como iremos viendo en los próximos artículos.
Lecturas Recomendadas
– Minsky, M. (1967) Computation. Finite and Infinite Machines.
– Feynman, R. P. (1996) Conferencias sobre computación.
