Los siguientes son ejemplos para complementar el artículo Máquina de Turing .
El primer ejemplo de Turing
La siguiente tabla es el primer ejemplo de Turing ( Alan Turing 1937):
- "1. Se puede construir una máquina para calcular la secuencia 0 1 0 1 0 1 ..." (0
1 Indecidible p. 119)0 ...) (
Configuración | Comportamiento | ||
---|---|---|---|
m-configuración (estado) | Símbolo de cinta | Operaciones de cinta | Configuración m final (estado) |
B | blanco | P0, R | C |
C | blanco | R | mi |
mi | blanco | P1, R | F |
F | blanco | R | B |
Con respecto a las acciones que realmente realiza la máquina, Turing (1936) ( Indecidible p. 121) afirma lo siguiente:
- "Esta tabla [de ejemplo] (y todas las tablas sucesivas 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 luego la máquina pasa a la configuración m en la columna final ". (Indecidible p. 121)
Lo deja muy claro cuando reduce la tabla anterior a una sola instrucción llamada "b" ( Indecidible pág. 120), pero su instrucción consta de 3 líneas. La instrucción "b" tiene tres posibilidades de símbolo diferentes {Ninguno, 0, 1}. A cada posibilidad le sigue una secuencia de acciones hasta llegar a la columna de la derecha, donde la configuración m final es "b":
Configuración m actual (instrucción) | Símbolo de cinta | Operaciones en la cinta | Configuración m final (instrucción) |
---|---|---|---|
B | Ninguno | P0 | B |
B | 0 | R, R, P1 | B |
B | 1 | R, R, P0 | B |
Como lo 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 simplificar más el modelo. realizarse sin reducir su potencia computacional; ver más en Post-Turing machine .
Como se indica en el artículo de la máquina de Turing , Turing propuso que su mesa se atomizara aún más permitiendo solo una sola impresión / borrado seguido de un solo movimiento de cinta L / R / N. Nos da este ejemplo de la primera mesita convertida ( Indecidible , p. 127):
Configuración m actual (estado de Turing) | Símbolo de cinta | Operación de impresión | Movimiento de cinta | Configuración m final (estado de Turing) |
---|---|---|---|---|
q 1 | blanco | P0 | R | q 2 |
q 2 | blanco | P en blanco, es decir, E | R | q 3 |
q 3 | blanco | P1 | R | q 4 |
q 4 | blanco | P en blanco, es decir, E | R | q 1 |
La declaración de Turing todavía implica cinco operaciones atómicas. En una instrucción dada (configuración m) la máquina:
- observa el símbolo de cinta debajo de la cabeza
- basado en el símbolo observado va a la secuencia de instrucciones apropiada para usar
- imprime el símbolo S j o borra o no hace nada
- mueve la cinta a la izquierda, a la derecha o no mueve nada
- va a la configuración m final para ese símbolo
Debido a que las acciones de una máquina de Turing no son atómicas, una simulación de la máquina debe atomizar cada 5 tupla 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 ) Pruebe el símbolo de cinta debajo de la cabeza: Si el símbolo es S 0, vaya a q i .01, si el símbolo S 1 vaya a q i .11, si el símbolo S 2 vaya a q i .21, etc.
- (q i .01) imprima el símbolo S j 0 o borre o no haga nada y luego vaya a q i .02
- (q i .02) mueva la cinta hacia la izquierda o hacia la derecha ni nada y luego vaya a qm0
- (q i .11) imprima el símbolo S j 1 o borre o no haga nada, luego vaya a q i .12
- (q i .12) mueva la cinta hacia la izquierda o hacia la derecha ni nada y luego vaya a qm1
- (q i .21) imprima el símbolo S j 2 o borre o no haga nada y luego vaya a q i .22
- (q i .22) mueva la cinta hacia la izquierda o hacia la derecha ni nada y luego vaya a qm2
- (etc - todos los símbolos deben tenerse en cuenta)
Las llamadas máquinas de estados finitos "canónicos" realizan las pruebas de símbolos "en paralelo"; ver más en microprogramación .
En el siguiente ejemplo de lo que hace la máquina, notaremos algunas peculiaridades de los modelos de Turing:
- "La convención de escribir las cifras sólo en cuadrados alternos es muy útil: siempre la utilizaré". (Indecidible p. 121)
Por lo tanto, al imprimir, se salta cada dos cuadrados. Los cuadrados impresos se denominan cuadrados F; los cuadrados en blanco en el medio pueden usarse como "marcadores" y se denominan "cuadrados E" como en "susceptibles de borrarse". Los cuadros F, a su vez, son sus "Cuadrados de figuras" y solo llevarán los símbolos 1 o 0, símbolos que él llamó "figuras" (como en "números binarios").
En este ejemplo, la cinta comienza "en blanco" y luego se imprimen las "cifras". En aras de la brevedad, aquí solo se muestran los estados TABLE:
Secuencia | Identificador de instrucción | Cabeza | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
. | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | ||
1 | 1 | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . | . |
2 | 2 | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . | . |
3 | 3 | . | . | . | . | . | . | 0 | . | . | . | . | . | . | . | . | . | . | . |
4 | 4 | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . | . |
5 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | . | . | . | . | . | . | . | . |
6 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . | . |
7 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . | . |
8 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . | . |
9 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . | . |
10 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . | . |
11 | 3 | . | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . | . |
12 | 4 | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | . |
13 | 1 | . | . | . | . | . | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . |
14 | 2 | . | . | . | . | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 | . | 1 | . | 0 |
Aquí se muestra la misma "ejecución" con todas las impresiones y movimientos de cinta intermedios:
Una mirada de cerca a la tabla revela ciertos problemas con el propio ejemplo de Turing: no se tienen en cuenta todos los símbolos.
Por ejemplo, supongamos que su cinta no estuviera inicialmente en blanco. ¿Qué pasaría? La máquina de Turing leería valores diferentes a los previstos.
Una subrutina de copia
Ésta es una subrutina muy importante que se utiliza en la rutina "multiplicar".
La máquina de Turing de ejemplo maneja una cadena de 0 y 1, con 0 representado por el símbolo en blanco. Su tarea es duplicar cualquier serie de unos que se encuentren en la cinta escribiendo un 0 entre ellos. Por ejemplo, cuando la cabeza lee "111", escribirá un 0 y luego "111". La salida será "1110111".
Para realizar su tarea, esta máquina de Turing solo necesitará 5 estados de operación, que se denominan {s 1 , s 2 , s 3 , s 4 , s 5 }. Cada estado realiza 4 acciones:
- Leer el símbolo debajo de la cabeza
- Escriba el símbolo de salida decidido por el estado
- Mueva la cinta hacia la izquierda o hacia la derecha que decida el estado
- Cambiar al siguiente estado decidido por el estado actual
Configuración m inicial (instrucción actual) | Símbolo de cinta | Operación de impresión | Movimiento de cinta | Configuración m final (siguiente instrucción) |
---|---|---|---|---|
s 1 | 0 | norte | norte | H |
s 1 | 1 | mi | R | s 2 |
s 2 | 0 | mi | R | s 3 |
s 2 | 1 | P1 | R | s 2 |
s 3 | 0 | P1 | L | s 4 |
s 3 | 1 | P1 | R | s 3 |
s 4 | 0 | mi | L | s 5 |
s 4 | 1 | P1 | L | s 4 |
s 5 | 0 | P1 | R | s 1 |
s 5 | 1 | P1 | L | s 5 |
H | - | - | - |
Una "ejecución" de las secuencias de la máquina a través de 16 configuraciones de máquina (también conocidas como estados de Turing):
Secuencia | Identificador de instrucción | Cabeza | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | s 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
2 | s 2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
3 | s 2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
4 | s 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
5 | s 4 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
6 | s 5 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
7 | s 5 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | s 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
9 | s 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
10 | s 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
11 | s 3 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
12 | s 4 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
13 | s 4 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
14 | s 5 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
15 | s 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
dieciséis | H | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
El comportamiento de esta máquina se puede describir como un bucle: comienza en s 1 , reemplaza el primer 1 con un 0, luego usa s 2 para moverse hacia la derecha, saltando los 1 y el primer 0 encontrado. s 3 luego salta la siguiente secuencia de 1s (inicialmente no hay ninguno) y reemplaza el primer 0 que encuentra con un 1. s 4 se mueve hacia la izquierda, saltando 1s hasta que encuentra un 0 y cambia a s 5 . s 5 luego se mueve hacia la izquierda, saltando 1s hasta que encuentra el 0 que fue escrito originalmente por s 1 .
Reemplaza ese 0 con un 1, se mueve una posición hacia la derecha y vuelve a ingresar s 1 para otra ronda del ciclo.
Esto continúa hasta que s 1 encuentra un 0 (este es el 0 en el medio de las dos cadenas de 1), momento en el que la máquina se detiene.
Descripción alternativa
Otra descripción ve el problema como cómo realizar un seguimiento 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 estados infinitos para representar todos los números naturales, y el La máquina de estado es finita , tendremos que rastrear esto usando la cinta de alguna manera.
La forma básica en que funciona es copiando cada "1" al otro lado, moviéndose hacia adelante y hacia atrás; es lo suficientemente inteligente como para recordar en qué parte del viaje se encuentra. Con más detalle, lleva cada "1" al otro lado, reconociendo el "0" de separación en el medio y reconociendo el "0" en el otro lado para saber que ha llegado al final. Vuelve usando el mismo método, detectando el "0" del medio y luego el "0" en el lado original. Este "0" en el lado original es la clave del rompecabezas de cómo lleva la cuenta del número de unos.
El truco es que antes de llevar el "1", marca ese dígito como "tomado" reemplazándolo con un "0". Cuando regresa, vuelve a llenar ese "0" con un "1", luego pasa al siguiente , lo marca con un "0" y repite el ciclo, llevando ese "1" a lo ancho y así sucesivamente. Con cada viaje de ida y vuelta, el marcador "0" se acerca un paso más al centro . Así es como realiza un seguimiento de cuántos "1" ha atravesado.
Cuando regresa, el marcador "0" se ve como el final de la colección de "1"; los "1" que ya se han cruzado son invisibles para él (en el otro lado del marcador "0" ) y así 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. Para verlo mejor haga clic en la imagen, luego haga clic en la descarga de mayor resolución:
Castor ocupado de 3 estados
La siguiente tabla de instrucciones de Turing se derivó de Peterson (1988) página 198, Figura 7.15. Peterson mueve la cabeza; en el siguiente modelo la cinta se mueve.
Símbolo de cinta | Estado actual A | Estado actual B | Estado actual C | ||||||
---|---|---|---|---|---|---|---|---|---|
Símbolo de escritura | Mueva la cinta | Siguiente estado | Símbolo de escritura | Mueva la cinta | Siguiente estado | Símbolo de escritura | Mueva la cinta | Siguiente estado | |
0 | 1 | R | B | 1 | L | A | 1 | L | B |
1 | 1 | L | C | 1 | R | B | 1 | norte | DETENER |
El dibujo de "estado" del castor ocupado de 3 estados muestra las secuencias internas de eventos requeridas para realizar realmente "el estado". Como se señaló anteriormente, Turing (1937) deja perfectamente claro que esta es la interpretación adecuada de las 5 tuplas que describen la instrucción ( Indecidible , p. 119). Para obtener más información sobre la atomización de las 5 tuplas de Turing, consulte la máquina Post-Turing :
La siguiente tabla muestra la ejecución "comprimida", solo los estados de Turing:
Secuencia | Identificador de instrucción | Cabeza | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | A | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | C | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | B | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | A | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | B | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
8 | B | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
9 | B | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
10 | B | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
11 | B | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
12 | A | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
13 | C | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
14 | H | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
La "carrera" completa del castor ocupado de 3 estados. Los estados de Turing resultantes (lo que Turing llamó las "configuraciones-m" - "configuraciones de máquina") se muestran resaltados en gris en la columna A, y también bajo las instrucciones de la máquina (columnas AF-AU)):
Referencias
Para obtener referencias completas, consulte la máquina de Turing .
- Ivars Peterson, 1988, The Mathematical Tourist: Instantáneas de las matemáticas modernas , WH Freeman and Company, Nueva York, ISBN 0-7167-2064-7 (pbk.). Las máquinas de Turing se describen en las páginas 194 y siguientes, el ejemplo del castor ocupado está en la Figura 7.15 en la página 198.
- Martin Davis editor, 1965, The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, Nueva York, sin ISBN, sin número de catálogo de tarjetas.
- Alan Turing, 1937, On Computable Numbers, with an Application to the Entscheidungsproblem , págs.116 y siguientes, con un breve comentario de Davis en la página 115.
- Alan Turing, 1937, On Computable Numbers, with an Application to the Entscheidungsproblem. Una corrección , pág. 152-154.