Una máquina Post-Turing [1] es una "formulación de programa" de un tipo de máquina de Turing , que comprende una variante del modelo de computación equivalente a Turing de Emil Post . 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 por el de Post en octubre. Una máquina Post-Turing utiliza 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 las ubicaciones de almacenamiento y la alteración de sus contenidos de uno en uno. Los nombres "programa Post-Turing" y "máquina Post-Turing" fueron utilizados por Martin Davis en 1973-1974 (Davis 1973, p. 69ff). Más tarde, en 1980, Davis utilizó el nombre "programa Turing-Post" (Davis, en Steen p. 241).
En su artículo de 1936 "Procesos combinatorios finitos: Formulación 1", Emil Post describió un modelo que, según su conjetura, es " lógicamente equivalente a la recursividad ".
El modelo de cálculo de Post difiere del modelo de máquina de Turing en una "atomización" adicional de los actos que una "computadora" humana realizaría durante un cálculo. [2]
El modelo de Post emplea un " espacio simbólico " que consiste en una "secuencia infinita de espacios o casillas bidireccionales", cada casilla capaz de estar en cualquiera de dos posibles condiciones, a saber, "marcada" (por ejemplo, con un único trazo vertical) y "no marcada" (vacía). Inicialmente, un número finito de casillas están marcadas, mientras que el resto no lo están. Un "trabajador" debe moverse entonces entre las casillas, estando y operando en una sola casilla a la vez, de acuerdo con un "conjunto finito de direcciones" ( instrucciones ) fijo, que están numeradas 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:
Entonces, la i -ésima "dirección" (instrucción) dada al trabajador debe ser una de las siguientes formas:
(El texto sangrado y en cursiva arriba son como en el original.) Post comenta que esta formulación está "en sus etapas iniciales" de desarrollo, y menciona varias posibilidades para una "mayor flexibilidad" en su "forma definitiva" final, incluyendo
Como se menciona brevemente en el artículo Máquina de Turing , Post, en su artículo de 1947 ( Recursive Unsolvability of a Problem of Thue ) atomizó las 5-tuplas de Turing en 4-tuplas:
Al igual que Turing, definió el borrado como la impresión del símbolo "S0". Por eso su modelo admitía cuatrillizos de sólo tres tipos (cf. Undecidable , p. 294):
En ese momento todavía conservaba la convención de máquina de estados de Turing: no había formalizado la noción de una supuesta ejecución secuencial de pasos hasta que una prueba específica de un símbolo "ramificó" la ejecución en otra parte.
Wang (1957, pero presentado a la ACM en 1954) es citado 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
Cualquier máquina de Turing de cinta binaria se convierte fácilmente en un "programa Wang" equivalente utilizando las instrucciones anteriores.
Martin Davis fue alumno de Emil Post y, junto con Stephen Kleene, completó su doctorado con Alonzo Church (Davis (2000) 1.ª y 2.ª notas al pie, pág. 188).
El siguiente modelo lo presentó en una serie de conferencias en el Courant Institute de la Universidad de Nueva York en 1973-1974. Este es el modelo al que Davis aplicó formalmente el nombre de "máquina post-Turing" con su "lenguaje post-Turing". [2] Se supone que las instrucciones se ejecutan secuencialmente (Davis 1974, p. 71):
El siguiente modelo aparece como ensayo ¿Qué es un cálculo? en Steen, páginas 241 a 267. Por alguna razón, Davis ha rebautizado su modelo como "máquina de Turing-Post" (con un retroceso 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:
"Un programa 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 ser reemplazada por un número definido (entero positivo)" (Davis en Steen, p. 247).
"Aunque la formulación de Turing que hemos presentado es más cercana en espíritu a la que originalmente dio Emil Post, fue el análisis de la computación que hizo Turing lo que hizo que esta formulación pareciera tan apropiada. Este lenguaje ha jugado un papel fundamental en la ciencia informática teórica." (Davis et al. (1994) p. 129)
Este modelo permite la impresión de múltiples símbolos. El modelo permite B (blanco) en lugar de S 0 . La cinta es infinita en ambas direcciones. Tanto la cabeza como la cinta se mueven, pero sus definiciones de DERECHA e IZQUIERDA siempre especifican el mismo resultado en ambos casos (Turing utilizó la misma convención).
Este modelo se reduce a las versiones binarias { 0, 1 } presentadas anteriormente, como se muestra aquí:
El siguiente método de "reducción" (descomposición, atomización) –de quintuplas de Turing de dos símbolos a una secuencia de instrucciones Post–Turing de dos 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 instrucciones Post-Turing en lugar de 7. No atomizó Wi0: "Escribe el símbolo Si0; ve al nuevo estado Mi0", y Wi1: "Escribe el símbolo Si1; ve 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 5-tuplas de Turing a instrucciones Post-Turing puede no resultar en un programa Post-Turing "eficiente", pero será fiel al programa de Turing original.
En el siguiente ejemplo, cada 5-tupla de Turing del castor ocupado de 2 estados se convierte en
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 dos estados, escrito como dos líneas de 5-tuplas, es:
La tabla representa una única "instrucción" de Turing, pero vemos que consta de dos líneas de 5-tuplas, una para el caso "símbolo de cinta bajo la cabeza = 1", la otra para el caso "símbolo de cinta bajo la cabeza = 0". Turing observó ( Undecidable , p. 119) que las dos columnas de la izquierda - "m-configuration" y "symbol" - representan la "configuración" actual de la máquina -su estado incluyendo 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 u otra configuración:
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 manera única). Debajo de cada salto (rama, destino) 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:
Y según las convenciones de la máquina Post-Turing, los "saltos" condicionales J0xxx, J1xxx constan de dos acciones:
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:
¿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,
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 }.
La misión del castor atareado es imprimir tantos unos como sea posible antes de detenerse. La instrucción "Imprimir" escribe un 1, la instrucción "Borrar" (no se utiliza en este ejemplo) escribe un 0 (es decir, es lo mismo que P0). La cinta se mueve "hacia la izquierda" o "hacia la derecha" (es decir, el "cabezal" permanece estacionario).
Tabla de estados para una máquina de Turing de dos estados :
Instrucciones para la versión post-Turing de un castor atareado de dos estados: observe que todas las instrucciones están en la misma línea y en secuencia. Esto es una desviación significativa de la versión "Turing" y tiene el mismo formato que lo que se denomina un "programa de computadora":
Como alternativa, podemos escribir la tabla como una cadena. El uso de los "separadores de parámetros" : " y los separadores de instrucciones "," son totalmente de nuestra elección y no aparecen en el modelo. No hay convenciones (pero véase Booth (1967) p. 374, y Boolos y Jeffrey (1974, 1999) p. 23), para algunas ideas útiles sobre cómo combinar las convenciones de los diagramas de estados con las instrucciones, es decir, utilizar flechas para indicar el destino de los saltos). En el ejemplo inmediatamente inferior, las instrucciones son secuenciales a partir de "1", y los parámetros/"operandos" se consideran parte de sus instrucciones/"códigos de operación":