Maquina De Turing

QUE ES Y EN QUE CONSISTE UNA MAQUINA DE TURING

Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por qué coincidir con los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador, existe un cambio en la representación del estado, usando para ello los números del 0 al 99, para permitir un mayor número de ellos. La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.

3. ¿QUÉ OPERACIONES PUEDE REALIZAR UNA MAQUINA DE TURING

1. Parar la computación.

2. Moverse un cuadrado a la derecha.

3. Moverse un cuadrado a la izquierda.

4. Escribir el símbolo S0 en lugar de cualquier otro que este en el cuadrado examinado.

5. Escribir el símbolo S1 en lugar de cualquier otro que este en el cuadrado examinado.

...