Máquina de Turing Artículo 1Una Máquina de Turing es un modelo matemático que consiste en un autómata capaz de implementar cualquier problema matemático expresado por medio de un algoritmo.

Alan TuringAntes de meternos de lleno en esta explicación acerca de la Máquina de Turing, hagamos una pequeña referencia a la persona que la descubrió y que le da nombre.

Alan Turing fue un matemático inglés que vivió durante la primera mitad del siglo XX. Aunque fue un matemático brillante en muchos campos, destacando especialmente en criptografía, su principal interés se centraba en la lógica, que en aquellos momentos se encontraba en plena ebullición gracias al intento de David Hilbert de hallar una formulación de las matemáticas sobre una base estricta de lógica formal. La Máquina de Turing, o Máquina de Computación Lógica como la llamaba él, fue quizás la mayor aportación de Alan Turing a esta tarea y con seguridad su descubrimiento de mayor transcendencia, ya que abrió el camino de la ciencia de la Computación, que a su vez nos lleva al computador que en estos momentos estoy utilizando para escribir esto, o al que usted está usando para leerlo. En definitiva, Alan Turing fue uno de los científicos más importantes de la primera mitad del siglo XX y, sin duda, una de las mentes que más influyó en la manera actual que tenemos de ver el mundo e interactuar con él.

¿qué es un algoritmo? Por suerte esto es mucho más sencillo.

Un algoritmo es un conjunto ordenado de pasos elementales que nos ayudan a resolver un problema. Por ejemplo, si quiero ver el televisor, podría utilizar el siguiente algoritmo para hacerlo:

1. ¿Estoy en el salón?

1.1 No → ir al salón, volver a 1

1.2 Si → pasar a 2

2. ¿Está encendido el televisor?

2.1 No → encenderlo, volver a 2

2.2 Si → pasar a 3

3. ¿Quiero seguir castigando mi cerebro?

3.1 No → apagarlo, FIN

3.2 Si → volver a 2, tú verás lo que haces

Así, un problema matemático expresado por medio de un algoritmo no es más que una afirmación que puede resolverse en un número determinado de pasos elementales. Por

ejemplo, dos más dos es cuatro se puede resolver partiendo del dos, sumándole uno, sumándole otro uno y comprobando el resultado. Como éste es cuatro, la afirmación es verdadera.

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 estados

Para comprender mejor, vamos a ver un simple ejemplo: sea la máquina de Turing capaz de leer o escribir los símbolos 0 y 1 en la cinta (en la definición original de Turing, el número de símbolos a usar podía ser cualquiera, con la única condición de ser un número finito, y no tenían por qué ser números; sin embargo, en aplicaciones prácticas se suelen limitar a estos dos), y que puede tener los estados A, B y C (una máquina de Turing puede tener cualquier número de estados; la única condición es que sea un número finito). Supongamos que definimos la siguiente tabla:

estado símbolo nuevo nuevo sentido de

inicial leído estado símbolo avance

A 0 B 1 DERECHA

A 1 B 0 IZQUIERDA

B 0 A 1 DERECHA

B 1 C 0 DERECHA

C 0 A 0 IZQUIERDA

C 1 C 0 DERECHA

La cual vamos a simplificar de la siguiente manera:

0 1

A B,1,> B,0,<

B A,1,> C,0,>

C A,0,< C,0,>

Hemos puesto los posibles estados en columna, y los posible símbolos en fila, y hemos expresado el nuevo estado, símbolo y sentido todo junto. El sentido lo expresamos con la dirección en la que apunta el símbolo < o >.

Vamos a poner nuestra máquina sobre esta cinta:

cabezal

v

... 0 0 0 0 0 1 0 0 0 0 ...