Una máquina de Turing es un dispositivo informático hipotético, concebido por primera vez por Alan Turing en 1936. Las máquinas de Turing manipulan símbolos en una tira de cinta potencialmente infinita de acuerdo con una tabla finita de reglas, y proporcionan los fundamentos teóricos de la noción de algoritmo informático.
Si bien ninguno de los siguientes modelos ha demostrado tener más poder que el modelo de máquina de Turing de múltiples símbolos, infinito unidireccional y de una sola cinta, sus autores los definieron y usaron para investigar preguntas y resolver problemas más fácilmente de lo que podrían haberlo hecho. si se hubieran quedado con Turing es un modelo -máquinas.
Máquinas equivalentes al modelo de máquina de Turing
Equivalencia de Turing
Se puede demostrar que muchas máquinas de las que se podría pensar que tienen más capacidad computacional que una simple máquina universal de Turing no tienen más potencia. [1] Quizás computen más rápido o usen menos memoria, o su conjunto de instrucciones puede ser más pequeño, pero no pueden computar con más potencia (es decir, más funciones matemáticas). (La tesis de Church-Turing plantea la hipótesis de que esto es cierto: que cualquier máquina de Turing puede calcular cualquier cosa que pueda "calcularse").
Los modelos de máquina secuencial
Todos los siguientes se denominan "modelos de máquinas secuenciales" para distinguirlos de los "modelos de máquinas paralelas". [2]
Máquinas de Turing basadas en cinta
El modelo de una máquina de Turing
La máquina-a de Turing (como él la llamó) tenía un extremo izquierdo, un extremo derecho infinito. Proporcionó los símbolos əə para marcar el extremo izquierdo. Se permitió un número finito de símbolos de cinta. Las instrucciones (si es una máquina universal) y la "entrada" y la "salida" se escribieron sólo en "F-cuadrados", y los marcadores debían aparecer en "E-cuadrados". En esencia, dividió su máquina en dos cintas que siempre se movían juntas. Las instrucciones aparecieron en una forma tabular llamada "5-tuplas" y no se ejecutaron secuencialmente.
Máquinas de una sola cinta con símbolos restringidos y / o instrucciones restringidas
Los siguientes modelos son máquinas Turing de una sola cinta pero restringidos con (i) símbolos de cinta restringidos {marca, espacio en blanco} y / o (ii) instrucciones secuenciales, similares a las de una computadora, y / o (iii) acciones de la máquina completamente atomizadas.
Modelo de cálculo de "Formulación 1" de Post
Emil Post en una descripción independiente de un proceso computacional, redujo los símbolos permitidos al conjunto binario equivalente de marcas en la cinta {"mark", "blank" = not_mark}. Cambió la noción de "cinta" de 1 vía infinita a la derecha a un conjunto infinito de habitaciones, cada una con una hoja de papel en ambas direcciones. Atomizó las 5 tuplas de Turing en 4 tuplas: instrucciones de movimiento separadas de las instrucciones de impresión / borrado. Aunque su modelo de 1936 es ambiguo al respecto, el modelo de Post de 1947 no requería la ejecución de instrucciones secuenciales.
Su modelo extremadamente simple puede emular cualquier máquina de Turing, y aunque su Formulación 1 de 1936 no usa la palabra "programa" o "máquina", es efectivamente una formulación de una computadora programable muy primitiva y un lenguaje de programación asociado , con las cajas actuando como una memoria de cadena de bits ilimitada y el conjunto de instrucciones que constituyen un programa.
Máquinas Wang
En un artículo influyente, Hao Wang redujo la " formulación 1 " de Post a máquinas que todavía usan una cinta binaria infinita bidireccional, pero cuyas instrucciones son más simples, siendo los componentes "atómicos" de las instrucciones de Post, y se ejecutan de forma predeterminada secuencialmente (como un "programa de computadora"). Su principal propósito declarado era ofrecer, como alternativa a la teoría de Turing, una que "sea más económica en las operaciones básicas". Sus resultados fueron "formulaciones de programas" de una variedad de tales máquinas, incluida la máquina Wang W de 5 instrucciones con el conjunto de instrucciones
- {MAYÚS-IZQUIERDA, MAYÚS-DERECHA, MARCAR-CUADRADO, BORRAR-CUADRADO, SALTAR-SI-CUADRADO-MARCADO-a xxx}
y su máquina Wang B de 4 instrucciones más severamente reducida ("B" para "básico") con el conjunto de instrucciones
- {MAYÚS-IZQUIERDA, MAYÚS-DERECHA, MARCA-CUADRADO, SALTAR-SI-CUADRADO-MARCADO-a xxx}
que ni siquiera tiene una instrucción ERASE-SQUARE.
Más tarde, muchos autores introdujeron variantes de las máquinas discutidas por Wang:
Minsky desarrolló la noción de Wang con su versión del modelo de "máquina de contador" (de varias cintas) que permitía el movimiento SHIFT-IZQUIERDA y SHIFT-RIGHT de los cabezales separados pero sin imprimir en absoluto. [3] En este caso, las cintas se terminarían a la izquierda, cada extremo marcado con una única "marca" para indicar el final. Pudo reducir esto a una sola cinta, pero a expensas de introducir un movimiento cuadrado de varias cintas equivalente a la multiplicación y división en lugar del mucho más simple {MAYÚS-IZQUIERDA = DISMINUCIÓN, MAYÚS-DERECHA = INCREMENTO}.
Davis, agregando una instrucción HALT explícita a una de las máquinas discutidas por Wang, usó un modelo con el conjunto de instrucciones
- {MAYÚS-IZQUIERDA, MAYÚS-DERECHA, BORRAR, MARCAR, SALTAR-SI-CUADRADO-MARCADO-a xxx, SALTAR-a xxx, DETENER}
y también consideró versiones con alfabetos de cinta de tamaño superior a 2.
El lenguaje de máquina teórico P de Böhm "
De acuerdo con el proyecto de Wang de buscar una teoría equivalente a Turing "económica en las operaciones básicas", y deseando evitar saltos incondicionales, un lenguaje teórico notable es el lenguaje de 4 instrucciones P " introducido por Corrado Böhm en 1964 - el primer" GOTO -Lenguaje de programación estructurado "imperativo" menos que se pruebe Turing-completo .
Máquinas de Turing de cintas múltiples
En el análisis práctico, a menudo se utilizan varios tipos de máquinas de Turing de cintas múltiples. Las máquinas de cintas múltiples son similares a las de una sola cinta, pero hay un número constante k de cintas independientes.
Máquinas de Turing deterministas y no deterministas
Si la tabla de acciones tiene como máximo una entrada para cada combinación de símbolo y estado, entonces la máquina es una "máquina de Turing determinista" (DTM). Si la tabla de acciones contiene múltiples entradas para una combinación de símbolo y estado, entonces la máquina es una "máquina de Turing no determinista" (NDTM). Los dos son computacionalmente equivalentes, es decir, es posible convertir cualquier NDTM en un DTM (y viceversa ) , aunque suelen tener diferentes tiempos de ejecución. Esto se puede demostrar mediante la construcción.
Máquinas de Turing ajenas
Una máquina de Turing inconsciente es una máquina de Turing en la que, para cada longitud de entrada, el movimiento de los distintos cabezales es una función fija del tiempo, independiente de la entrada. En otras palabras, hay una secuencia predeterminada en la que se escanean, avanzan y escriben las distintas cintas. Los valores reales que se escriben en la cinta en cualquier paso aún pueden ser diferentes para cada entrada de esa longitud. Pippenger y Fischer demostraron que cualquier cálculo que pueda ser realizado por una máquina de Turing de cintas múltiples en n pasos puede ser realizado por una máquina de Turing de dos cintas inconsciente enpasos. [4]
Registrar modelos de máquinas
Peter van Emde Boas incluye todas las máquinas de este tipo en una clase, "la máquina de registro". [2] Sin embargo, históricamente la literatura también ha llamado al miembro más primitivo de este grupo, es decir, "la máquina de contador" - "la máquina de registro". Y la encarnación más primitiva de una "máquina contraria" se llama a veces la "máquina de Minsky".
La "máquina contadora", también llamada modelo de "máquina registradora"
La máquina de registro de modelos primitivos es, en efecto, una máquina Post-Turing de 2 símbolos de varias cintas con su comportamiento restringido, por lo que sus cintas actúan como simples "contadores".
En la época de Melzak, Lambek y Minsky, la noción de un "programa de computadora" produjo un tipo diferente de máquina simple con muchas cintas de extremo izquierdo cortadas de una cinta Post-Turing. En todos los casos, los modelos permiten sólo dos símbolos de cinta {marca, en blanco}. [3]
Algunas versiones representan los números enteros positivos como sólo una cadena / pila de marcas permitidas en un "registro" (es decir, una cinta con el extremo izquierdo) y una cinta en blanco representada por el recuento "0". Minsky eliminó la instrucción PRINT a costa de proporcionar a su modelo una única marca obligatoria en el extremo izquierdo de cada cinta. [3]
En este modelo, las cintas como registros de un solo extremo se consideran "contadores", y sus instrucciones se limitan a solo dos (o tres si la instrucción TEST / DECREMENT está atomizada). Dos conjuntos de instrucciones comunes son los siguientes:
- (1): {INC (r), DEC (r), JZ (r, z)}, es decir
- {Incremento del contenido del registro #r; Disminuir el contenido del registro #r; SI el contenido de # r = cero ENTONCES Saltar a la instrucción #z}
- (2): {CLR (r); INC (r); JE (r i , r j , z)}, es decir
- {CONTENIDO CLARO del registro r; Incremento del contenido de r; compare el contenido de r i con r j y, si es igual, vaya a la instrucción z}
Aunque su modelo es más complicado que esta simple descripción, el modelo de "guijarros" de Melzak amplió esta noción de "contador" para permitir sumas y restas de múltiples guijarros.
El modelo de máquina de acceso aleatorio (RAM)
Melzak reconoció un par de defectos graves en su modelo de registro / contra-máquina: [5] (i) Sin una forma de direccionamiento indirecto, no podría mostrar "fácilmente" que el modelo es equivalente a Turing , (ii) El programa y los registros estaban en diferentes "espacios", por lo que los programas de modificación automática no serían fáciles. Cuando Melzak agregó direccionamiento indirecto a su modelo, creó un modelo de máquina de acceso aleatorio.
(Sin embargo, con la numeración de las instrucciones de Gödel, Minsky ofreció una prueba de que con tal numeración las funciones recursivas generales eran realmente posibles; ofrece una prueba de que la recursividad μ es realmente posible [3] ).
A diferencia del modelo RASP, el modelo RAM no permite que las acciones de la máquina modifiquen sus instrucciones. A veces, el modelo solo funciona de registro a registro sin acumulador, pero la mayoría de los modelos parecen incluir un acumulador.
van Emde Boas divide los distintos modelos de RAM en varios subtipos: [2]
- SRAM, la "RAM sucesora" con una sola instrucción aritmética, la sucesora (INCREMENT h). Los otros incluyen "CLEAR h" y un IF igualdad entre registros ENTONCES salta a xxx.
- RAM: el modelo estándar con suma y resta
- MRAM: la RAM aumentada con multiplicación y división
- BRAM, MBRAM: versiones booleanas bit a bit de RAM y MRAM
- N ****: versiones no deterministas de cualquiera de los anteriores con una N antes del nombre
El modelo de máquina del programa almacenado de acceso aleatorio (RASP)
El RASP es una RAM con las instrucciones almacenadas junto con sus datos en el mismo "espacio", es decir, secuencia de registros. La noción de RASP se describió al menos ya en Kiphengst. Su modelo tenía un "molino", un acumulador, pero ahora las instrucciones estaban en los registros con los datos, la llamada arquitectura de von Neumann . Cuando el RASP tiene registros pares e impares alternados, el par contiene el "código de operación" (instrucción) y el impar contiene su "operando" (parámetro), entonces el direccionamiento indirecto se logra simplemente modificando el operando de una instrucción. [6]
El modelo RASP original de Elgot y Robinson tenía sólo tres instrucciones a la manera del modelo de máquina de registro, [7] pero las colocaron en el espacio de registro junto con sus datos. (Aquí COPY toma el lugar de CLEAR cuando un registro, por ejemplo, "z" o "0" comienza con 0 y siempre contiene 0. Este truco no es inusual. La unidad 1 en el registro "unit" o "1" también es útil).
- {INC (r), COPIA (r i , r j ), JE (r i , r i , z)}
Los modelos RASP permiten direccionamiento directo e indirecto; algunos también permiten instrucciones "inmediatas", por ejemplo, "Acumulador de carga con constante 3". Las instrucciones pueden ser de un conjunto muy restringido, como las siguientes 16 instrucciones de Hartmanis. [8] Este modelo utiliza un acumulador A. Los mnemónicos son los que utilizaron los autores (su CLA es "acumulador de carga" con constante o de registro; STO es "acumulador de tienda"). Su sintaxis es la siguiente, excepto los saltos: "n,
- {ADD n, ADD
, ADD << n >>, SUB n, SUB , SUB << n >>, CLA n, CLA , CLA << n >>, STO , STO << n >>, TRA n, TRA , TRZ n, TRA , HALT}
El modelo de máquina Pointer
Un recién llegado relativamente es la máquina de modificación de almacenamiento de Schönhage o la máquina de puntero . Otra versión es la máquina Kolmogorov-Uspensii, y la propuesta del "autómata de enlace" de Knuth. (Para obtener referencias, consulte la máquina de puntero ). Como un diagrama de máquina de estados, un nodo emite al menos dos "bordes" etiquetados (flechas) que apuntan a otro nodo o nodos que a su vez apuntan a otros nodos, etc. El mundo exterior apunta al nodo central.
Máquinas con entrada y salida
Cualquiera de las máquinas de cinta anteriores puede equiparse con cintas de entrada y salida; cualquiera de las máquinas basadas en registros anteriores puede equiparse con registros de entrada y salida dedicados. Por ejemplo, el modelo de máquina de puntero de Schönhage tiene dos instrucciones llamadas " entrada λ 0 , λ 1 " y " salida β ".
Es difícil estudiar la complejidad del espacio sublineal en máquinas de cintas múltiples con el modelo tradicional, porque una entrada de tamaño n ya ocupa el espacio n . Por lo tanto, para estudiar pequeñas clases de DSPACE , debemos utilizar un modelo diferente. En cierto sentido, si nunca "escribimos" en la cinta de entrada, no queremos cobrarnos por este espacio. Y si nunca "leemos" nuestra cinta de salida, no queremos cobrarnos por este espacio.
Resolvemos este problema introduciendo una máquina de Turing de k- cuerdas con entrada y salida. Esto es lo mismo que una máquina de Turing ordinaria de k- cuerdas, excepto que la función de transición δ está restringida para que la cinta de entrada nunca se pueda cambiar y el cabezal de salida nunca se pueda mover hacia la izquierda. Este modelo nos permite definir clases espaciales deterministas más pequeñas que lineales. Las máquinas de Turing con entrada y salida también tienen la misma complejidad temporal que otras máquinas de Turing; en palabras de Papadimitriou 1994 Prop 2.2:
- Para cualquier máquina M de Turing de cuerdas k que opere dentro de un límite de tiempo hay un -Máquina de Turing de cuerda M ' con entrada y salida, que opera dentro de un límite de tiempo .
Las máquinas de Turing de cadena k con entrada y salida se pueden utilizar en la definición formal del recurso de complejidad DSPACE . [9]
Otras máquinas y métodos equivalentes
- Máquina de Turing multidimensional: por ejemplo, un modelo de Schönhage utiliza los cuatro comandos de movimiento de la cabeza { N orth, S outh, E ast, W est}. [10]
- Máquina de Turing de una sola cinta y múltiples cabezales: en una prueba indecidible del "problema de la etiqueta", Minsky y Shepherdson y Sturgis describieron máquinas con una sola cinta que podían escribir a lo largo de la cinta con una cabeza y leer más a lo largo de la cinta con otra. . [11] [12]
- El algoritmo de Markov es otro modelo computacional notablemente simple, basado en la reescritura de cadenas, equivalente a las máquinas de Turing.
- Cálculo lambda
- Autómata de cola
Referencias
- ^ John Hopcroft y Jeffrey Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Addison – Wesley, Reading Mass. ISBN 0-201-02988-X.
- ^ a b c Peter van Emde Boas , Modelos de máquinas y simulaciones ; Jan van Leeuwen , ed. Manual de Informática Teórica. Volumen A: Algoritmos y complejidad , pág. 3-66, The MIT Press / Elsevier, 1990. ISBN 0-262-72014-0 (volumen A). QA76.H279 1990.
- ^ a b c d Marvin Minsky , Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc., Nueva Jersey, 1967. Consulte el Capítulo 8, Sección 8.2 "Inestabilidad del problema de detención".
- ^ Pippenger, Nicholas ; Fischer, Michael J. (1979), "Relaciones entre medidas de complejidad", J ACM , 26 (3): 361–381, doi : 10.1145 / 322123.322138
- ^ ZA Melzak , Un enfoque aritmético informal a la computabilidad y la computación , Boletín matemático canadiense, vol. 4, no. 3. Septiembre de 1961 páginas 279–293.
- ^ Stephen A. Cook y Robert A. Reckhow (1972), Máquinas de acceso aleatorio limitadas en el tiempo , Journal of Computer Systems Science 7 (1973), 354–375.
- ^ Calvin Elgot y Abraham Robinson (1964), Máquinas de programa almacenado de acceso aleatorio, un enfoque de lenguajes de programación , Revista de la Asociación de Maquinaria de Computación, vol. 11, núm. 4 (octubre de 1964), págs. 365–399.
- ^ J. Hartmanis (1971), "Complejidad computacional de las máquinas de programas almacenados de acceso aleatorio", Teoría de sistemas matemáticos 5, 3 (1971) pp. 232-245.
- ^ Christos Papadimitriou (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1. Capítulo 2: Máquinas de Turing, págs. 19–56.
- ^ A. Schōnhage (1980), Máquinas de modificación de almacenamiento , Sociedad de matemáticas industriales y aplicadas, SIAM J. Comput. Vol. 9, N ° 3, agosto de 1980.
- ^ Marvin Minsky (15 de agosto de 1960). "Inestabilidad recursiva del problema de Post de 'etiqueta' y otros temas en la teoría de las máquinas de Turing". Annals of Mathematics . Annals of Mathematics. 74 (3): 437–455. doi : 10.2307 / 1970290 . JSTOR 1970290 .
- ^ John C. Shepherdson y HE Sturgis recibieron en diciembre de 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10: 217-255, 1963