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
Hubiera sido informativo ver la tabla de transiciones de la máquina que se ejecuta en el ejemplo. Ahora no queda muy claro bajo qué regla se mueve en la cinta y cómo se decide qué queda escrito en ella. Te pongo un punto extra.
ResponderEliminar