maquina de turing

Maquina de turing
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 demodelos matemáticos, autómatas y, por último, de Máquinas de Turing.
“Una Máquina de Turing es unmodelo 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ónconcreta 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 degeneralizar 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 modelomatemá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 modelomatemá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áquinateó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 estadosegú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 cintatiene 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 denominafunció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 dosagujeros 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 denuevo.
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é...