Los equivalentes de la máquina de Turing son una serie de desarrollos teóricos ideados para modelizar el comportamiento de un dispositivo informático simple. El primero y más conocido de este tipo de modelos es la máquina de Turing, un dispositivo informático hipotético concebido por primera vez por el matemático británico Alan Turing en 1936. Las máquinas de Turing manipulan símbolos en una cinta potencialmente infinita según una tabla finita de reglas, y proporcionan los fundamentos teóricos para la noción de algoritmo informático.

Si bien no se ha demostrado que ninguno de los siguientes modelos tenga mayor potencia que el modelo de máquina de Turing de una sola cinta, unidireccional, infinita y multisímbolo, sus autores los definieron y utilizaron para investigar cuestiones y resolver problemas con mayor facilidad que si se hubieran ceñido al modelo de la máquina a de Turing.

Máquinas equivalentes al modelo de máquina de Turing

Equivalencia de Turing

Muchas máquinas que podrían considerarse con mayor capacidad computacional que una simple máquina de Turing universal, se puede comprobar que no tienen mayor potencia. Podrían calcular más rápido, usar menos memoria o tener un conjunto de instrucciones más pequeño, pero no pueden calcular con mayor potencia (es decir, realizar más funciones matemáticas). En este sentido, la tesis de Church-Turing sostiene la hipótesis de que cualquier cosa que pueda ser calculada, puede ser calculada por alguna máquina de Turing.

Modelos de máquinas secuenciales

Todos los siguientes ejemplos se denominan "modelos de máquinas secuenciales", para distinguirlos de los "modelos de máquinas en paralelo". Peter van Emde Boas, Machine Models and Simulations; Jan van Leeuwen, ed. Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, p. 3-66, The MIT Press/Elsevier, 1990. (volume A). QA76.H279 1990.

Máquinas de Turing basadas en cinta

Modelo de máquina a de Turing

La máquina a de Turing (como él la llamaba) tenía un extremo izquierdo y un extremo derecho infinito. Estaba provista de los 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), así como 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 tabular, denominadas "5-tuplas", y no se ejecutaban secuencialmente.

Máquinas de una sola cinta con símbolos y/o instrucciones restringidas Los siguientes modelos son máquinas de Turing de una sola cinta, pero restringidas con: (i) símbolos de cinta restringidos {marca, vacío}, y/o (ii) instrucciones secuenciales, similares a las de una computadora, y/o (iii) acciones de la máquina completamente atomizadas.

Modelo de computación "Formulación 1" de Post

Emil Leon 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", "vacío" = no_marca]. Cambió la noción de "cinta" de una cinta unidireccional infinita hacia la derecha a un conjunto infinito de habitaciones, cada una con una hoja de papel en ambas direcciones. Descompuso las 5-tuplas de Turing en 4-tuplas: instrucciones de movimiento separadas de las instrucciones de impresión/borrado. Si bien su modelo de 1936 es ambiguo al respecto, el modelo de Post de 1947 no requería la ejecución secuencial de las instrucciones.

Su modelo, extremadamente simple, puede emular cualquier máquina de Turing, y aunque su "Formulación 1" de 1936 no utiliza las palabras "programa" ni "máquina", es, en efecto, una formulación de una computadora programable muy primitiva y su lenguaje de programación asociado, donde las cajas actúan como una memoria de cadena de bits ilimitada y el conjunto de instrucciones constituye un programa.

Máquinas de Wang

En un influyente artículo, Hao Wang redujo la "formulation 1" de Post a máquinas que aún utilizan una cinta binaria bidireccional infinita, pero cuyas instrucciones son más simples (siendo los componentes "atómicos" de las instrucciones de Post) y se ejecutan secuencialmente por defecto (como un "programa de computadora"). Su principal objetivo 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 programas" de diversas máquinas de este tipo, incluyendo la máquina W de Wang de 5 instrucciones con el conjunto de instrucciones:

{ DESPLAZAR A LA IZQUIERDA, DESPLAZAR A LA DERECHA, MARCAR CUADRADO, BORRAR CUADRADO, SALTAR SI CUADRADO ESTÁ MARCADO A xxx }

y su versión más reducida de 4 instrucciones, la máquina de Wang B ("B" de "básica"), con el conjunto de instrucciones:

{ DESPLAZAR A LA IZQUIERDA, DESPLAZAR A LA DERECHA, MARCAR CUADRADO, SALTAR SI CUADRADO ESTÁ MARCADO A xxx }

que ni siquiera incluye la instrucción BORRAR CUADRADO.

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

Minsky desarrolló la idea de Wang con su versión del modelo de "máquina contadora" (de cintas múltiples) que permitía el movimiento de los cabezales por separado mediante las órdenes DESPLAZAR A LA IZQUIERDA y DESPLAZAR A LA DERECHA, pero sin impresión alguna. En este caso, las cintas terminarían a la izquierda, cada extremo marcado con una sola "marca" para indicar el final. Logró reducirlo a una sola cinta, pero a costa de introducir un movimiento de cuadrícula de cintas múltiples equivalente a la multiplicación y la división, en lugar del mucho más simple { DESPLAZAR A LA IZQUIERDA = DECREMENTO, DESPLAZAR A LA DERECHA = INCREMENTO }.

Davis, al añadir una instrucción explícita de DETENER a una de las máquinas analizadas por Wang, utilizó un modelo con el siguiente conjunto de instrucciones:

{ DESPLAZAR A LA IZQUIERDA, DESPLAZAR A LA DERECHA, BORRAR, MARCAR, SALTAR SI EL CUADRADO ESTÁ 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 de Böhm, P

En consonancia con el proyecto de Wang de buscar una teoría equivalente a la "economía en las operaciones básicas" de Turing, y con el deseo de evitar saltos incondicionales, un lenguaje teórico notable es el P′′ de 4 instrucciones, introducido por Corrado Böhm en 1964, el primer lenguaje imperativo "sin GOTO" programación estructurada que se demostró Turing completo.

El lenguaje de máquina de Müller, Brainfuck Brainfuck (BF) es una especie de lenguaje de programación esotérico creado en 1993 por el estudiante suizo Urban Müller. Es una variante del lenguaje de Böhm, el P′′. En el lenguaje P′′ de Böhm, la instrucción combina dos acciones: incrementar el contenido de la celda actual de la cinta y mover el cabezal de la cinta una posición. En BF, esta operación combinada se divide en dos instrucciones separadas:

una instrucción que incrementa el valor almacenado en la celda actual; y una instrucción que mueve el cabezal de la cinta una celda.

Ambos lenguajes son computacionalmente equivalentes; es decir, es posible transformar cualquier programa P′′ en un programa BF (y viceversa), siempre que la semántica esté debidamente sincronizada.

Máquinas de Turing de múltiples cintas

En el análisis práctico, se suelen utilizar diversos tipos de máquinas de Turing de múltiples cintas. Estas máquinas son similares a las de una sola cinta, pero con un número constante k de cintas independientes.

Ambas son computacionalmente equivalentes; es decir, es posible convertir cualquier máquina de varias cintas en una de solo una cinta (y viceversa), aunque generalmente tienen tiempos de ejecución diferentes.

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

Máquinas de Turing oblicuas

Una máquina de Turing oblicua es aquella 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 cada paso pueden ser diferentes para cada entrada de esa longitud. Pippenger y Fischer demostraron que cualquier cálculo que pueda realizar una máquina de Turing de múltiples cintas en n pasos puede ser realizado por una máquina de Turing oblicua de dos cintas en pasos.

Las máquinas oblicuas se corresponden de forma lineal por pasos con los circuitos lógicos combinacionales, cuando la complejidad de la tabla de transiciones se considera constante. Por lo tanto, es posible realizar cálculos como problemas de circuitos de tamaño y profundidad (véase complejidad deun circuito). Esto mejora el resultado original obtenido por Cook y Levin.

Modelos de máquinas de registro

Peter van Emde Boas incluye todas las máquinas de este tipo en una sola clase: "la máquina de registro". Sin embargo, históricamente, la literatura también ha denominado al miembro más primitivo de este grupo, es decir, "la máquina contadora", como "la máquina de registro". Y el desarrollo más primitivo de una "máquina contadora" se conoce a veces como "máquina Minsky".

Modelo de "máquina contadora", también llamada "máquina de registro"

El modelo primitivo de máquina de registro es, en efecto, una máquina Post-Turing de dos símbolos y múltiples cintas, cuyo comportamiento está 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" dio lugar a un tipo diferente de máquina simple con muchas cintas con extremos izquierdos, cortadas de una cinta Post-Turing. En todos los casos, los modelos solo permiten dos símbolos de cinta: marca y espacio en blanco.

Algunas versiones representan los enteros positivos como cadenas/pilas de marcas permitidas en un "registro" (es decir, una cinta con extremo izquierdo), y una cinta en blanco representada por el conteo "0". Minsky eliminó la instrucción PRINT a costa de dotar a su modelo de una marca única obligatoria en el extremo izquierdo de cada cinta.

En este modelo, las cintas de un solo extremo, consideradas como registros, se conciben como "contadores", y sus instrucciones se limitan a dos (o tres si la instrucción TEST/DECREMENT se atomiza). 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 ( ri, rj, z ) }, es decir: { Borrar el contenido del registro r; INCrementar el contenido de r; comparar el contenido de ri con rj y, si son iguales, saltar a la instrucción z }.

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

Modelo de máquina de acceso aleatorio (RAM)