Equivalentes de la máquina de Turing - Turing machine equivalents

Máquinas de Turing
Máquina
Equivalentes de la máquina de Turing Ejemplos de máquinas de Turing Galería de la máquina de Turing
Variantes
Máquina de Turing alternante Máquina de Turing neuronal Máquina de Turing no determinista Máquina cuántica de Turing Máquina post-Turing Máquina probabilística de Turing Máquina de Turing de solo lectura Máquinas de Turing en movimiento a la derecha de solo lectura Máquina de Turing de cintas múltiples Máquina de Turing multipista Máquina de Turing simétrica Máquina de Turing total Máquina de Turing inequívoca Máquina de Turing universal Máquina zeno
Ciencias
Alan Turing Categoría: máquina de Turing
v t mi

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. 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".

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 se trataba de una máquina universal) y la "entrada" y la "salida" se escribieron sólo 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 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 el 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, ya que son 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, MARCA-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 contador" (de varias cintas) que permitía el movimiento SHIFT-IZQUIERDA y SHIFT-RIGHT de los cabezales separados pero sin imprimir en absoluto. 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 {SHIFT-LEFT = DECREMENT, SHIFT-RIGHT = INCREMENT}.

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.

Lenguaje teórico de máquina de Böhm P "

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 demuestre 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 en pasos. ${\ Displaystyle O (n \ log n)}$

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". 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 modelo primitivo 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}.

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 expensas de proporcionar a su modelo una única marca obligatoria en el extremo izquierdo de cada cinta.

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: (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 auto-modificables 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).

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:

• 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.

El modelo RASP original de Elgot y Robinson tenía solo tres instrucciones a la manera del modelo de máquina de registro, 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. 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, <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):

{ADD n, ADD <n>, ADD << 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>, 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 λ ₀ , λ ₁ " 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 una máquina M de Turing de cuerdas k con entrada y salida, que opera dentro de un límite de tiempo .${\ Displaystyle f (n)}$${\ Displaystyle (k + 2)}$${\ Displaystyle O (f (n))}$

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 .

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}.
• 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 leer a lo largo de la cinta con una cabeza y escribir más a lo largo de la cinta con otra. .

• 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