Máquinas de Turing

La máquina de Turing es un modelo computacional autómata que de una forma secuencial realiza una lectura/escritura de datos, moviéndose en los dos sentidos, derecha e izquierda.

Kurt Gödel descubrió que ciertos teoremas matemáticos aunque eran ciertos no podían ser probados por personas, entonces aquí entra lo que es el concepto de máquina de Turing, introducido por Alan Mathison Turing, quien quería demostrar que estos teoremas se podían probar de una manera mecánica a través de la máquina de Turing.


La máquina de Turing esta conformada por:

• Una cinta. Una cinta es infinita y esta conformada por celdas o casillas, además sobre ella se realiza la lectura/escritura de los datos. Las celdas en las que en un principio no se ha escrito nada, contienen un carácter especial nulo o vacío que se representa por medio de un 0 o por medio de #. En cada celda se puede escribir un símbolo de un conjunto finito de símbolos llamado alfabeto de la máquina.

• Un cabezal. Hay un dispositivo que se mueve sobre la cinta, el cual contiene un cabezal. El cabezal se puede mover a la derecha y a la izquierda de la posición en que se encuentre de la cinta. Además el cabezal puede leer el contenido de una celda, de una en una, o escribir en la celda cualquier símbolo de su alfabeto .

• Un registro de estado. El registro de estado es el que almacena los estados de la máquina. Lo estados de la máquina son finitos y la máquina no tiene que empezar exactamente con un estado especifico.

• Tabla de acción. Contiene las instrucciones que se realizarán, y al ejecutarse estas instrucciones, se siguen los siguientes pasos:
  

1. Se lee el carácter o símbolo en la posición que se encuentra el cabezal.
2. Se escribe un nuevo símbolo en esa posición (puede ser el mismo que había). El símbolo que se escriba tiene que ser del alfabeto de la máquina y además depende del estado actual y del carácter leído.
3. Se desplaza el cabezal una celda ya sea a la izquierda o a la derecha.
4. Se decidirá cual será el nuevo estado en función del estado actual y del carácter que se acaba de leer. Si la tabla de acción no tiene ya correspondencia con el estado actual y con el símbolo, entonces la máquina ya no realiza su funcionamiento, es decir la máquina detiene su funcionamiento.

Ejemplo de una suma de dos números.
Para realizar la suma de dos números, representaremos a cada número tantos unos como se el tamaño del número, es decir, que si vamos a sumar los números 3 y 5, entonces al número 3 lo representaremos así, 111 (3 veces 1) y al número 5 lo representaremos así 11111 (5 veces 1).

Si tenemos a los dos números que sumaremos, separados por un 0, entonces lo que haríamos para sumarlos, sería cambiar un 1 de cualquier extremo de la cinta a un 0, y después al 0 que esta separando a los dos números lo convertiríamos a un 1. Así, ya tendríamos todos los unos juntos, es decir, ya tendríamos los dos números (3 y 5) juntos, es decir, ya estarían sumados.

Es decir, esto sería así:
Cinta
0000111011111000

Ahora colocaremos un 0 en el primer 1 de la izquierda.
0000011011111000

Ahora, colocaremos un 1 en donde se encuentra el 0 de separación.
0000011111111000

Y ahora que ya tenemos todos los unos juntos, es decir los dos números, 3 y 5, ya tenemos la suma, que es 8 unos, entonces la suma de 3 y 5 es 8.

Veamos esto ahora implementándolo con la máquina de Turing.

Vamos a suponer que la máquina se encuentra del lado izquierdo. Empezamos con el estado A y como el cabezal no se encuentra necesariamente antes del primer número, en este caso en el 111 (3), haremos que el cabezal llegue hasta allí sin alterar los caracteres anteriores a este número. Lo que haremos, será que cuando el cabezal lea un 0 en una celda y este en estado A, entonces se escribirá un cero, es decir no se alterará nada, después se volverá al estado A y se moverá hacia la derecha.

Después al moverse a la derecha se llegará al primer número, es decir al 111 (3), y como nos encontraremos en estado A y llegamos a un 1, entonces se cambiará al 1 por un 0 (este 1 es el único que debemos cambiar a 0 como lo mencione anteriormente, cambiar un 1 de cualquier extremo de la cinta a un 0). Como seguiremos a la derecha para llegar al 0 de separación, nos encontraremos con mas unos, entonces como nos encontramos en estado A, esos unos se convertirían en ceros, pero no queremos esto, ya que queremos juntar los unos, para realizar la suma de los dos números, entonces lo que haremos será añadir un nuevo estado B, que cuando se encuentre un 1 en estado A, se deberá pasar a estado B.

Ya cuando se convirtió en 0 el 1, el estado A se pasa a estado B, entonces se seguirá desplazando el cabezal hacia la derecha hasta llegar al 0 de separación, sin alterar nada y cuando se va desplazando el cabezal por cada celda y se encuentra un 1 en estado B, entonces este 1 se convertirá en un 1 y se pasará el cabezal hacia la derecha y se pasará de nuevo a estado B. Y ya cuando llegue a una celda en donde encuentre el carácter 0, significa que ha llegado al 0 de separación y si esta en estado B, entonces este 0 se convertirá a 1.

Ahora que la suma esta terminada, entonces la máquina deberá de parar y pasar a un estado correspondiente, al cual llamaremos @. Cuando la máquina llega a este estado, ya no leerá ninguna celda mas y tampoco ya no se desplazará, entonces la máquina se detendrá.

El programa de este ejemplo con la máquina Turing es así (donde > es desplazarse hacia la derecha):

           0         1 

  A      0,A,>     0,B,> 

  B      1,@       1,B,> 

Las páginas en las que me base son las siguientes:

Computación: Máquina de Turing
Máquina de Turing
Máquinas de Turing

Videos sobre la máquina de Turing

Máquina de Turing (1)

Máquina de Turing (2)

Saludos.