Equivalentes de la máquina de Turing

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 para la noción de un algoritmo informático.

Si bien no se ha demostrado que ninguno de los siguientes modelos tenga más poder que el modelo de máquina de Turing de cinta única, unidireccional, infinito y con múltiples símbolos, sus autores los definieron y utilizaron para investigar cuestiones y resolver problemas con mayor facilidad de lo que podrían haberlo hecho si se hubieran quedado con el modelo de máquina a de Turing .

Equivalencia de Turing

Se puede demostrar que muchas máquinas que podrían tener una capacidad computacional mayor que una simple máquina universal de Turing no tienen más potencia. ^[1] Tal vez calculen más rápido o utilicen menos memoria, o su conjunto de instrucciones sea menor, pero no pueden calcular con mayor potencia (es decir, más funciones matemáticas). (La tesis de Church-Turing plantea la hipótesis de que esto es cierto: cualquier cosa que pueda ser "calculada" puede ser calculada por alguna máquina de Turing.)

Los modelos de máquinas secuenciales

A todos los siguientes se les denomina "modelos de máquinas secuenciales" para distinguirlos de los "modelos de máquinas paralelas". ^[2]

El modelo de máquina A de Turing

La máquina A de Turing (como la llamó) tenía un extremo izquierdo y un extremo derecho infinito. Incluyó símbolos əə para marcar el extremo izquierdo. Se permitía un número finito de símbolos de cinta. Las instrucciones (si se trataba de una máquina universal) y la "entrada" y la "salida" se escribían únicamente en "cuadrados F", y los marcadores debían aparecer en "cuadrados E". En esencia, dividió su máquina en dos cintas que siempre se movían juntas. Las instrucciones aparecían en forma de tabla llamada "5-tuplas" y no se ejecutaban secuencialmente.

Los siguientes modelos son máquinas de Turing de cinta única pero restringidas 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 máquina completamente atomizadas.

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 { "marca", "blanco"=no_marca}. Cambió la noción de "cinta" de infinita unidireccional 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 secuencial de instrucciones.

Su modelo extremadamente simple puede emular cualquier máquina de Turing, y aunque su Formulación 1 de 1936 no utiliza 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 constituyendo un programa.

En un influyente artículo, Hao Wang redujo la " formulación 1 " de Post a máquinas que todavía utilizan una cinta binaria infinita de dos vías, pero cuyas instrucciones son más simples (al ser los componentes "atómicos" de las instrucciones de Post) y se ejecutan por defecto de forma secuencial (como un "programa informático"). Su objetivo principal declarado era ofrecer, como alternativa a la teoría de Turing, una que "fuera más económica en las operaciones básicas". Sus resultados fueron "formulaciones de programa" de una variedad de tales máquinas, incluida la máquina W de Wang de 5 instrucciones con el conjunto de instrucciones

{ SHIFT-IZQUIERDA, SHIFT-DERECHA, MARCAR-CUADRADO, BORRAR-CUADRADO, SALTAR-SI-CUADRADO-ESTÁ-MARCADO-a xxx }

y su máquina B de Wang de 4 instrucciones, severamente reducida ("B" por "básica") con el conjunto de instrucciones

{ SHIFT-IZQUIERDA, SHIFT-DERECHA, MARCAR-CUADRADO, SALTAR-SI-CUADRADO-ESTÁ-MARCADO-a xxx }

que ni siquiera tiene una instrucción ERASE-SQUARE.

Muchos autores introdujeron posteriormente variantes de las máquinas analizadas por Wang:

Minsky desarrolló la noción de Wang con su versión del modelo de "máquina contadora" (de cintas múltiples) que permitía el movimiento SHIFT-LEFT y SHIFT-RIGHT de los cabezales separados pero sin impresión en absoluto. ^[3] En este caso, las cintas tendrían extremos izquierdos, cada extremo marcado con una única "marca" para indicar el final. Fue capaz de reducir esto a una sola cinta, pero a expensas de introducir un movimiento de múltiples cintas cuadradas equivalente a la multiplicación y división en lugar del mucho más simple { SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT }.

Davis, al agregar una instrucción HALT explícita a una de las máquinas analizadas por Wang, utilizó un modelo con el conjunto de instrucciones

{ SHIFT-IZQUIERDA, SHIFT-DERECHA, BORRAR, MARCAR, SALTAR-SI-CUADRADO-ESTÁ MARCADO-a xxx, SALTAR-a xxx, DETENER }

y también se consideraron versiones con alfabetos de cinta de tamaño mayor a 2.

En consonancia 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 lenguaje de " programación estructurada " imperativo "sin GOTO" que se demostró que era Turing-completo .

En el análisis práctico, se suelen utilizar varios tipos de máquinas de Turing de cintas múltiples. Las máquinas de cintas múltiples son similares a las de cinta única, pero hay un número k constante de cintas independientes.

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). Las dos son computacionalmente equivalentes, es decir, es posible convertir cualquier NDTM en una DTM (y viceversa ) , aunque normalmente tienen tiempos de ejecución diferentes. Esto se puede demostrar mediante la construcción.

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 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 múltiples cintas en n pasos puede ser realizado por una máquina de Turing de dos cintas inconsciente en ⁠ ⁠${\displaystyle O(n\log n)}$ pasos. ^[4]

Las máquinas inconscientes se corresponden de manera lineal y escalonada con los circuitos lógicos combinacionales, cuando la complejidad de la tabla de transición se toma como constante. Por lo tanto, es posible realizar cálculos como problemas de circuitos en tamaño y profundidad (${\displaystyle O(n\log n)}$ ver Complejidad de circuitos ) . Esto mejora el resultado original de Cook y Levin . ${\displaystyle O(n)}$${\displaystyle O(n^{3})}$

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 denominado al miembro más primitivo de este grupo, es decir, la "máquina de contador", "máquina de registro". Y la realización más primitiva de una "máquina de contador" a veces se denomina "máquina de Minsky".

La máquina de registro del modelo primitivo es, en efecto, una máquina Post-Turing de dos símbolos y múltiples cintas con su comportamiento restringido de modo que sus cintas actúan como simples "contadores".

En la época de Melzak, Lambek y Minsky, la noción de "programa informático" produjo un tipo diferente de máquina simple con muchas cintas con extremos izquierdos cortados de una cinta post-Turing. En todos los casos, los modelos sólo permiten dos símbolos de cinta {marca, espacio en blanco}. ^[3]

Algunas versiones representan los números enteros positivos como una cadena o pila de marcas permitidas en un "registro" (es decir, una cinta con el extremo izquierdo), y una cinta en blanco representada por el conteo "0". Minsky eliminó la instrucción PRINT a expensas de proporcionar a su modelo una única marca obligatoria en el extremo izquierdo de cada cinta. ^[3]

En este modelo, las cintas de un solo extremo como registros 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

{ INCrementar el contenido del registro #r; DECrementar 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

{ BORRAR el contenido del registro r; ​​INCREMENTAR el contenido de r; comparar el contenido de r _i con r _j y si es igual entonces saltar a la instrucción z}

Aunque su modelo es más complicado que esta simple descripción, el modelo de "guijarros" de Melzak extendió esta noción de "contador" para permitir sumas y restas de múltiples guijarros.

Melzak reconoció un par de defectos graves en su modelo de registro/contramáquina: ^[5] (i) Sin una forma de direccionamiento indirecto no podría demostrar "fácilmente" que el modelo es equivalente a Turing , (ii) El programa y los registros estaban en "espacios" diferentes, por lo que los programas automodificables no serían fáciles. Cuando Melzak agregó el direccionamiento indirecto a su modelo, creó un modelo de máquina de acceso aleatorio.

(Sin embargo, con la numeración de Gödel de las instrucciones, Minsky ofreció una prueba de que con dicha numeración las funciones recursivas generales eran de hecho posibles; ofrece una prueba de que la recursión μ es de hecho 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 funciona solo 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). Las otras incluyen "CLEAR h" y un IF igualdad entre registros THEN salto 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 la RAM y MRAM
• N****: Versiones no deterministas de cualquiera de las anteriores con una N antes del nombre

El RASP es una memoria RAM con las instrucciones almacenadas junto con sus datos en el mismo «espacio», es decir, una secuencia de registros. La noción de un RASP fue descrita al menos tan temprano como por 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 se logra el direccionamiento indirecto simplemente modificando el operando de una instrucción. ^[6]

El modelo RASP original de Elgot y Robinson tenía sólo tres instrucciones al estilo del modelo de máquina de registros ^[7] , pero las colocaban en el espacio de registros junto con sus datos. (Aquí COPY toma el lugar de CLEAR cuando un registro, por ejemplo "z" o "0", comienza con 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 tanto el direccionamiento indirecto como el directo; algunos también permiten instrucciones "inmediatas", por ejemplo, "Cargar acumulador con la constante 3". Las instrucciones pueden ser de un conjunto altamente 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 "cargar acumulador" con constante o desde registro; STO es "almacenar acumulador"). Su sintaxis es la siguiente, excepto los saltos: "n, <n>, <<n>>" para "inmediato", "directo" e "indirecto"). Los saltos se realizan mediante dos "instrucciones de transferencia" TRA: salto incondicional mediante la inserción directa "n" o indirecta "< n >" del contenido del registro n en el contador de instrucciones, TRZ (salto condicional si el acumulador es cero de la misma manera que TRA):

{ AGREGAR n , AGREGAR < n >, AGREGAR << n >>, SUB n, SUB < n >, SUB << n >>, CLA n, CLA < n >, CLA << n >>, STO < n > , STO << n >>, TRA n, TRA < n >, TRZ n, TRA < n >, DETENER }

Un recién llegado es la máquina de modificación de almacenamiento de Schönhage o máquina de punteros . Otra versión es la máquina de Kolmogorov-Uspensky y la propuesta de "autómata de enlace" de Knuth. (Para referencias, véase máquina de punteros ). Al igual que 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.

Cualquiera de las máquinas basadas en cintas mencionadas anteriormente puede estar equipada con cintas de entrada y salida; cualquiera de las máquinas basadas en registros mencionadas anteriormente puede estar equipada con registros de entrada y salida dedicados. Por ejemplo, el modelo de máquina de puntero de Schönhage tiene dos instrucciones llamadas " entrada λ ₀ , λ ₁ " y " salida β ".

Es difícil estudiar la complejidad del espacio sublineal en máquinas de múltiples cintas con el modelo tradicional, porque una entrada de tamaño n ya ocupa espacio n . Por lo tanto, para estudiar clases DSPACE pequeñas , 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 desde" 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. Es igual que una máquina de Turing de k -cuerdas común, excepto que la función de transición δ está restringida de modo que la cinta de entrada nunca se puede cambiar y el cabezal de salida nunca se puede mover a la izquierda. Este modelo nos permite definir clases espaciales deterministas más pequeñas que las 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 de Turing de k cuerdas M que opera dentro de un límite de tiempo , hay${\displaystyle f(n)}$ una máquina de Turing de k cuerdas M ' ${\displaystyle (k+2)}$con entrada y salida, que opera dentro de un límite de tiempo .${\displaystyle O(f(n))}$

Las máquinas de Turing de k -cadenas con entrada y salida se pueden utilizar en la definición formal del recurso de complejidad DSPACE . ^[9]

• Máquina de Turing multidimensional: por ejemplo, un modelo de Schönhage utiliza los cuatro comandos de movimiento de la cabeza { Norte , Sur , Este , Oeste }. ^[10]
• Máquina de Turing de una sola cinta y múltiples cabezales: en una prueba de indecidibilidad del "problema de la etiqueta", Minsky, Shepherdson y Sturgis describieron máquinas con una sola cinta que podían leer a lo largo de la cinta con un cabezal y escribir más a lo largo de la cinta con otro. ^{[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