Descripción Instantánea

                             Descripción Instantánea

Es una secuencia de la forma a1 qa2 donde 01, 02 Є Г* y q∈Q que escribe el estado de una máquina de Turing. La cinta contiene la cadena 01 02 seguida de infinitos blancos. El cabezal señala el primer símbolo de A2.

Por ejemplo, para la máquina de Turing

MT = ({p, q}, {0, 1}, {0, 1, x}, p, A, {q},

con las transiciones

б(р, 1) = (p, x, R),

б(p, 0) = (p, 0, R) у

δ(p, A) = (q, A, R).

La descripción instantánea para la cinta 1011

es:

p1011∆∆

xp01144

x0p11∆∆

x0 x x q∆∆

Definimos una máquina de Turing sobre el alfabeto {0,1}, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie. La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás de dicho símbolo blanco. Es decir, posiciona el cabezal sobre el 1 situado en el extremo izquierdo, doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá "1110111", con "1111" devolverá "111101111", y sucesivamente.

 El conjunto de estados es {81, 82, 83, 84, 85} y el estado inicial es s₁. La tabla que describe la función de transición es la siguiente:

El funcionamiento de una computación de esta máquina puede mostrarse con el siguiente ejemplo (en negrita se resalta la posición de la cabeza lectora/escritora):

La máquina realiza su 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 hacia la derecha, saltando los símbolos 1 hasta un 0 (que debe existir), cuando lo encuentra pasa al estado s3, con este estado avanza saltando los 1 hasta encontrar otro 0 (la primera vez no habrá 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 continúa 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 símbolo 0, será el símbolo central, con lo que la máquina se detiene al haber finalizado el cómputo.