Hispanopedia WikiUna máquina de Post o 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 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 modificación de su contenido una a una. Los nombres "programa Post-Turing" y "máquina Post-Turing" fueron utilizados por Martin Davis en 1973-1974 (Davis 1973, p. 69 y ss.). Posteriormente, en 1980, Davis utilizó el nombre "programa Turing-Post" (Davis, en Steen, p. 241).
1936: Modelo de poste
En su artículo de 1936, "Procesos combinatorios finitos : formulación 1", Emil Post describió un modelo que, según conjeturaba, era " lógicamente equivalente a la recursividad ".
El modelo de computación de Post difiere del modelo de la máquina de Turing en una "atomización" adicional de los actos que una "computadora" humana realizaría durante una computación. [ 2 ]
El modelo de Post emplea un " espacio de símbolos " que consiste en una "secuencia infinita bidireccional de espacios o casillas", cada casilla capaz de estar en una de dos condiciones posibles: "marcada" (por ejemplo, con un solo trazo vertical) o "sin marcar" (vacía). Inicialmente, un número finito de casillas están marcadas, mientras que el resto están sin marcar. Un "trabajador" debe entonces moverse entre las casillas, estando y operando en una sola casilla a la vez, de acuerdo con un "conjunto finito" de instrucciones , numeradas en orden (1, 2, 3, ..., n ). Comenzando en una casilla "seleccionada como punto de partida", el trabajador debe seguir el conjunto de instrucciones una a una, comenzando con la instrucción 1.
Existen cinco operaciones primitivas diferentes que el trabajador puede realizar:
- (a) Marcar la casilla en la que se encuentra, si está vacía.
- (b) Borrar la marca en la casilla en la que se encuentra, si está marcada.
- (c) Moverse a la casilla que está a su derecha
- (d) Moverse a la casilla que está a su izquierda
- (e) Determinar si la caja en la que se encuentra está o no marcada.
Entonces, la i -ésima "direcció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 ″.
- Detener .
(El texto anterior con sangría y en cursiva se mantiene igual que en el original). Post señala que esta formulación se encuentra "en sus etapas iniciales" de desarrollo y menciona varias posibilidades para una "mayor flexibilidad" en su "forma definitiva" final, incluyendo:
- reemplazar la infinidad de cajas por un espacio de símbolos finito y extensible, "extendiendo 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 sirven como punteros, que el trabajador puede 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 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:
- "Nuestros cuatrillizos son quintrillizos en el desarrollo de Turing. Es decir, donde nuestra instrucción estándar ordena una impresión (sobreimpresión) o un movimiento, a la izquierda o a la derecha, la instrucción estándar de Turing siempre ordena una impresión y un movimiento, a la derecha, a la izquierda o ninguno" (nota al pie 12, Undecidible , pág. 300).
Al igual que Turing, definió el borrado como la impresión de un símbolo "S0". Y así, su modelo admitía cuartetos de solo tres tipos (cf. Undecidible , p. 294):
- q i S j L q l ,
- q i S j R q l ,
- q i S j S k q l
En ese momento, aún mantenía la convención de la máquina de estados de Turing; no había formalizado la noción de una ejecución secuencial supuesta de pasos hasta que una prueba específica de un símbolo "ramificaba" la ejecución en otro lugar.
1954, 1957: Modelo Wang
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
- escribir 0
- escribir 1
- Muévase a la izquierda
- Muévete a la derecha
- Si escanea 0, vaya a la instrucción i.
- Si escanea 1, vaya a la instrucción j.
Cualquier máquina de Turing de cinta binaria se puede convertir fácilmente en un "programa Wang" equivalente utilizando las instrucciones anteriores.
1974: primer modelo Davis
Martin Davis fue estudiante de pregrado de Emil Post. Junto con Stephen Kleene , completó su doctorado bajo la dirección de Alonzo Church (Davis (2000), notas al pie 1 y 2, pág. 188).
El siguiente modelo lo presentó en una serie de conferencias en el Instituto Courant de la Universidad de Nueva York entre 1973 y 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):
1978: segundo modelo Davis
El siguiente modelo aparece como un ensayo titulado " ¿Qué es un cálculo?" en las páginas 241-267 de Steen. Por alguna razón, Davis ha renombrado su modelo como una "máquina de Turing-Post" (con una retractación 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. Citando a Davis: "Ahora estamos listos para presentar el lenguaje de programación Turing-Post. En este lenguaje hay siete tipos de instrucciones:
- "IMPRESIÓN 1
- "IMPRIMIR 0
- "VAYA A LA DERECHA"
- "VAYAN A LA IZQUIERDA"
- "VAYA AL PASO i SI SE ESCANEA EL 1"
- "VAYA AL PASO i SI SE ESCANEA 0"
- "DETENER
«Un programa de Turing-Post es, por tanto, una lista de instrucciones, cada una de las cuales pertenece a uno de estos siete tipos. Por supuesto, en un programa real, la letra i en un paso del quinto o sexto tipo debe sustituirse por un número entero positivo definido». (Davis en Steen, p. 247).
1994 (segunda edición): modelo de programa Post-Turing de Davis-Sigal-Weyuker
«Si bien la formulación de Turing que hemos presentado se asemeja más a la propuesta originalmente por Emil Post, fue el análisis que Turing hizo de la computación lo que hizo que esta formulación resultara tan apropiada. Este lenguaje ha desempeñado un papel fundamental en la 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 (en blanco) en lugar de S 0. La cinta es infinita en ambas direcciones. Tanto el cabezal 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).
- IMPRIMIR σ ;Reemplazar el símbolo escaneado con σ
- SI σ IR A L; SI el símbolo escaneado es σ ENTONCES ir a la primera instrucción etiquetada como L
- DERECHA; Escanee el cuadrado inmediatamente a la derecha del cuadrado que se está escaneando actualmente.
- IZQUIERDA; Escanee el cuadrado inmediatamente a la izquierda del cuadrado que se está escaneando actualmente.
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 = BLANCO
- IMPRIMIR 1; Reemplazar el símbolo escaneado con 1
- SI 0 IR A L; SI el símbolo escaneado es 0 ENTONCES ir a la primera instrucción etiquetada como L
- SI 1 IR A L; SI el símbolo escaneado es 1 ENTONCES ir a la primera instrucción etiquetada como L
- DERECHA; Escanee el cuadrado inmediatamente a la derecha del cuadrado que se está escaneando actualmente.
- IZQUIERDA; Escanee el cuadrado inmediatamente a la izquierda del cuadrado que se está escaneando actualmente.
Ejemplos de la máquina Post-Turing
Atomización de quíntuplas de Turing en una secuencia de instrucciones post-Turing.
El siguiente método de "reducción" (descomposición, atomización) —de 5-tuplas de Turing de 2 símbolos a una secuencia de instrucciones post-Turing de 2 símbolos— se puede encontrar en Minsky (1961). Él 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 (cursivas en el original, cf. Minsky (1961), pág. 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: "Escribir el símbolo Si0; pasar al nuevo estado Mi0", ni Wi1: "Escribir el símbolo Si1; pasar 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 Post-Turing puede que no dé como resultado 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
- un "salto" condicional inicial (goto, bifurcación), 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:
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 el cabezal = 1", y la otra para el caso "símbolo de cinta bajo el cabezal = 0". Turing observó ( Undecidible , p. 119) que las dos columnas de la izquierda —"m-configuración" y "símbolo"— representan la "configuración" actual de la máquina —su estado, incluyendo tanto la cinta como la tabla en ese instante— y las últimas tres columnas representan su "comportamiento" subsiguiente. Como la máquina no puede estar en dos "estados" a la vez, debe "ramificar" hacia una configuración u otra:
Tras 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, destino) colocamos su "número" (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:
- Acción de la cinta: {P, E, L, R}, luego
- Acción de la tabla: pasar 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: observe el símbolo en la cinta debajo del cabezal.
- Acción de la tabla: Si el símbolo es 0 (1) y J0 (J1), entonces vaya a xxx; de lo contrario, vaya a la siguiente instrucción en la 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: observe el símbolo en la cinta debajo del cabezal.
- Acción de la tabla: Si el símbolo es 0, entonces vaya a xxx; de lo contrario, si el símbolo es 1, entonces vaya a xxx.
¿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 solo se requiere un salto condicional, es decir, J0 xxx o J1 xxx. Sin embargo, con esta restricción, la máquina se vuelve difícil de escribir instrucciones. A menudo solo se usan 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 Busy Beaver de 2 estados, usamos solo { J1 xxx, J xxx }.
castor ocupado de dos estados
La misión del castor trabajador es imprimir tantos unos 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 "a la izquierda" o "a la derecha" (es decir, el "cabezal" está fijo).
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 dos estados: observe que todas las instrucciones están en la misma línea y en secuencia. Esto representa una diferencia significativa con respecto a la versión "Turing" y tiene el mismo formato que lo que se denomina un " programa informático ":
Alternativamente, podríamos escribir la tabla como una cadena. El uso de "separadores de parámetros" ":" y separadores de instrucciones "," es una elección completamente nuestra y no aparece en el modelo. No hay convenciones (pero véase Booth (1967), pág. 374, y Boolos y Jeffrey (1974, 1999), pág. 23), para obtener algunas ideas útiles sobre cómo combinar las convenciones de diagramas de estados con las instrucciones, es decir, usar flechas para indicar el destino de los saltos). En el ejemplo inmediatamente inferior, las instrucciones son secuenciales comenzando desde "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
- ↑ Rajendra Kumar, Teoría de los autómatas , Tata McGraw-Hill Education, 2010, pág. 343.
- 1 2 En su capítulo XIII Funciones Computables , Kleene adopta el modelo de Post; el modelo de Kleene utiliza un espacio en blanco y un símbolo "marca de conteo ¤" (Kleene p. 358), un "tratamiento más cercano en algunos aspectos al de Post 1936. Post 1936 consideró la computación con una cinta infinita de 2 vías y solo 1 símbolo" (Kleene p. 361). Kleene observa que el tratamiento de Post proporcionó una reducción adicional a "actos atómicos" (Kleene p. 357) del "acto de Turing" (Kleene p. 379). Como lo describe Kleene, "El acto de Turing" es la combinación de 3 acciones (secuenciales en el tiempo) especificadas en una línea de una tabla de Turing: (i) imprimir-símbolo/borrar/no hacer nada seguido de (ii) mover-cinta-izquierda/mover-cinta-derecha/no hacer nada seguido de (iii) probar-cinta-ir-a-la-siguiente-instrucción: por ejemplo, "s1Rq1" significa "Imprimir el símbolo "¤", luego mover la cinta a la derecha, luego si el símbolo de la cinta es "¤" entonces ir al estado q1". (Véase el ejemplo de Kleene, pág. 358). Kleene observa que Post atomizó estas 3-acciones aún más en dos tipos de 2-acciones. El primer tipo es una acción de "imprimir/borrar", el segundo es una acción de "mover cinta izquierda/derecha": (1.i) imprimir-símbolo/borrar/no hacer nada seguido de (1.ii) cinta de prueba-ir-a-la-siguiente-instrucción, O (2.ii) mover-cinta-izquierda/mover-cinta-derecha/no hacer nada seguido de (2.ii) cinta de prueba-ir-a-la-siguiente-instrucción. Pero Kleene observa que mientras
- "De hecho, podría argumentarse que el acto de la máquina de Turing ya es compuesto y consiste psicológicamente en una impresión y un cambio en el estado mental, seguidos de un movimiento y otro estado mental [y] Post 1947 separa así el acto de Turing en dos; no lo hemos hecho aquí, principalmente porque ahorra espacio en las tablas de la máquina no hacerlo." (Kleene, p. 379)
Referencias
- Stephen C. Kleene , Introducción a las metamatemáticas, North-Holland Publishing Company , Nueva York, 10.ª edición, 1991, publicado originalmente en 1952. El capítulo XIII ofrece una excelente descripción de las máquinas de Turing; Kleene utiliza un modelo similar al de Post en su descripción y admite que el modelo de Turing podría atomizarse aún más (véase la nota al pie 1).
- Martin Davis , editor: The Undecidable, Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions , Raven Press, Nueva York, 1965. Los artículos incluyen los de Gödel , Church , Rosser , Kleene y Post.
- Martin Davis , «¿Qué es un cálculo?», en Matemáticas Hoy , Lynn Arthur Steen, Vintage Books (Random House), 1980. Un artículo breve pero excelente, quizás el mejor jamás escrito sobre 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 breve 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 – 2.ª 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, No. 3, noviembre de 1961.
- Roger Penrose , La nueva mente del emperador: Sobre las computadoras, las mentes y las leyes de la física , Oxford University Press, Oxford, Inglaterra, 1990 (con correcciones). Cf. Capítulo 2, "Algoritmos y máquinas de Turing". Una presentación demasiado compleja (véase el artículo de Davis para un modelo mejor), pero una presentación exhaustiva de las máquinas de Turing y el problema de la parada , y el cálculo lambda de Church .
- Hao Wang (1957): "Una variante de la teoría de Turing sobre las máquinas de computación", Journal of the Association for Computing Machinery (JACM) 4, 63–92.
- Máquina de Turing
- Modelos de computación
