Ejemplos de máquinas de Turing

Los siguientes son ejemplos para complementar el artículo Máquina de Turing .

La siguiente tabla es el primer ejemplo de Turing (Turing 1937):

"1. Se puede construir una máquina para calcular la secuencia 0 1 0 1 0 1..." (0 <espacio en blanco> 1 <espacio en blanco> 0...) ^{[ 1 ]}

Con respecto a las acciones que realiza realmente la máquina, Turing (1936) ^{[ 2 ]} afirma lo siguiente:

"Esta tabla [de ejemplo] (y todas las tablas siguientes del mismo tipo) debe entenderse en el sentido de que, para una configuración descrita en las dos primeras columnas, las operaciones de la tercera columna se llevan a cabo sucesivamente, y la máquina pasa entonces a la configuración m de la última columna." ^{[ 2 ]}

Lo deja muy claro cuando reduce la tabla anterior a una sola instrucción llamada "b", ^{[ 3 ]} pero su instrucción consta de 3 líneas. La instrucción "b" tiene tres posibilidades de símbolos diferentes {Ninguno, 0, 1}. Cada posibilidad va seguida de una secuencia de acciones hasta que llegamos a la columna más a la derecha, donde la configuración m final es "b":

Como observaron varios comentaristas, incluido el propio Turing (1937), (por ejemplo, Post (1936), Post (1947), Kleene (1952), Wang (1954)), las instrucciones de Turing no son atómicas : se pueden hacer simplificaciones adicionales del modelo sin reducir su potencia computacional; véase más información en Post–Turing machine .

Como se indica en el artículo Máquina de Turing , Turing propuso que su mesa se atomizara aún más permitiendo solo una única impresión/borrado seguida de un único movimiento de cinta L/R/N. Nos da este ejemplo de la primera mesa pequeña convertida: ^{[ 4 ]}

La afirmación de Turing aún implica cinco operaciones atómicas. Ante una instrucción dada (configuración m), la máquina:

1. observa el símbolo de la cinta debajo de la cabeza
2. basado en el símbolo observado va a la secuencia de instrucciones apropiada para usar
3. imprime el símbolo S _j o borra o no hace nada
4. Mueve la cinta hacia la izquierda, hacia la derecha o no la mueve en absoluto.
5. va a la configuración m final para ese símbolo

Dado que las acciones de una máquina de Turing no son atómicas, una simulación de la máquina debe atomizar cada quíntupla en una secuencia de acciones más simples. Una posibilidad —utilizada en los siguientes ejemplos de "comportamientos" de su máquina— es la siguiente:

(q _i ) Símbolo de cinta de prueba debajo del cabezal: Si el símbolo es S _0, vaya a q _i .01, si el símbolo es S _1, vaya a q _i .11, si el símbolo es S _2, vaya a q _i .21, etc.

(q _i .01) imprime el símbolo S _j 0 o borra o no hagas nada y luego ve a q _i .02

(q _i .02) mueva la cinta hacia la izquierda o hacia la derecha, o no la mueva en absoluto, luego vaya a qm0

(q _i .11) imprime el símbolo S _j 1 o borra o no hagas nada y luego ve a q _i .12

(q _i .12) mueva la cinta hacia la izquierda o hacia la derecha, o no la mueva en absoluto, luego vaya a qm1.

(q _i .21) imprime el símbolo S _j 2 o borra o no hagas nada y luego ve a q _i .22

(q _i .22) mueva la cinta hacia la izquierda o hacia la derecha, o no la mueva en absoluto, luego vaya a qm2.

(etc. — deben tenerse en cuenta todos los símbolos)

Las llamadas máquinas de estados finitos "canónicas" realizan las pruebas de símbolos "en paralelo"; consulte más información en microprogramación .

En el siguiente ejemplo de lo que hace la máquina, observaremos algunas peculiaridades de los modelos de Turing:

La convención de escribir las cifras solo en casillas alternas es muy útil: siempre la utilizaré. ^{[ 2 ]}

Así, al imprimir, omite un cuadrado de cada dos. Los cuadrados impresos se denominan cuadrados F; los cuadrados en blanco intermedios pueden usarse como marcadores y se llaman cuadrados E, como en "susceptibles de borrar". Los cuadrados F, a su vez, son sus "cuadrados de figura" y solo llevan los símbolos 1 o 0 , símbolos que él denominaba "figuras" (como en "números binarios").

En este ejemplo, la cinta comienza en blanco y luego se imprimen las cifras sobre ella. Para mayor brevedad, aquí solo se muestran los estados de la tabla:

Aquí se muestra la misma "ejecución" con todas las impresiones de cinta y movimientos intermedios:

Un examen minucioso de la tabla revela ciertos problemas con el ejemplo de Turing : no se tienen en cuenta todos los símbolos.

Por ejemplo, supongamos que su cinta no estaba inicialmente en blanco. ¿Qué ocurriría? La máquina de Turing leería valores diferentes a los previstos.

Esta es una subrutina muy importante que se utiliza en la rutina de "multiplicación".

La máquina de Turing de ejemplo procesa una secuencia de 0s y 1s, donde el 0 se representa con un espacio en blanco. Su tarea consiste en duplicar cualquier serie de 1s encontrada en la cinta escribiendo un 0 entre ellos. Por ejemplo, cuando el cabezal lee "111", escribe un 0 y luego "111". La salida será "1110111".

Para cumplir su tarea, esta máquina de Turing solo necesitará 5 estados de operación, que se denominan {s ₁ , s ₂ , s ₃ , s ₄ , s ₅ }. Cada estado realiza 4 acciones:

1. Lee el símbolo que aparece debajo del encabezado.
2. Escriba el símbolo de salida decidido por el estado
3. Mueva la cinta hacia la izquierda o hacia la derecha según lo decida el estado.
4. Cambiar al siguiente estado determinado por el estado actual.

Operación de impresión : Imprime el símbolo S o borra o no hace nada .

Una "ejecución" de la máquina secuencia a través de 16 configuraciones de la máquina (también conocidas como estados de Turing):

El comportamiento de esta máquina se puede describir como un bucle: comienza en s ₁ , reemplaza el primer 1 con un 0, luego usa s ₂ para moverse a la derecha, saltándose los 1 y el primer 0 encontrado. s ₃ luego salta la siguiente secuencia de 1 (inicialmente no hay ninguna) y reemplaza el primer 0 que encuentra con un 1. s ₄ se mueve de nuevo a la izquierda, saltándose los 1 hasta que encuentra un 0 y cambia a s _5. s ₅ luego se mueve a la izquierda, saltándose los 1 hasta que encuentra el 0 que fue escrito originalmente por s ₁ .

Reemplaza ese 0 con un 1, se mueve una posición a la derecha y vuelve a entrar en s ₁ para otra ronda del bucle.

Esto continúa hasta que s ₁ encuentra un 0 (este es el 0 en medio de las dos cadenas de 1s), momento en el que la máquina se detiene.

Descripción alternativa

Otra descripción plantea el problema como la forma de llevar la cuenta de cuántos "1" hay. No podemos usar un estado para cada número posible (un estado para cada uno de 0, 1, 2, 3, 4, 5, 6, etc.), porque entonces necesitaríamos infinitos estados para representar todos los números naturales, y la máquina de estados es finita ; tendremos que llevar la cuenta de alguna manera usando la cinta.

Su funcionamiento básico consiste en copiar cada "1" al otro lado, moviéndose de un lado a otro; es lo suficientemente inteligente como para recordar en qué parte del recorrido se encuentra. En detalle, transporta cada "1" al otro lado, reconociendo el "0" que lo separa en el medio y el "0" del otro lado para saber que ha llegado al final. Regresa utilizando el mismo método, detectando el "0" del medio y luego el "0" del lado original. Este "0" del lado original es la clave para comprender cómo lleva la cuenta de los 1.

El truco consiste en que, antes de llevar el "1", marca ese dígito como "ocupado" reemplazándolo por un "0". Al regresar, vuelve a colocar ese "0" por un "1", luego pasa al siguiente , lo marca con un "0" y repite el ciclo, llevando ese "1" de un lado a otro, y así sucesivamente. Con cada viaje de ida y vuelta, el marcador "0" se mueve un paso más cerca del centro . De esta manera, lleva la cuenta de cuántos "1" ha llevado.

Cuando regresa, el marcador "0" parece el final de la colección de "1" para él; cualquier "1" que ya haya sido tomado al otro lado es invisible para él (al otro lado del marcador "0") y por lo tanto es como si estuviera trabajando en un número (N-1) de "1", similar a una demostración por inducción matemática .

Una "ejecución" completa que muestra los resultados de los "movimientos" intermedios.

La siguiente tabla de instrucciones de Turing se derivó de Peterson: ^{[ 5 ]} "un castor ocupado de tres estados escribe 6 unos antes de detenerse". Peterson mueve el cabezal; en el siguiente modelo, la cinta se mueve. 0 es el carácter en blanco: la cinta comienza con todas las celdas en 0.

El diagrama de "estado" del castor ocupado de 3 estados muestra las secuencias internas de eventos necesarias para realizar realmente "el estado". Como se señaló anteriormente, Turing (1937) deja perfectamente claro que esta es la interpretación correcta de las 5-tuplas que describen la instrucción. ^{[ 1 ]} Para más información sobre la atomización de las 5-tuplas de Turing, véase Máquina post-Turing :

La siguiente tabla muestra la ejecución "comprimida", es decir , solo los estados de Turing:

La ejecución completa del castor ocupado de 3 estados. Los estados de Turing resultantes (lo que Turing denominó las "m-configuraciones" — "configuraciones de la máquina") se muestran resaltados en gris en la columna A, y también debajo de las instrucciones de la máquina (columnas AF-AU):