Máquinas Turing

Laboratorio de Lenguajes de Programación

En esta entrada les hablaré sobre las máquinas turing.

Este concepto se intridujo por Alan Turing en un trabajo llamado "On computable numbers, with an application to the Entscheidungsproblem" en el cual se hablaba sobre si las matemáticas tienen un método que se pueda aplicar para cualquier sentencia matemática y nos diga si esta sentencia es verdadera o no.

Una máquina de turing consiste en una cinta infinita, dividida en casillas, sobre ella se encuentra un dispositivo que se puede desplazar a lo largo de ella de casilla en casilla. Dicho dispositivo tiene un cabeza que sirve para leer, borrar o imprimir símbolos que se encuentren escritos en la cinta. Contiene también un registro que almacena un estado que es definido por un símbolo. Estos símbolos no pueden ser iguales a los que están escritos en la cinta. En la cinta solo se pueden poner el símbolo 0 y 1 y el registro de estados los símbolos se escriben con letras mayúsculas.

La máquina funciona de forma mecánica y secuencial. Lee el símbolo que hay en cada casilla, después toma el estado en que se encuentra cada uno y con estos datos entra a una tabla, la cual lee el símbolo que debe escribir en la cinta, el nuevo estado en el que estará y a donde debe desplazarse, derecha o izquierda.

Por ejemplo, si tenemos lo siguiente:

Esto se puede escribir de la siguiente forma:

Como pueden ver en esta última tabla se pusieron los posibles estados en la primera columna y los posibles  símbolos introducidos en la cinta en la primera fila. Y también pusimos el nuevo estado, nuevo símbolo y dirección la cual es derecha(>) o izquierda(<).

Se pone la máquina sobre la cinta, supongamos la cinta y el símbolo donde está apuntando la v es el que se conoce como cabezal que como ya dijimos es el que va leyendo, borrando o imprimiendo.

        cabezal

              v

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

Se indica el estado  actual encima del cabezal partiendo del estado A.

1.
             A
              v   
... 0 0 0 0 0 1 0 0 0 ...           El estado es A y se está leyendo un 0, después debemos   de cambiar el estado a B, escribir un 1 y movernos a la derecha.

2. 
                B
                 v
... 0 0 0 1 0 1 0 0 0 ...          El estado es B y se lee un 0, debemos de cambiar el estado a A, escribir un 1 y movernos a la derecha.


3.
                    A
                    v
... 0 0 0 1 1 1 0 0 0 0 ...      El estado es A y leemos un 1,  debemos cambiar el estado a B, escribir un 0 y movernos hacia la izquierda.


4.
                 B
                 v
... 0 0 0 1 1 0 0 0 0 0 ...       El estado es B y leemos un 1, debemos cambiar al estado B, escribir un 0 y movernos hacia la derecha

La ejecución de esta máquina sigue indefinidamente, rellenando la cinta con 1 y 0. En realidad una máquina Turing útil deberia tener un estado en donde pudiera detenerse, este estado se alcanzaría como cualquier otro y se detendría cuando se haya terminado el cálculo. A pesar de esto, está máquina tiene múltiples usos útiles como sumar dos números, multiplicarios, copiarlos, entre otras cosas.

Estas máquinas plantean una deducción muy curiosa, como pueden realizar cualquier trabajo computable, es posible programarlas para que simulen el comportamiento de un ordenador muy potente. Ya que esta puede ser codificada en cualquier ordenador, por más pequeño que sea, podríamos tener una máquina Turing en casa que simule un super ordenador. 

Les dejo el link a las diapositivas de la Dra. Schaeffer donde explicó este tema.

Y también un video donde se muestra como trabaja la máquina Turing está en inglés pero esta muy interesante, ojala tengan tiempo para verlo. Saludos:)