¿Qué es una Máquina de Turing? (ii)

En el artículo anterior hablamos de problemas matemáticos y algoritmos, haciendo uso de una definición algo compleja, pero que nos sirvió para introducir estos conceptos fundamentales a la hora de comprender qué es una Máquina de Turing. Hoy vamos a dar un paso más y hablaremos de modelos matemáticos, autómatas y, por último, de Máquinas de Turing.

“Una Máquina de Turing es un modelo matemático“
“Modelo matemático” es una expresión de esas que se utilizan con cierta frecuencia pero que pocas veces nos paramos a pensar qué significa. Y aunque parezca algo complicado, en realidad se trata de un concepto bastante sencillo.

Un modelo matemático es un conjunto de reglas que “encajan” en la explicación y resolución de un problema, es decir, que modelizan una situación concreta para poder explicarla y encontrar el modo de resolverla. Más aún, se podría decir que un modelo matemático es un conjuto de reglas capaces de generalizar y resolver un problema matemático concreto y cualquier otro de su misma naturaleza que se pueda plantear.

El ejemplo más simple que se me ocurre es, ante el problema “¿cuántas manzanas tenemos si yo tengo tres y tú tienes dos?”, el modelo matemático a aplicar es el que comprende a los números naturales (1,2,3,4,…) y su suma finita. Así, cuando nos encontremos con otro caso similar, como por ejemplo averiguar cuántos años suman las edades de tres personas, basta con aplicar este modelo para averiguarlo, es decir, sumar la edad de cada uno de ellos. Tan fácil como parece.

Ahora la afirmación una Máquina de Turing es un modelo matemático cobra significado: nos dice que es una forma de resolver cierto tipo de problemas, que además funciona para cualquier problema de la misma naturaleza. Como a estas alturas se podrán imaginar, uno de los problemas que será capaz de resolver la Máquina de Turing es el Problema de la decisión.

“Una máquina de Turing es un autómata”
En matemáticas, un autómata es lo que se conoce como una máquina teórica, es decir, un dispositivo cuyo funcionamiento se estudia sin necesidad de construirlo realmente. En concreto un autómata es una máquina teórica que lee unas instrucciones en forma de símbolos y cambia de estado según éstas.

Vamos a tratar de explicar esto mediante un sencillo ejemplo. Imaginemos que nuestro autómata es un robot que sólo sabe hacer tres cosas: tumbarse, levantarse y decir “he quedado con unas robopilinguis”. Estas tres “cosas” serían los tres estados en los que se puede encontrar nuestro autómata.

Imaginemos también que el robot tiene una abertura por la que podemos introducir una cinta de papel perforada, y un dispositivo que lee si cada tramo concreto de la cinta tiene un agujero o no. Supongamos que el mecanismo del robot funciona de tal forma que cuando la cinta tiene un agujero, el robot se levanta, cuando tiene otro más, el robot habla y cuando no lo tiene, se sienta (esta serie de instrucciones de funcionamiento en función de las instrucciones de entrada forman lo que se denomina función de estado del autómata) Por último, supongamos que el robot está tumbado antes de leer la primera instrucción.

Entonces si introducimos una cinta que conste de dos agujeros y un espacio sin perforar, que representamos por OOX, el robot leerá el primer agujero y se levantará, leerá el segundo y dirá “he quedado con unas robopilinguis”, y al llegar al espacio sin perforar se volverá a tumbar.

Si ahora introducimos una cinta con la instrucción OXOOOX, el robot se levantará, se tumbará, se volverá a levantar, dirá dos veces su célebre frase, y acabará tumbado de nuevo.

Esto es básicamente un autómata: un dispositivo que lee (implementa) unas instrucciones (algoritmos), y cambia su estado en función de estas (se sienta, se levanta o dice la frase). Pero para un matemático, que el dispositivo sea un robot que vaya a cuerda o un computador cuántico es completamente indiferente, lo importante es el estudio de qué algoritmos puede implementar, qué simbología y qué gramática se puede utilizar para representar estos algoritmos y cómo hacer que el autómata llegue a un estado determinado partiendo de un estado inicial.

Este ejemplo puede parecer demasiado sencillo, pero háganse a la idea que con los actuales recortes en los presupuestos dedicados a I+D es probable que a lo más que podamos llegar en este país es a construir robots gamberros como este.

Pero, ¿qué es una Máquina de Turing?

Después de esta pequeña introducción en el mundo de la Computación, por fin nos encontramos en disposición de comprender lo que es una Máquina de Turing y cómo funciona.

Si recopilamos lo que hemos visto hasta ahora, ya sabemos lo que es un modelo matemático, un autómata, un problema matemático, un algoritmo y lo que significa implementar, además de que todo esto debe de tener que ver con el Problema de la decisión, porque por algo se habrá mencionado. Así que sólo nos falta meterlo todo en la coctelera y sacar la Máquina de Turing de ella, así que vamos al lío.

Una máquina de Turing es un autómata que consta de una cabeza lectora y una cinta infinita en la que la cabeza puede leer símbolos, borrarlos, escribirlos y moverse a la derecha o a la izquierda. Por supuesto también  consta de una función de estado que determinará los cambios de un estado a otro que se deben producir en función de las instrucciones que reciba.

Representación artística de una Máquina de Turing

Éste aparato tan sencillo (y tan parecido a un radiocasete) tiene una propiedad sorprendente, y es que es capaz de implemetar cualquier problema matemático que se nos ocurra, con la única condición de que éste se pueda expresar por medio de un algoritmo (que recordemos que no es más que estructurar el problema en un número de pasos determinados) Por tanto, podremos escribir una cadena de símbolos que represente el problema de manera que la máquina lo pueda leer y, como además también puede escribir y borrar, cuando vayamos de un paso a otro del algoritmo podrá recordar el paso en el que se encuentra en cada momento para así poder dar el siguiente en la dirección correcta.

Si nos fijamos bien, es sencillo encontrar una analogía entre una Máquina de Turing y un computador moderno. En un computador, tenemos un dispositivo de lectura y borrado que interpreta los datos grabados en un soporte (hardware) sobre el que puede además borrar, escribir y moverse. Además, este dispositivo dispone de un código (software) que, según sean las instrucciones de entrada, proporciona una salida determinada en forma de imagen en una pantalla, cálculo matemático, sonido, etc.  La única diferencia esencial es que el soporte de información no es infinito, pero eso en la práctica no es un gran problema porque en la mayoría de los casos nuestras necesidades de computación son finitas.

Por tanto, podemos identificar el hardware de un computador con la cabeza lectora y la cinta, mientras que el software serían las instrucciones de la cinta y la función de estado de la Máquina de Turing.

Ahora sí es fácil ver las implicaciones que el estudio teórico de la Máquina de Turing tiene en el avance de la Informática, pues nos permite, entre otras cosas, comprender los límites de lo que podemos esperar que haga una computadora y lo que no.

La Máquina de Turing y el Problema de la decisión

Lo más curioso de todo esto es que, en realidad, cuando Alan Turing descubrió su máquina no lo hizo buscando la forma de inventar un ordenador personal (al menos no era su principal motivación), sino tratando de resolver el Problema de la decisión.

Alan Turing probó que cualquier método de implemetar un problema se puede siempre simplificar a una Máquina de Turing, es decir, que su máquina era algo así como “la madre de todos los métodos”. Por otro lado, también probó que no se puede construir una Máquina de Turing capaz de determinar si un problema se va a poder resolver o no y, por tanto, quedó demostrado que no hay ningún sistema para decidir si un problema matemático tiene solución o no, ya que si lo hubiera, nos encontraríamos con la paradoja de que el sistema se podría reducir a una Máquina de Turing que sabemos a ciencia cierta que no existe.

En definitiva, lo más interesante de la Máquina de Turing desde el punto de vista de un matemático es que nos señala la existencia de una limitación en el universo de las matemáticas: la imposibilidad de saber, a priori,  si un problema matemático va a poder ser resuelto o no. Así, la próxima vez que su jefe le exija una respuesta antes de ponerse a trabajar en la pregunta, podrá contestarle que, gracias al Problema de la decisión, no sólo no puede dársela aún, sino que debe hacerse a la idea de que a lo mejor ésta no existe.

Para que después digan que las matemáticas puras no tienen aplicaciones en la vida real…

Sevilla, Octubre de 2009

Lo publicó Javier Oribe en  El Máquina de Turing.