Máquina de Turing

Clases de autómatas

Una máquina de Turing es un modelo matemático de computación que describe una máquina abstracta ^{[ 1 ]} que manipula símbolos en una tira de cinta según una tabla de reglas. ^{[ 2 ]} A pesar de la simplicidad del modelo, es capaz de implementar cualquier algoritmo informático . ^{[ 3 ]}

La máquina opera en una cinta de memoria infinita ^{[ 4 ]} dividida en celdas discretas , ^{[ 5 ]} cada una de las cuales puede contener un solo símbolo extraído de un conjunto finito de símbolos llamado alfabeto de la máquina. Tiene un "cabezal" que, en cualquier punto de la operación de la máquina, se posiciona sobre una de estas celdas, y un "estado" seleccionado de un conjunto finito de estados. En cada paso de su operación, el cabezal lee el símbolo en su celda. Luego, basándose en el símbolo y en el estado actual de la máquina, esta escribe un símbolo en la misma celda y mueve el cabezal un paso a la izquierda o a la derecha, ^{[ 6 ]} o detiene el cálculo. La elección del símbolo de reemplazo a escribir, la dirección en la que se mueve el cabezal y si se debe detener se basa en una tabla finita que especifica qué hacer para cada combinación del estado actual y el símbolo leído. Al igual que con un programa de computadora real, es posible que una máquina de Turing entre en un bucle infinito que nunca se detendrá.

La máquina de Turing fue inventada en 1936 por Alan Turing , ^{[ 7 ] [ 11 ]} quien la llamó "máquina automática". ^{[ 12 ]} Fue el director de tesis doctoral de Turing, Alonzo Church , quien posteriormente acuñó el término "máquina de Turing" en una reseña. ^{[ 13 ]} Con este modelo, Turing pudo responder negativamente a dos preguntas:

• ¿Existe alguna máquina capaz de determinar si una máquina cualquiera en su cinta es "circular" (por ejemplo, se congela o no logra continuar su tarea computacional)?
• ¿Existe alguna máquina que pueda determinar si alguna máquina cualquiera en su cinta imprime alguna vez un símbolo dado? ^{[ 14 ] [ 15 ]}

Así, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo demostrar propiedades de la computación en general, y en particular, la incomputabilidad del Entscheidungsproblem , o «problema de decisión» (si toda afirmación matemática es demostrable o refutable). ^{[ 16 ]}

Las máquinas de Turing demostraron la existencia de limitaciones fundamentales en el poder de la computación mecánica. ^{[ 3 ]}

Si bien pueden expresar cálculos arbitrarios, su diseño minimalista los hace demasiado lentos para la computación en la práctica: las computadoras del mundo real se basan en diseños diferentes que, a diferencia de las máquinas de Turing, utilizan memoria de acceso aleatorio .

La completitud de Turing es la capacidad de un modelo de computación o un sistema de instrucciones para simular una máquina de Turing. Un lenguaje de programación que es Turing completo es teóricamente capaz de expresar todas las tareas que pueden realizar las computadoras; casi todos los lenguajes de programación son Turing completos si se ignoran las limitaciones de la memoria finita.

Una máquina de Turing es un modelo idealizado de una unidad central de procesamiento (CPU) que controla toda la manipulación de datos realizada por una computadora. La máquina clásica utiliza memoria secuencial para almacenar datos. Normalmente, la memoria secuencial se representa como una cinta de longitud infinita sobre la cual la máquina puede realizar operaciones de lectura y escritura.

En el contexto de la teoría del lenguaje formal , una máquina de Turing ( autómata ) es capaz de enumerar un subconjunto arbitrario de cadenas válidas de un alfabeto . Un conjunto de cadenas que se pueden enumerar de esta manera se denomina lenguaje recursivamente enumerable . La máquina de Turing puede definirse, de forma equivalente, como un modelo que reconoce cadenas de entrada válidas, en lugar de enumerar cadenas de salida.

Dada una máquina de Turing M y una cadena arbitraria s , generalmente no es posible decidir si M producirá finalmente s . Esto se debe a que el problema de la parada es irresoluble, lo cual tiene importantes implicaciones para los límites teóricos de la computación.

Una máquina de Turing capaz de simular cualquier otra máquina de Turing se denomina máquina de Turing universal (MTU, o simplemente máquina universal). Otro formalismo matemático, el cálculo lambda , con una naturaleza "universal" similar, fue introducido por Alonzo Church . El trabajo de Church se entrelazó con el de Turing para formar la base de la tesis Church-Turing . Esta tesis afirma que las máquinas de Turing, el cálculo lambda y otros formalismos de computación similares capturan la noción informal de métodos efectivos en lógica y matemáticas , proporcionando así un modelo mediante el cual se puede razonar sobre un algoritmo o "procedimiento mecánico" de forma matemáticamente precisa, sin estar atado a ningún formalismo en particular. El estudio de las propiedades abstractas de las máquinas de Turing ha aportado numerosas perspectivas a la informática , la teoría de la computabilidad y la teoría de la complejidad .

La máquina de Turing modela matemáticamente una máquina que opera mecánicamente sobre una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a uno, mediante un cabezal de lectura/escritura. El funcionamiento está completamente determinado por un conjunto finito de instrucciones elementales, como «en el estado 42, si el símbolo visto es 0, escribir un 1; si el símbolo visto es 1, pasar al estado 17; en el estado 17, si el símbolo visto es 0, escribir un 1 y pasar al estado 6»; etc. En el artículo original (« Sobre los números computables, con una aplicación al problema de decisión », véanse también las referencias a continuación ), Turing imagina no un mecanismo, sino una persona a la que llama «computadora», que ejecuta estas reglas mecánicas deterministas de forma servil (o, como dice Turing, «de manera desordenada»).

Más explícitamente, una máquina de Turing consta de:

• Una cinta dividida en celdas, una al lado de la otra. Cada celda contiene un símbolo de un alfabeto finito. El alfabeto contiene un símbolo especial en blanco (aquí escrito como '0') y uno o más símbolos adicionales. Se supone que la cinta es extensible arbitrariamente hacia la izquierda y hacia la derecha, de modo que la máquina de Turing siempre dispone de la cantidad de cinta necesaria para su cálculo. Se supone que las celdas que no se han escrito previamente están rellenas con el símbolo en blanco. En algunos modelos, la cinta tiene un extremo izquierdo marcado con un símbolo especial; la cinta se extiende o es indefinidamente extensible hacia la derecha.
• Un cabezal capaz de leer y escribir símbolos en la cinta y moverla de izquierda a derecha, celda por celda. En algunos modelos, el cabezal se mueve mientras la cinta permanece fija.
• Un registro de estado que almacena el estado de la máquina de Turing, uno de un número finito de estados. Entre estos se encuentra el estado inicial especial con el que se inicializa el registro de estado. Estos estados, escribe Turing, reemplazan el "estado mental" en el que normalmente se encontraría una persona que realiza cálculos.
• Una tabla finita ^{[ 19 ]} de instrucciones ^{[ 20 ]} que, dado el estado (q _i ) en el que se encuentra actualmente la máquina y el símbolo (a _j ) que está leyendo en la cinta (el símbolo que se encuentra actualmente bajo el cabezal), le indica a la máquina que haga lo siguiente en secuencia (para los modelos de 5- tuplas ):

1. Borra o escribe un símbolo (reemplazando una _j por una _j1 ).
2. Mover la cabeza (que se describe mediante d _k y puede tener los valores: 'L' para un paso a la izquierda , 'R' para un paso a la derecha o 'N' para permanecer en el mismo lugar).
3. Suponga el mismo estado o uno nuevo según lo prescrito (vaya al estado q _i1 ).

En los modelos de 4-tuplas, borrar o escribir un símbolo (a _j1 ) y mover el cabezal a la izquierda o a la derecha (d _k ) se especifican como instrucciones separadas. La tabla indica a la máquina que (ia) borre o escriba un símbolo o (ib) mueva el cabezal a la izquierda o a la derecha, y luego (ii) adopte el mismo estado o uno nuevo según lo prescrito, pero no ambas acciones (ia) e (ib) en la misma instrucción. En algunos modelos, si no hay ninguna entrada en la tabla para la combinación actual de símbolo y estado, la máquina se detendrá; otros modelos requieren que todas las entradas estén completas.

Cada parte de la máquina (es decir, su estado, colecciones de símbolos y cinta usada en un momento dado) y sus acciones (como imprimir, borrar y movimiento de la cinta) es finita , discreta y distinguible ; es la cantidad ilimitada de cinta y tiempo de ejecución lo que le da una cantidad ilimitada de espacio de almacenamiento .

Siguiendo a Hopcroft y Ullman (1979), ^{[ 21 ]} una máquina de Turing (de una cinta) puede definirse formalmente como una 7- tupla${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$dónde

• ${\displaystyle Q}$es un conjunto finito y no vacío de estados ;
• ${\displaystyle \Gamma }$es un conjunto finito y no vacío de símbolos del alfabeto de cinta ;
• ${\displaystyle b\in \Gamma }$es el símbolo en blanco (el único símbolo que puede aparecer en la cinta infinitamente a menudo en cualquier paso durante el cálculo);
• ${\displaystyle \Sigma \subseteq \Gamma \setminus \{b\}}$es el conjunto de símbolos de entrada , es decir, el conjunto de símbolos que se permite que aparezcan en el contenido inicial de la cinta;
• ${\displaystyle \delta$ :(Q\setminus F)\times \Gamma \rightharpoonup Q\times \Gamma \times \{L,R\}} es una función parcial llamada función de transición , donde L es el desplazamiento a la izquierda y R es el desplazamiento a la derecha. Si${\displaystyle \delta }$no está definido en el estado actual y el símbolo de cinta actual, entonces la máquina se detiene; ^{[ 22 ]} intuitivamente, la función de transición especifica el siguiente estado transitado desde el estado actual, qué símbolo sobrescribir el símbolo actual apuntado por el cabezal y el siguiente movimiento del cabezal.
• ${\displaystyle q_{0}\in Q}$es el estado inicial ;
• ${\displaystyle F\subseteq Q}$es el conjunto de estados finales o estados de aceptación . Se dice que el contenido inicial de la cinta es aceptado por${\displaystyle M}$si finalmente se detiene en un estado de${\displaystyle F}$.

Una variante permite "ningún desplazamiento", digamos N, como un tercer elemento del conjunto de direcciones.${\displaystyle \{L,R\}}$.

La 7-tupla para el castor ocupado de 3 estados se ve así (vea más sobre este castor ocupado en los ejemplos de máquinas de Turing ):

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$(estados);
• ${\displaystyle \Gamma =\{0,1\}}$(cinta de símbolos del alfabeto);
• ${\displaystyle b=0}$(símbolo en blanco);
• ${\displaystyle \Sigma =\{1\}}$(símbolos de entrada);
• ${\displaystyle \delta =}$Consulte la tabla de estados a continuación (función de transición).
• ${\displaystyle q_{0}={\mbox{A}}}$(estado inicial);
• ${\displaystyle F=\{{\mbox{HALT}}\}}$(estados finales);

Inicialmente, todas las celdas de cinta están marcadas con${\displaystyle 0}$.

En palabras de van Emde Boas (1990): "El objeto de teoría de conjuntos [su descripción formal de siete tuplas similar a la anterior] proporciona solo información parcial sobre cómo se comportará la máquina y cómo serán sus cálculos". ^{[ 23 ]}

Por ejemplo,

• Será necesario tomar muchas decisiones sobre el aspecto real de los símbolos, así como establecer un método infalible para leer y escribir símbolos de forma indefinida.
• Las operaciones de desplazamiento a la izquierda y a la derecha pueden mover el cabezal de la cinta a lo largo de la misma, pero a la hora de construir una máquina de Turing, resulta más práctico hacer que la cinta se deslice hacia adelante y hacia atrás bajo el cabezal.
• La cinta puede ser finita y extenderse automáticamente con espacios en blanco según sea necesario (lo cual se aproxima más a la definición matemática), pero es más común imaginarla extendiéndose infinitamente en uno o ambos extremos y prellenándose con espacios en blanco, excepto en el fragmento finito explícitamente dado donde se encuentra el cabezal de la cinta (esto, por supuesto, no es implementable en la práctica). La cinta no puede tener una longitud fija, ya que eso no se correspondería con la definición dada y limitaría seriamente el rango de cálculos que la máquina puede realizar a los de un autómata lineal acotado si la cinta fuera proporcional al tamaño de entrada, o a los de una máquina de estados finitos si tuviera una longitud estrictamente fija.

Diagramas de "estado"

A la derecha: la tabla anterior representada como un diagrama de "transición de estados".

Por lo general, es mejor dejar las tablas grandes como tablas (Booth, p.  74). Se simulan más fácilmente mediante ordenador en formato tabular (Booth, p.  74). Sin embargo, ciertos conceptos —por ejemplo, máquinas con estados de «reinicio» y máquinas con patrones repetitivos (cf. Hill y Peterson, p.  244 y ss.)— se aprecian mejor al visualizarlos como un dibujo.

El lector deberá decidir, en función del contexto particular, si un dibujo supone una mejora respecto a su tabla.

Cabe advertir nuevamente al lector que dichos diagramas representan una instantánea de su tabla congelada en el tiempo, no el curso ("trayectoria") de un cálculo a través del tiempo y el espacio. Si bien la máquina del castor ocupado "se ejecuta" siempre seguirá la misma trayectoria de estado, esto no ocurre con la máquina de "copia", a la que se le pueden proporcionar "parámetros" de entrada variables.

El diagrama "progreso del cálculo" muestra el progreso del "estado" (instrucción) del castor ocupado de tres estados a través de su cálculo de principio a fin. En el extremo derecho se encuentra la "configuración completa" de Turing (la "situación" de Kleene y la "descripción instantánea" de Hopcroft-Ullman) en cada paso. Si la máquina se detuviera y se borrara tanto el "registro de estado" como toda la cinta, estas "configuraciones" podrían usarse para reiniciar un cálculo en cualquier punto de su progreso. ^{[ 38 ]}

Se ha demostrado que muchas máquinas que podrían considerarse con mayor capacidad computacional que una simple máquina de Turing universal no poseen mayor potencia (Hopcroft y Ullman, pág.  159; cf. Minsky, 1967). Quizás computan más rápido, utilizan menos memoria o su conjunto de instrucciones es menor, pero no pueden computar con mayor potencia (es decir, realizar más funciones matemáticas). (La tesis de Church-Turing postula que esto es cierto para cualquier tipo de máquina: que todo lo que se puede "computar" puede ser computado por alguna máquina de Turing).

Una máquina de Turing es equivalente a un autómata de pila (PDA) de una sola pila, que se ha vuelto más flexible y conciso al flexibilizar el requisito de último en entrar, primero en salir (LIFO) de su pila. Además, una máquina de Turing también es equivalente a un PDA de dos pilas con semántica LIFO estándar, utilizando una pila para modelar la cinta a la izquierda del cabezal y la otra pila para la cinta a la derecha.

En el otro extremo, algunos modelos muy simples resultan ser equivalentes a una máquina de Turing , es decir, tienen la misma capacidad de cálculo que el modelo de máquina de Turing.

Los modelos equivalentes comunes son la máquina de Turing de cintas múltiples , la máquina de Turing de pistas múltiples , las máquinas con entrada y salida, y la máquina de Turing no determinista (NDTM) en contraposición a la máquina de Turing determinista (DTM) para la cual la tabla de acciones tiene como máximo una entrada para cada combinación de símbolo y estado.

Las máquinas de Turing de solo lectura que se mueven hacia la derecha son equivalentes a los autómatas finitos deterministas (así como a los autómatas finitos no deterministas mediante la conversión utilizando el algoritmo de conversión de autómatas finitos no deterministas ).

Con fines prácticos y didácticos, la máquina de registros equivalente puede utilizarse como un lenguaje de programación ensamblador convencional .

Una pregunta relevante es si el modelo de computación representado por lenguajes de programación concretos es equivalente a una máquina de Turing. Si bien la computación de una computadora real se basa en estados finitos y, por lo tanto, no puede simular una máquina de Turing, los lenguajes de programación en sí mismos no necesariamente tienen esta limitación. Kirner et al., 2009 demostraron que, entre los lenguajes de programación de propósito general, algunos son Turing completos, mientras que otros no. Por ejemplo, ANSI C no es Turing completo, ya que todas las instancias de ANSI C (son posibles diferentes instancias, ya que el estándar deja deliberadamente ciertos comportamientos sin definir por razones de compatibilidad con versiones anteriores) implican una memoria de espacio finito. Esto se debe a que el tamaño de los tipos de datos de referencia de memoria, llamados punteros , es accesible dentro del lenguaje. Sin embargo, otros lenguajes de programación como Pascal no tienen esta característica, lo que les permite ser Turing completos en principio. Es Turing completo en principio, ya que se permite que la asignación de memoria en un lenguaje de programación falle, lo que significa que el lenguaje de programación puede ser Turing completo al ignorar las asignaciones de memoria fallidas, pero los programas compilados ejecutables en una computadora real no pueden.

Al principio de su artículo (1936), Turing establece una distinción entre una "máquina automática" —cuyo "movimiento está completamente determinado por la configuración"— y una "máquina de elección":

...  cuyo movimiento está determinado solo parcialmente por la configuración... Cuando una máquina de este tipo alcanza una de estas configuraciones ambiguas, no puede continuar hasta que un operador externo haya tomado una decisión arbitraria. Este sería el caso si usáramos máquinas para trabajar con sistemas axiomáticos.

Turing (1936) no profundiza más, salvo en una nota a pie de página donde describe cómo usar una máquina automática para "encontrar todas las fórmulas demostrables del cálculo [de Hilbert]" en lugar de usar una máquina de elección. "Supone que las elecciones siempre están entre dos posibilidades, 0 y 1. Cada prueba estará entonces determinada por una secuencia de elecciones i ₁ , i ₂ , ..., i _n (i ₁ = 0 o 1, i ₂ = 0 o 1, ..., i _n = 0 o 1), y por lo tanto el número 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... +i _n determina completamente la prueba. La máquina automática lleva a cabo sucesivamente la prueba 1, la prueba 2, la prueba 3, ..." ^{[ 39 ]}

Esta es, de hecho, la técnica mediante la cual una máquina de Turing determinista (es decir, a-) puede usarse para imitar la acción de una máquina de Turing no determinista ; Turing resolvió el asunto en una nota a pie de página y parece descartarlo para futuras consideraciones.

Una máquina oráculo u o-máquina es una a-máquina de Turing que pausa su cálculo en el estado " o " mientras, para completarlo, "espera la decisión" del "oráculo", una entidad no especificada por Turing "aparte de decir que no puede ser una máquina" (Turing (1939)). ^{[ 40 ]}

Como escribió Turing en Lo indecidible , (cursiva añadida): ^{[ 41 ]}

Es posible inventar una única máquina que pueda utilizarse para calcular cualquier secuencia computable. Si a esta máquina U se le proporciona una cinta en cuyo inicio está escrita la cadena de quíntuples separados por punto y coma de alguna máquina de cálculo M , entonces U calculará la misma secuencia que M.

El modelo de computación que Turing llamó su "máquina universal" —" U " para abreviar— es considerado por algunos ^{[ 42 ]} como el avance teórico fundamental que condujo a la noción de la computadora de programa almacenado .

El artículo de Turing... contiene, en esencia, la invención del ordenador moderno y algunas de las técnicas de programación que lo acompañaron.

En términos de complejidad computacional , una máquina de Turing universal de múltiples cintas solo necesita ser más lenta por un factor logarítmico en comparación con las máquinas que simula. Este resultado fue obtenido en 1966 por FC Hennie y RE Stearns . ^{[ 44 ] [ 45 ]}

Las máquinas de Turing son más potentes que otros tipos de autómatas, como las máquinas de estados finitos y los autómatas de pila . Según la tesis de Church-Turing , son tan potentes como las máquinas reales y pueden ejecutar cualquier operación que un programa real pueda realizar. Lo que se pasa por alto en esta afirmación es que, dado que una máquina real solo puede tener un número finito de configuraciones , no es más que una máquina de estados finitos, mientras que una máquina de Turing dispone de una cantidad ilimitada de espacio de almacenamiento para sus cálculos.

Existen varias maneras de explicar por qué las máquinas de Turing son modelos útiles de ordenadores reales:

• Todo aquello que una computadora real puede calcular, una máquina de Turing también puede hacerlo. Por ejemplo: «Una máquina de Turing puede simular cualquier tipo de subrutina presente en los lenguajes de programación, incluyendo procedimientos recursivos y cualquiera de los mecanismos conocidos de paso de parámetros» (Hopcroft y Ullman, p.  157). Un autómata finito suficientemente grande también puede modelar cualquier computadora real, sin tener en cuenta la entrada/salida. Por lo tanto, cualquier afirmación sobre las limitaciones de las máquinas de Turing también se aplica a las computadoras reales.
• La diferencia radica únicamente en la capacidad de una máquina de Turing para manipular una cantidad ilimitada de datos. Sin embargo, dado un tiempo finito, una máquina de Turing (al igual que una máquina real) solo puede manipular una cantidad finita de datos.
• Al igual que una máquina de Turing, una máquina real puede ampliar su espacio de almacenamiento según sea necesario, adquiriendo más discos u otros medios de almacenamiento.
• Las descripciones de programas de máquinas reales mediante modelos abstractos más sencillos suelen ser mucho más complejas que las descripciones que utilizan máquinas de Turing. Por ejemplo, una máquina de Turing que describe un algoritmo puede tener unos pocos cientos de estados, mientras que el autómata finito determinista (AFD) equivalente en una máquina real dada tiene cuatrillones. Esto hace que la representación mediante AFD sea inviable para su análisis.
• Las máquinas de Turing describen algoritmos independientemente de la cantidad de memoria que utilicen. Si bien la memoria de cualquier máquina actual tiene un límite, este límite puede aumentar arbitrariamente con el tiempo. Las máquinas de Turing nos permiten formular afirmaciones sobre algoritmos que, en teoría, se mantendrán indefinidamente, independientemente de los avances en la arquitectura de las máquinas de computación convencionales .
• Los algoritmos que se ejecutan en máquinas abstractas equivalentes a Turing pueden disponer de tipos de datos de precisión arbitraria y nunca tienen que lidiar con condiciones inesperadas (incluidas, entre otras, la falta de memoria ).

El modelo aritmético de computación difiere del modelo de Turing en dos aspectos: ^{[ 46 ]}

• En el modelo aritmético, cada número real requiere una sola celda de memoria, mientras que en el modelo de Turing el tamaño de almacenamiento de un número real depende del número de bits necesarios para representarlo.
• En el modelo aritmético, cada operación aritmética básica con números reales (suma, resta, multiplicación y división) se puede realizar en un solo paso, mientras que en el modelo de Turing el tiempo de ejecución de cada operación aritmética depende de la longitud de los operandos.

Algunos algoritmos se ejecutan en tiempo polinomial en un modelo pero no en el otro. Por ejemplo:

• El algoritmo euclidiano se ejecuta en tiempo polinomial en el modelo de Turing, pero no en el modelo aritmético.
• El algoritmo que lee n números y luego calcula${\displaystyle 2^{2^{n}}}$mediante repetidas ejecuciones de elevación al cuadrado en tiempo polinomial en el modelo aritmético, pero no en el modelo de Turing. Esto se debe a que el número de bits necesarios para representar el resultado es exponencial con respecto al tamaño de la entrada.

Sin embargo, si un algoritmo se ejecuta en tiempo polinomial en el modelo aritmético y, además, la longitud binaria de todos los números involucrados es polinomial con respecto a la longitud de la entrada, entonces siempre se ejecutará en tiempo polinomial en el modelo de Turing. Se dice que dicho algoritmo se ejecuta en tiempo fuertemente polinomial .