Máquinas de Turing (puntos extras)

Máquina de Turing

La Turing es un dispositivo que nos transforma un "INPUT" en un "OUTPUT" después de algunos pasos. Tanto el INPUT como el OUPUT que tiene números en código binario (ceros y unos). 

Al principio la máquina de Turing trataba en una cinta infinitamente larga con unos y ceros que pasa a través de una caja que era tan fina que solo el trozo de cinta que ocupa un bit (0 ó 1) está en su interior. La máquina tenia una serie de estados internos finitos que también se pueden enumerar en código binario.

Para poder hacer un algoritmo, la maquina se inicializa en un estado interno aleatorio. Después, se pone en marcha y la maquina lee el bit que esta en ese momento en el interior y ejecuta alguna operación con ese bit lo cual puede ser que se cambie o se quede así dependiendo del estado interno. 

Después se mueve para la derecha o hacia la izquierda, y vuelve a repetir el mismo procedimiento de la misma manera. 

Al final se para, dejando el resultado al lado izquierdo por ejemplo.

PASO	ESTADO	CINTA
1	s1	11
2	s2	01
3	s2	010
4	s3	0100
5	s4	0101
6	s5	0101
7	s5	0101
8	s1	1101
9	s2	1001
10	s3	1001
11	s3	10010
12	s4	10011
13	s4	10011
14	s5	10011
15	s1	11011
PARADA

Estas maquinas realizan estos proceso por medio de un bucle, en el estado inicial s1, reemplaza el primer 1 con un 0, y pasa al estado s2, con el que avanza hasta la derecha, saltando los símbolos 1 hasta un 0 (que tiene que existir), cuando lo encuentra pasa a ser s3, con este estado avanza saltando todos los 1 hasta encontrar otro 0 (la primera vez no habría ningún 1). Una vez en el extremo derecho, añade un 1. Después comienza el proceso de retorno; con s4 vuelve a la izquierda saltando los 1, cuando encuentra un 0 (en el medio de la secuencia), pasa a s5 que sigue a la izquierda saltando los 1 hasta el 0 que se escribió al principio. Se reemplaza de nuevo este 0 por 1, y pasa al símbolo siguiente, si es un 1, se pasa a otra iteración del bucle, pasando al estado s1 de nuevo. Si es un número 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado su proceso