Máquinas de Turing

Alan Turing es el bien llamado Padre o Abuelo de la computación, el funcionamiento de una máquina de Turing es muy sencillo, es un apuntador con varios estados que se mueve a través de una cinta de datos y cambia el dato, lo mantiene, se mueve, o no, son tantas posibilidades con algo tan simple! 

Aquí una imagen para entenderlo intuitivamente:

Entonces, hay varias posibilidades:

• Poner el mismo número leído 
• Poner un 0
• Poner un 1
• Poner un espacio vacío _

También está:

• No moverse
• Moverse una posición a la derecha
• Moverse una posición a la izquierda 

Y por último:

• Mantenerse en el mismo estado
• Cambiar de estado 

Actualmente, cualquiera puede programar su propia máquina de Turing de manera virtual, y jugar con todas las posibilidades que este mecanismo ofrece, parece muy limitado pero fué una máquina de turing la que logró romper la seguridad de la máquina enigma, que parecía tener un cifrado imposible de quebrar.

Para hacer tu propia máquina de Turing puedes entrar aquí.

La estructura es sencilla:

Estado - Lectura - Escritura - Movimiento - Nuevo estado

0 0 1 r 1 

Que significa, estado 0, si leo un 0, escribo un 1, me muevo a la derecha(right) y cambio al estado 1.

Los estados podrían considerarse como modos que puede tener el apuntador para tomar una cierta decisión según algún dato.

Aquí hay un ejemplo de mi máquina de Turing, una que permite determinar si un número es múltiplo de dos o no, (excepto con el 0).

0 * * r 0

0 _ _ l 1o

1o 0 ) l 2o

1o 1 ( l 2o

2o * : l 2i

2i * _ l 2i

2i _ _ * * ! ;

Explicado de la siguiente manera, empiezo en el estado 0, si leo un 0, pongo 0, me muevo a la derecha y sigo en el estado 0, igual si leo el número 1, dejo un 1, me muevo y  sigo en estado 0. Pero si leo un espacio vacío, es decir, llegué hasta el final de la cadena, me muevo a la izquierda, el último dígito de la cadena, si es 0, osea, si mi número binario es par(porque todos los binarios pares tienen un 0 al final) entonces pongo un cierre de paréntesis, para formar una cara feliz. Si leo un 1 al final, entonces pongo el abrir paréntesis, para la cara triste. Ahora, me muevo una posición a la izquierda, sin importar qué número o símbolo encuentre, pongo dos puntos, para terminar de hacer la carita :) o :(. Y finalmente, cambio al estado 2i, en el que si leo un 1 lo borro, si leo un 0 lo borro, y si leo un espacio en blanco la máquina se detiene, así quito todo y me quedo solo con la carita, eso es todo!. El procedimiento suena complicado pero es increíblemente intuitivo y útil.

Video probando el código: 

(Ignorar música épica)

Trata de hacer tu propia máquina de Turing, y diviértete!

Puedes empezar por sumarle 1 a algún número binario :3