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 se ha demostrado que ninguno de los siguientes modelos tiene más poder que el modelo de máquina de Turing de múltiples símbolos, unidireccional e infinito, sus autores los definieron y utilizaron para investigar preguntas y resolver problemas más fácilmente de lo que podrían haberlo hecho. si se hubieran quedado con el modelo de máquina de Turing.
equivalencia de turing
Se puede demostrar que muchas máquinas 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] Es posible que calculen más rápido, tal vez, o utilicen menos memoria, o que su conjunto de instrucciones sea más pequeño, pero no pueden calcular 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 cosa que pueda ser "calculada" puede ser calculada por alguna máquina de Turing).
Los modelos de máquinas secuenciales.
Todos los siguientes se denominan "modelos de máquinas secuenciales" para distinguirlos de los "modelos de máquinas paralelas". [2]
El modelo de máquina de Turing
La máquina a de Turing (como él la llamó) tenía un extremo izquierdo y un extremo derecho infinito. Proporcionó símbolos əə para marcar el extremo izquierdo. Se permitía un número finito de símbolos de cinta. Las instrucciones (si era una máquina universal) y la "entrada" y la "salida" se escribían sólo en los "cuadrados F", y los marcadores debían aparecer en los "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 denominada "5 tuplas" y no se ejecutaban de forma secuencial.
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 { "mark", "blank"=not_mark }. Cambió la noción de "cinta" de unidireccional infinita hacia 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 imprimir/borrar. 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 que constituyen un programa.
En un artículo influyente, 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 (son los componentes "atómicos" de las instrucciones de Post) y, por defecto, se ejecutan secuencialmente (como un "programa de ordenador"). Su principal objetivo 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 máquinas de este tipo, incluida la máquina Wang W de cinco instrucciones con el conjunto de instrucciones
y su máquina Wang B de 4 instrucciones más reducida ("B" para "básico") con el conjunto de instrucciones
que ni siquiera tiene una instrucción ERASE-SQUARE.
Muchos autores introdujeron posteriormente variantes de las máquinas analizadas por Wang:
Minsky evolucionó la noción de Wang con su versión del modelo de "contramáquina" (de múltiples cintas) que permitía el movimiento SHIFT-LEFT y SHIFT-RIGHT de los cabezales separados pero no imprimía en absoluto. [3] En este caso, las cintas tendrían el extremo izquierdo y cada extremo estaría 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 múltiples cintas equivalente a la multiplicación y división en lugar del mucho más simple {MAYÚS-IZQUIERDA = DISMINUCIÓN, MAYÚS-DERECHA = INCREMENTAR}.
Davis, añadiendo una instrucción HALT explícita a una de las máquinas analizadas por Wang, utilizó un modelo con el conjunto de instrucciones
y también se consideraron versiones con alfabetos en cinta de tamaño mayor a 2.
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 estructurada "imperativo" menos " que se demostrará como Turing-completo" .
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 máquinas 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 varias 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 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, existe 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 seguir siendo 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 pasos. [4]
Las máquinas ajenas se corresponden de forma lineal por pasos con circuitos lógicos combinacionales, cuando la complejidad de la tabla de transición se toma como constante. Por tanto, es posible realizar cálculos como problemas de circuitos en tamaño y profundidad (consulte Complejidad del circuito ). Esto mejora el resultado original de Cook y Levin .
Peter van Emde Boas incluye todas las máquinas de este tipo en una clase, "la máquina registradora". [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 contadora" a veces se llama "máquina de Minsky".
El modelo primitivo de máquina de registro 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 de computadora" producía un tipo diferente de máquina simple con muchas cintas con el extremo izquierdo cortadas de una cinta de 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 sólo como cadenas/pila de marcas permitidas en un "registro" (es decir, cinta del 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 como registros de un solo extremo se consideran "contadores", y sus instrucciones se restringen a sólo dos (o tres si la instrucción TEST/DECREMENT está atomizada). Dos conjuntos de instrucciones comunes son los siguientes:
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.
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 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 automodificados no serían fáciles. Cuando Melzak añadió 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 funciona sólo 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]
El RASP es una RAM con las instrucciones almacenadas junto con sus datos en el mismo "espacio", es decir, una 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 von Neumann . Cuando el RASP tiene registros pares e impares alternos: 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 al estilo 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 y siempre contiene 0. Este truco no es inusual. La unidad 1 en el registro "unit" o "1" también es útil).
Los modelos RASP permiten direccionamiento directo e indirecto; algunos también permiten instrucciones "inmediatas", por ejemplo "Cargar acumulador con la 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 desde registro; STO es "acumulador de tienda"). Su sintaxis es la siguiente, excepto los saltos: "n, <n>, <<n>>" para "inmediato", "directo" e "indirecto"). Los saltos se realizan a través de dos "Instrucciones de transferencia" TRA: salto incondicional directamente "n" o indirectamente "< n >" interfiriendo el contenido del registro n en el contador de instrucciones, TRZ (salto condicional si el acumulador es cero de la misma manera que TRA):
Un recién llegado es la máquina de modificación de almacenamiento o máquina de punteros de Schönhage . Otra versión es la máquina de Kolmogorov-Uspensky y la propuesta de "autómata de enlace" de Knuth. (Para referencias ver máquina 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.
Cualquiera de las máquinas basadas en cintas 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 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 espacio n . Por tanto, para estudiar clases pequeñas de DSPACE , debemos utilizar un modelo diferente. En cierto sentido, si nunca "escribimos" en la cinta de entrada, no queremos cobrar por este espacio. Y si nunca "leemos" nuestra cinta de salida, no queremos cobrar 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 de k cuerdas ordinaria, excepto que la función de transición δ está restringida para que la cinta de entrada nunca pueda cambiarse y para que el cabezal de salida nunca pueda moverse 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 Proposición 2.2:
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]
