Máquina de post-Turing - Post–Turing machine
Una máquina de Post-Turing es una "formulación del programa" de un tipo de máquina de Turing , que comprende una variante de Emil Publicar 's Turing equivalente modelo de cálculo . El modelo de Post y el modelo de Turing, aunque muy similares entre sí, se desarrollaron de forma independiente. El artículo de Turing se recibió para su publicación en mayo de 1936, seguido del de Post en octubre). Una máquina de Post-Turing usa un alfabeto binario , una secuencia infinita de ubicaciones de almacenamiento binario y un lenguaje de programación primitivo con instrucciones para el movimiento bidireccional entre el almacenamiento. ubicaciones y alteración de su contenido de uno en uno. Martin Davis utilizó los nombres "programa de Post-Turing" y "máquina de Post-Turing" en 1973-1974 (Davis 1973, p. 69ff). Más tarde, en 1980, Davis utilizó el nombre de "programa Turing-Post" (Davis, en Steen p. 241).
1936: modelo posterior
En su artículo de 1936 "Procesos combinatorios finitos — Formulación 1", Emil Post describió un modelo del que conjeturó que es " lógicamente equivalente a la recursividad ".
El modelo de cálculo de Post difiere del modelo de la máquina de Turing en una "atomización" adicional de los actos que realizaría una "computadora" humana durante un cálculo.
El modelo de Post emplea un " espacio de símbolo " que consiste en una "secuencia infinita de dos direcciones de espacios o cuadros", cada cuadro capaz de estar en cualquiera de las dos condiciones posibles, a saber, "marcado" (como por un solo trazo vertical) y "sin marcar" " (vacío). Inicialmente, finitamente , muchas de las casillas están marcadas, el resto sin marcar. Entonces, un "trabajador" debe moverse entre las cajas, estando dentro y operando en una sola caja a la vez, de acuerdo con un "conjunto de direcciones" ( instrucciones ) finito y fijo , que se enumeran en orden (1,2,3, ..., n ). Comenzando en una casilla "señalada como punto de partida", el trabajador debe seguir el conjunto de instrucciones una a la vez, comenzando con la instrucción 1.
Hay cinco operaciones primitivas diferentes que el trabajador puede realizar:
- (a) Marcar la casilla en la que se encuentra, si está vacía
- (b) Borrando la marca en la casilla en la que está, si está marcada
- (c) Pasando a la caja de su derecha
- (d) Moviéndose a la caja a su izquierda
- (e) Determinar si la casilla en la que se encuentra, está o no marcada.
Entonces, la i ésima "instrucción" (instrucción) dada al trabajador debe ser una de las siguientes formas:
- Realice la operación O i [ O i = (a), (b), (c) o (d)] y luego siga la dirección j i
- Realice la operación (e) y según la respuesta sea sí o no, siga la dirección j i ′ o j i ′ ′
- Deténgase .
(El texto con sangría y cursiva anteriores son como en el original). Post comenta que esta formulación se encuentra "en sus etapas iniciales" de desarrollo, y menciona varias posibilidades de "mayor flexibilidad" en su "forma definitiva" final, que incluyen
- reemplazar la infinidad de cajas por un espacio de símbolos extensible finito, "extender las operaciones primitivas para permitir la extensión necesaria del espacio de símbolos finito dado a medida que avanza el proceso",
- usar un alfabeto de más de dos símbolos, "tener más de una forma de marcar una casilla",
- introducir un número finito de "objetos físicos que sirvan como indicadores, que el trabajador pueda identificar y mover de una caja a otra".
1947: Reducción formal de Post de las 5 tuplas de Turing a 4 tuplas
Como se menciona brevemente en el artículo Turing machine , Post, en su artículo de 1947 ( Recursive Unsolvability of a Problem of Thue ) atomizó las 5 tuplas de Turing en 4 tuplas:
- "Nuestros cuatrillizos son quintillizos en el desarrollo de Turing. Es decir, donde nuestra instrucción estándar ordena una impresión (sobreimpresión) o movimiento, izquierda o derecha, la instrucción estándar de Turing siempre ordena una impresión y un movimiento, derecha, izquierda o ninguno" ( nota al pie 12, Indecidible , p. 300)
Al igual que Turing, definió el borrado como la impresión de un símbolo "S0". Y así, su modelo admitía cuatrillizos de sólo tres tipos (cf. Indecidible , p. 294):
- q yo S j L q l ,
- q yo S j R q l ,
- q yo S j S k q l
En ese momento todavía conservaba la convención de máquina de estado de Turing: no había formalizado la noción de una ejecución secuencial asumida de pasos hasta que una prueba específica de un símbolo "ramificara" la ejecución en otra parte.
1954, 1957: modelo Wang
Para una reducción aún mayor, a solo cuatro instrucciones, del modelo de Wang presentado aquí, consulte Wang B-machine .
Wang (1957, pero presentado al ACM en 1954) se cita a menudo (cf. Minsky (1967), p. 200) como la fuente de la "formulación del programa" de las máquinas de Turing de cinta binaria que utilizan instrucciones numeradas del conjunto
- escribir 0
- escribir 1
- mover hacia la izquierda
- mover a la derecha
- si escanea 0, vaya a la instrucción i
- si escanea 1, entonces vaya a la instrucción j
Cualquier máquina de Turing de cinta binaria se convierte fácilmente en un "programa Wang" equivalente utilizando las instrucciones anteriores.
1974: primer modelo de Davis
Martin Davis era un estudiante de pregrado de Emil Post. Junto con Stephen Kleene completó su Ph.D. bajo Alonzo Church (Davis (2000) 1ª y 2ª notas al pie de página p. 188).
El siguiente modelo lo presentó en una serie de conferencias en el Instituto Courant en NYU en 1973-1974. Este es el modelo al que Davis aplicó formalmente el nombre de "máquina post-Turing" con su "lenguaje post-Turing". Se supone que las instrucciones se ejecutan secuencialmente (Davis 1974, p. 71):
1978: segundo modelo de Davis
El siguiente modelo aparece como ensayo ¿Qué es un cálculo? en Steen, páginas 241-267. Por alguna razón, Davis ha cambiado el nombre de su modelo a "máquina de Turing-Post" (con un deslizamiento hacia atrás en la página 256).
En el siguiente modelo, Davis asigna los números "1" a la "marca / barra" de Post y "0" al cuadrado en blanco. Para citar a Davis: "Ahora estamos listos para presentar el lenguaje de programación Turing-Post. En este lenguaje hay siete tipos de instrucciones:
- "IMPRIMIR 1
- "IMPRIMIR 0
- "VE A LA DERECHA
- "VE A LA IZQUIERDA
- "VAYA AL PASO i SI SE ESCANE 1
- "VAYA AL PASO i SI SE ESCANEA 0
- "PARADA
"Un programa de Turing-Post es entonces una lista de instrucciones, cada una de las cuales es de uno de estos siete tipos. Por supuesto, en un programa real, la letra i en un paso del quinto o sexto tipo debe reemplazarse por un número definido (entero positivo) ". (Davis en Steen, p. 247).
1994 (2ª edición): modelo de programa Post-Turing de Davis – Sigal – Weyuker
"Aunque la formulación de Turing que hemos presentado tiene un espíritu más cercano a la dada originalmente por Emil Post, fue el análisis de Turing de la computación lo que ha hecho que esta formulación parezca tan apropiada. Este lenguaje ha jugado un papel fundamental en la informática teórica". (Davis et al. (1994) pág. 129)
Este modelo permite la impresión de múltiples símbolos. El modelo permite B (en blanco) en lugar de S 0 . La cinta es infinita en ambas direcciones. Se mueve la cabeza o la cinta, pero sus definiciones de DERECHA e IZQUIERDA siempre especifican el mismo resultado en cualquier caso (Turing usó la misma convención).
- IMPRIMIR σ; Reemplazar el símbolo escaneado con σ
- SI σ GOTO L; SI el símbolo escaneado es σ ENTONCES, vaya a "la primera" instrucción etiquetada como L
- DERECHA; Escanear el cuadrado inmediatamente a la derecha del cuadrado actualmente escaneado
- IZQUIERDA; Escanear el cuadrado inmediatamente a la izquierda del cuadrado actualmente escaneado
Este modelo se reduce a las versiones binarias {0, 1} presentadas anteriormente, como se muestra aquí:
- IMPRIMIR 0 = BORRAR; Reemplazar el símbolo escaneado con 0 = B = EN BLANCO
- IMPRIMIR 1; Reemplazar el símbolo escaneado con 1
- SI 0 GOTO L; SI el símbolo escaneado es 0 ENTONCES, vaya a "la primera" instrucción etiquetada como L
- SI 1 GOTO L; SI el símbolo escaneado es 1 ENTONCES vaya a "la primera" instrucción etiquetada L
- DERECHA; Escanear el cuadrado inmediatamente a la derecha del cuadrado actualmente escaneado
- IZQUIERDA; Escanear el cuadrado inmediatamente a la izquierda del cuadrado actualmente escaneado
Ejemplos de la máquina Post-Turing
Atomizar quintuples de Turing en una secuencia de instrucciones de Post-Turing
El siguiente método de "reducción" (descomposición, atomización), desde 5 tuplas de Turing de 2 símbolos hasta una secuencia de instrucciones Post-Turing de 2 símbolos, se puede encontrar en Minsky (1961). Afirma que esta reducción a "un programa ... una secuencia de instrucciones " está en el espíritu de la máquina B de Hao Wang (cursiva en el original, cf. Minsky (1961) p. 439).
(La reducción de Minsky a lo que él llama "una subrutina" da como resultado 5 en lugar de 7 instrucciones Post-Turing. No atomizó Wi0: "Escriba el símbolo Si0; vaya al nuevo estado Mi0" y Wi1: "Escriba el símbolo Si1; ir al nuevo estado Mi1 ". El siguiente método atomiza aún más Wi0 y Wi1; en todos los demás aspectos, los métodos son idénticos.)
Esta reducción de las 5 tuplas de Turing a instrucciones de Post-Turing puede no resultar en un programa de Post-Turing "eficiente", pero será fiel al programa de Turing original.
En el siguiente ejemplo, cada tupla de 5 de Turing del castor ocupado de 2 estados se convierte en
- un "salto" condicional inicial (goto, rama), seguido de
- 2 instrucciones de acción de cinta para el caso "0": Imprimir o Borrar o Ninguno, seguido de Izquierda o Derecha o Ninguno, seguido de
- un "salto" incondicional para el caso "0" a su siguiente instrucción
- 2 instrucciones de acción de cinta para el caso "1": Imprimir o Borrar o Ninguno, seguido de Izquierda o Derecha o Ninguno, seguido de
- un "salto" incondicional para el caso "1" a su siguiente instrucción
para un total de 1 + 2 + 1 + 2 + 1 = 7 instrucciones por estado de Turing.
Por ejemplo, el estado de Turing "A" del castor ocupado de 2 estados, escrito como dos líneas de 5 tuplas, es:
| Configuración m inicial (estado de Turing) | Símbolo de cinta | Operación de impresión | Movimiento de cinta | Configuración m final (estado de Turing) |
|---|---|---|---|---|
| A | 0 | PAG | R | B |
| A | 1 | PAG | L | B |
La tabla representa una sola "instrucción" de Turing, pero vemos que consta de dos líneas de 5 tuplas, una para el caso "símbolo de cinta debajo del encabezado = 1", la otra para el caso "símbolo de cinta debajo del encabezado = 0 ". Turing observó ( Indecidible , p. 119) que las dos columnas de la izquierda - "configuración-m" y "símbolo" - representan la "configuración" actual de la máquina - su estado incluye tanto Tape como Table en ese instante - y las últimas tres columnas son su "comportamiento" posterior. Como la máquina no puede estar en dos "estados" a la vez, la máquina debe "ramificarse" a una configuración u otra:
| Configuración inicial m y símbolo S | Operación de impresión | Movimiento de cinta | Configuración m final |
|---|---|---|---|
| S = 0 → | P → | R → | B |
| → A < | |||
| S = 1 → | P → | L → | B |
Después de la "rama de configuración" (J1 xxx) o (J0 xxx), la máquina sigue uno de los dos "comportamientos" subsiguientes. Enumeramos estos dos comportamientos en una línea y los numeramos (o etiquetamos) secuencialmente (de forma única). Debajo de cada salto (rama, ir a) colocamos su "número" de salto (dirección, ubicación):
Según las convenciones de la máquina Post-Turing, cada una de las instrucciones Imprimir, Borrar, Izquierda y Derecha constan de dos acciones:
- Acción de cinta: {P, E, L, R}, luego
- Acción de la tabla: ir a la siguiente instrucción en secuencia
Y según las convenciones de la máquina Post-Turing, los "saltos" condicionales J0xxx, J1xxx constan de dos acciones:
- Acción de la cinta: mire el símbolo en la cinta debajo de la cabeza
- Acción de la tabla: si el símbolo es 0 (1) y J0 (J1), vaya a xxx; de lo contrario, vaya a la siguiente instrucción en secuencia.
Y según las convenciones de la máquina Post-Turing, el "salto" incondicional Jxxx consiste en una sola acción, o si queremos regularizar la secuencia de 2 acciones:
- Acción de la cinta: mire el símbolo en la cinta debajo de la cabeza
- Acción de la tabla: si el símbolo es 0, vaya a xxx; de lo contrario, si el símbolo es 1, vaya a xxx.
¿Cuáles y cuántos saltos son necesarios? El salto incondicional J xxx es simplemente J0 seguido inmediatamente por J1 (o viceversa). Wang (1957) también demuestra que solo se requiere un salto condicional, es decir, J0 xxx o J1 xxx. Sin embargo, con esta restricción, resulta difícil escribir instrucciones para la máquina. A menudo solo se utilizan dos, es decir
- { J0 xxx, J1 xxx}
- { J1 xxx, J xxx}
- { J0 xxx, J xxx},
pero el uso de los tres { J0 xxx, J1 xxx, J xxx} elimina instrucciones adicionales. En el ejemplo de Busy Beaver de 2 estados, usamos solo { J1 xxx, J xxx}.
Castor ocupado de 2 estados
La misión del castor ocupado es imprimir tantos como sea posible antes de detenerse. La instrucción "Imprimir" escribe un 1, la instrucción "Borrar" (no utilizada en este ejemplo) escribe un 0 (es decir, es lo mismo que P0). La cinta se mueve "Izquierda" o "Derecha" (es decir, la "cabeza" está estacionaria).
Tabla de estado para un castor ocupado de la máquina de Turing de 2 estados :
| Símbolo de cinta | Estado actual A | Estado actual B | ||||
|---|---|---|---|---|---|---|
| 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 | 1 | L | B | 1 | norte | H |
Instrucciones para la versión Post-Turing de un castor ocupado de 2 estados: observe que todas las instrucciones están en la misma línea y en secuencia. Esta es una desviación significativa de la versión "Turing" y tiene el mismo formato que lo que se llama un "programa de computadora":
| Instrucción # | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Instrucción | J1 | PAG | R | J | PAG | L | J | J1 | PAG | L | J | PAG | norte | J | H |
| Salta a # | 5 | 8 | 8 | 12 | 1 | 15 | |||||||||
| Etiqueta del estado de Turing | A | B | H |
Alternativamente, podríamos escribir la tabla como una cadena. El uso de "separadores de parámetros" ":" y separadores de instrucciones "," son totalmente nuestra elección y no aparecen en el modelo. No hay convenciones (pero vea Booth (1967) p. 374, y Boolos y Jeffrey (1974, 1999) p. 23), para algunas ideas útiles de cómo combinar las convenciones de diagramas de estado con las instrucciones, es decir, usar flechas para indicar el destino de los saltos). En el ejemplo que se muestra a continuación, las instrucciones son secuenciales a partir de "1", y los parámetros / "operandos" se consideran parte de sus instrucciones / "códigos de operación":
- J1: 5, P, R, J: 8, P, L, J: 8, J1: 12, P, L, J1: 1, P, N, J: 15, H
Notas
Referencias
- Stephen C. Kleene , Introducción a las metamatemáticas, North-Holland Publishing Company , Nueva York, décima edición de 1991, publicado por primera vez en 1952. El capítulo XIII es una excelente descripción de las máquinas de Turing; Kleene usa un modelo similar a Post en su descripción y admite que el modelo de Turing podría atomizarse aún más, ver nota al pie 1.
- Martin Davis , editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, Nueva York, 1965. Entre los artículos se incluyen los de Gödel , Church , Rosser , Kleene y Post.
- Martin Davis , "What is a computation", en Mathematics Today , Lynn Arthur Steen, Vintage Books (Random House), 1980. Un pequeño artículo maravilloso, quizás el mejor escrito sobre las Máquinas de Turing. Davis reduce la máquina de Turing a un modelo mucho más simple basado en el modelo de cálculo de Post. Incluye una pequeña biografía de Emil Post.
- Martin Davis , Computabilidad: con notas de Barry Jacobs , Instituto Courant de Ciencias Matemáticas, Universidad de Nueva York, 1974.
- Martin Davis , Ron Sigal , Elaine J. Weyuker , (1994) Computabilidad, complejidad y lenguajes: Fundamentos de la informática teórica - 2da edición , Academic Press: Harcourt, Brace & Company, San Diego, 1994 ISBN 0-12-206382- 1 (Primera edición, 1983).
- Fred Hennie , Introducción a la computabilidad , Addison-Wesley, 1977.
- Marvin Minsky , (1961), Recursive Unsolvability of Post's problem of 'Tag' and other Topics in Theory of Turing Machines , Annals of Mathematics, vol. 74, N ° 3, noviembre de 1961.
- Roger Penrose , The Emperor's New Mind: Concerning Computers, Minds and the Laws of Physics , Oxford University Press, Oxford, Inglaterra, 1990 (con correcciones). Cf. Capítulo 2, "Algoritmos y máquinas de Turing". Una presentación demasiado complicada (ver el artículo de Davis para un mejor modelo), pero una presentación completa de las máquinas de Turing y el problema de la detención , y el cálculo lambda de Church .
- Hao Wang (1957): "Una variante de la teoría de las máquinas informáticas de Turing", Revista de la Asociación de Maquinaria de Computación (JACM) 4, 63–92.