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 cálculo 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 del 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 su contenido uno a la vez. Martin Davis utilizó los nombres "programa Post-Turing" y "máquina Post-Turing" 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, conjeturó, 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 mayor "atomización" 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 bidireccional de espacios o cajas", cada caja capaz de estar en cualquiera de dos condiciones posibles, a saber, "marcada" (como por un solo trazo vertical) y "sin marcar". " (vacío). Inicialmente, un número finito de casillas están marcadas y el resto sin marcar. Un "trabajador" debe entonces moverse entre las cajas, estando y operando en una sola caja a la vez, de acuerdo con un "conjunto de direcciones" finito y fijo ( instrucciones ), 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 por una, 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 será de una de las siguientes formas:
(El texto con sangría y cursiva de arriba es el mismo que 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 ( Insolvabilidad recursiva de un problema de Thue ) atomizó las 5 tuplas de Turing en 4 tuplas:
Al igual que Turing, definió el borrado como imprimir un símbolo "S0". Y así su modelo admitía cuatrillizos de sólo tres tipos (cf. Indecidible , p. 294):
En ese momento todavía conservaba la convención de la 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.
Para una reducción aún mayor (a solo cuatro instrucciones) del modelo Wang presentado aquí, consulte Wang B-machine .
A menudo se cita a Wang (1957, pero presentado a la ACM en 1954) (cf. Minsky (1967), p. 200) como la fuente de la "formulación de programas" de las máquinas de Turing de cinta binaria utilizando instrucciones numeradas del conjunto.
Cualquier máquina de Turing de cinta binaria se convierte fácilmente en un "programa Wang" equivalente siguiendo las instrucciones anteriores.
Martin Davis era un estudiante universitario de Emil Post. Junto con Stephen Kleene completó su doctorado. bajo Alonzo Church (Davis (2000) 1ª y 2ª notas al pie p. 188).
Presentó el siguiente modelo en una serie de conferencias en el Instituto Courant 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 a modo de ensayo ¿Qué es un cómputo? 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 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 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 ser reemplazada por una número definido (entero positivo)". (Davis en Steen, pág. 247).
"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 del cálculo lo que hizo que esta formulación pareciera 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. O la cabeza o la cinta se mueven, pero sus definiciones de DERECHA e IZQUIERDA siempre especifican el mismo resultado en cualquier caso (Turing usó 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), 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: "Escribe el símbolo Si0; pasa al nuevo estado Mi0", y Wi1: "Escribe 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 5 tuplas de Turing a instrucciones Post-Turing puede no dar como resultado un programa Post-Turing "eficiente", pero será fiel al programa de Turing original.
En el siguiente ejemplo, cada tupla de 5 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 2 estados, escrito como dos líneas de 5 tuplas, es:
La tabla representa solo una "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" y la otra para el caso "símbolo de cinta debajo del encabezado = 0". ". Turing observó ( Undecidable , 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 que incluye tanto la Cinta como la Tabla 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:
Después de la "rama de configuración" (J1 xxx) o (J0 xxx) la máquina sigue uno de los dos "comportamientos" siguientes. Enumeramos estos dos comportamientos en una línea y los numeramos (o etiquetamos) de forma secuencial (ú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 consta 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 de J1 (o viceversa). Wang (1957) también demuestra que sólo 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 sólo 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 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, el "cabezal" está estacionario).
Tabla de estados para un castor ocupado de máquina de Turing de 2 estados :
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":
Alternativamente, podríamos escribir la tabla como una cadena. El uso de "separadores de parámetros" ":" y separadores de instrucciones "," son enteramente de nuestra elección y no aparecen en el modelo. No hay convenciones (pero consulte Booth (1967) p. 374, y Boolos y Jeffrey (1974, 1999) p. 23), para obtener algunas ideas útiles sobre cómo combinar las convenciones del diagrama de estados con las instrucciones, es decir, usar flechas para indicar el destino de los saltos). En el ejemplo inmediatamente siguiente, las instrucciones son secuenciales a partir de "1" y los parámetros/"operandos" se consideran parte de sus instrucciones/"códigos de operación":