Esta máquina es un autómata que se mueve sobre una secuencia lineal de datos; puede leer un solo dato de la secuencia a la vez y realiza ciertas acciones en base a una tabla que contiene su estado actual (interno) y su último dato leído; de acuerdo con esto puede escribir nuevos datos, recorrer la secuencia en ambos sentidos (izquierda o derecha) y cambiar su estado dentro de un conjunto finito de estados definidos.
La máquina de Turing consta de un cabezal lector/escritor, una cinta infinita en la que el cabezal lee el contenido, borra y escribe un nuevo valor; sus operaciones se limitan a: avanzar el cabezal lector / escritor a la izquierda, y avanzar el cabezal avanzar el cabezal lector / escritor a la derecha; también existe un registro de estado que almacena el estado de una maquina (su número de estados posibles es finito y no se exige un estado en especial para iniciar la maquina). Existe una tabla de acción que contiene las instrucciones de lo que hará la máquina y la ejecución de de cada instrucción en la tabla de acción consta de cuatro pasos:
o Leer un carácter en la posición actual.
o Escribir un nuevo símbolo en esta posición (puede ser el mismo que había). El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual.
o Desplazar el cabezal una celda a derecha o izquierda (R/L); en algunos modelos el desplazamiento puede ser nulo (detener H).
o Decidir cuál será el nuevo estado en función del carácter que se acaba de leer y del estado actual. Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.
La tabla quedaría así:
+---+---++---+---+---+
| S | R || W | M | N |
+---+---++---+---+---+
| 0 | 0 || 0 | R | 0 |
| 0 | 1 || 1 | R | 1 |
| 1 | 0 || 1 | R | 2 |
| 1 | 1 || 1 | R | 1 |
| 2 | 0 || 0 | H | 2 |
| 2 | 1 || 0 | H | 2 |
+---+---++---+---+---+
S = Estado actual
R = Carácter leído
W = Carácter escrito
M = Dirección del movimiento
N = Nuevo estado
Algo que vale la pena subrayar es que el diseño de Turing lleva implícita la idea de que puede cambiar su propio programa, además de que se puede comportar como la mente es decir no se puede predecir lo que hará ya que esto depende no solo de su tabla de acción (interna), sino que también depende de la entrada recibida (externa).
Supongamos una máquina de Turing con un alfabeto unario, en la que el nulo (ausencia de dato) lo señalamos con 0. La máquina puede tener cinco estados que denominamos {e0, e1, e2, e3, e4}.
La sucesión de pasos de cómputo es la siguiente (suponemos un estado inicial cualquiera ex):
S: Estado anterior
R: Símbolo leído
W: Símbolo a escribir
M: Movimiento (R, L).
N: Nuevo estado.
1.- Se lee un carácter c (en nuestro caso es necesariamente 0 o 1)
2.- Se mira en la tabla que fila corresponde a la combinación ex/c.
3a.- Si no existe entrada la máquina se detiene.
3b.- Si existe entrada se ejecuta la instrucción en el siguiente orden:
3b1.- Se escribe en la posición actual el carácter señalado (puede ser el mismo que había).
3b2.- Se mueve el cabezal una posición a izquierda o derecha.
3b3.- Se pasa al estado señalado en la última columna (puede implicar no cambiar de estado).
3b4.- Se repite el ciclo desde el punto 1.
El programa hace que el autómata lea la cantidad y la repita a la derecha separadas por un nulo (0). Por ejemplo, si encuentra 111100000 lo transforma en 111101111.
P1: La máquina ejecuta el primer paso. Arranca en el estado e0, donde lee un 1; entonces, de acuerdo con su tabla de acción escribe un 0 en esa posición, se mueve a la derecha y entra en estado e1.
P2: En e1 lee un 1, escribe un 1 y se mueve a la derecha. Sigue en e1.
P3: En e1 lee 0, escribe 0, se mueve a la derecha y cambia a e2
P4: En e2 lee 0, escribe 1, se mueve a la izquierda y cambia a e3
P5: En e3 lee 0, escribe 0, se mueve a la izquierda y cambia a e4
P6: En e4 lee 1, escribe 1, se mueve a la izquierda y sigue en e4
El proceso sigue la misma lógica a través de los sucesivos pasos hasta llegar al último.
P15: En e0 lee 0; no existe ninguna entrada en la tabla para esta combinación, por lo que el autómata se detiene. Comprobamos como al final ha escrito en la cinta la cantidad esperada: 11011.
