Máquina de Turing

Un modelo de máquina de Turing físico. Una verdadera máquina de Turing tendría cinta ilimitada en ambos lados, sin embargo, los modelos físicos sólo pueden tener una cantidad finita de cinta.

Clases de automata

(Haga clic en cada capa obtiene un artículo sobre ese tema)

Una máquina de Turing es un modelo matemático de computación que describe una máquina abstracta que manipula símbolos en una tira de cinta de acuerdo con una tabla de reglas. A pesar de la simplicidad del modelo, es capaz de implementar cualquier algoritmo informático.

La máquina opera en una cinta de memoria infinita dividida en celdas discretas, cada una de las cuales puede contener un solo símbolo extraído de un conjunto finito de símbolos llamado el alfabeto de la máquina. Tiene una "cabeza" que, en cualquier punto de la operación de la máquina, se coloca sobre una de estas celdas, y un "estado" seleccionado de un conjunto finito de estados. En cada paso de su operación, la cabeza lee el símbolo en su celda. Luego, según el símbolo y el estado actual de la máquina, la máquina escribe un símbolo en la misma celda y mueve la cabeza un paso hacia la izquierda o hacia la derecha, o detiene el cálculo. La elección de qué símbolo de reemplazo escribir y en qué dirección moverse se basa en una tabla finita que especifica qué hacer para cada combinación del estado actual y el símbolo que se lee.

La máquina de Turing fue inventada en 1936 por Alan Turing, quien la llamó "una-máquina" (máquina automática). Fue el asesor de doctorado de Turing, Alonzo Church, quien más tarde acuñó el término 'máquina de Turing'. en una revisión. Con este modelo, Turing pudo responder negativamente a dos preguntas:

• ¿Existe una máquina que pueda determinar si cualquier máquina arbitraria en su cinta es "circular" (por ejemplo, congela o no continúa su tarea computacional)?
• ¿Existe una máquina que pueda determinar si alguna máquina arbitraria en su cinta alguna vez imprime un símbolo dado?

Por lo tanto, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo probar las propiedades de la computación en general y, en particular, la imposibilidad de calcular el Entscheidungsproblem ('problema de decisión').

Las máquinas de Turing demostraron la existencia de limitaciones fundamentales en el poder de la computación mecánica. Si bien pueden expresar cálculos arbitrarios, su diseño minimalista los hace inadecuados para el cálculo en la práctica: las computadoras del mundo real se basan en diferentes diseños que, a diferencia de las máquinas de Turing, usan memoria de acceso aleatorio.

La completitud de Turing es la capacidad de 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.

Resumen

Una máquina de Turing es un ejemplo general de una unidad central de procesamiento (CPU) que controla toda la manipulación de datos realizada por una computadora, y la máquina canónica usa memoria secuencial para almacenar datos. Más específicamente, es una máquina (autómata) capaz de enumerar algún subconjunto arbitrario de cadenas válidas de un alfabeto; estas cadenas son parte de un conjunto recursivamente enumerable. Una máquina de Turing tiene una cinta de longitud infinita en la que puede realizar operaciones de lectura y escritura.

Asumiendo una caja negra, la máquina de Turing no puede saber si eventualmente enumerará una cadena específica del subconjunto con un programa dado. Esto se debe al hecho de que el problema de la detención no tiene solución, lo que tiene importantes implicaciones para los límites teóricos de la computación.

La máquina de Turing es capaz de procesar una gramática sin restricciones, lo que implica además que es capaz de evaluar lógica de primer orden de manera sólida en un número infinito de formas. Esto se demuestra a través del cálculo lambda.

Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing se denomina máquina de Turing universal (UTM, o simplemente máquina universal). Una definición más orientada matemáticamente con un "universal" La naturaleza fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelazó con el de Turing en una teoría formal de computación conocida como la tesis de Church-Turing. La tesis afirma que las máquinas de Turing capturan la noción informal de métodos efectivos en lógica y matemáticas, y proporcionan un modelo a través del cual se puede razonar sobre un algoritmo o "procedimiento mecánico". El estudio de sus propiedades abstractas arroja muchas ideas sobre la informática y la teoría de la complejidad.

Descripción física

En su ensayo de 1948, "Maquinaria inteligente", Turing escribió que su máquina constaba de:

...una capacidad de memoria ilimitada obtenida en forma de una cinta infinita marcada en cuadrados, en cada uno de los cuales se podría imprimir un símbolo. En cualquier momento hay un símbolo en la máquina; se llama el símbolo escaneado. La máquina puede alterar el símbolo escaneado, y su comportamiento está determinado en parte por ese símbolo, pero los símbolos en la cinta en otro lugar no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover de ida y vuelta a través de la máquina, siendo ésta una de las operaciones elementales de la máquina. Cualquier símbolo en la cinta puede por lo tanto eventualmente tener una entrada.

—Turing 1948, pág. 3

Descripción

La máquina de Turing modela matemáticamente una máquina que opera mecánicamente en una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, utilizando un cabezal de cinta. La operación está completamente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo que se ve es 0, escriba un 1; si el símbolo visto es 1, cambia al estado 17; en el estado 17, si el símbolo que se ve es 0, escriba un 1 y cambie al estado 6;" etc. En el artículo original ("Sobre números computables, con una aplicación al Entscheidungsproblem", véanse también las referencias a continuación), Turing no imagina un mecanismo, sino una persona a la que llama la "computadora" 34;, que ejecuta estas reglas mecánicas deterministas servilmente (o, como dice Turing, "de manera inconexa").

La cabeza está siempre sobre un cuadrado particular de la cinta; sólo se muestra un tramo finito de cuadrados. La instrucción a realizar (q₄) se muestra en la plaza escaneada. (Drawing after Kleene (1952) p. 375.)

Aquí, el estado interno (q₁) se muestra dentro de la cabeza, y la ilustración describe la cinta como siendo infinita y pre-llenada con "0", el símbolo que sirve como blanco. El estado completo del sistema (su "configuración completa") consiste en el estado interno, cualquier símbolo no negro en la cinta (en esta ilustración "11B"), y la posición de la cabeza relativa a esos símbolos incluyendo en blancos, es decir, "011B". (Trabajando después de Minsky (1967) p. 121.)

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

• A cinta adhesiva dividido en células, una junto a la otra. Cada célula contiene un símbolo de algún alfabeto finito. El alfabeto contiene un símbolo en blanco especial (aquí está escrito como '0') y uno o más símbolos. Se supone que la cinta es extensible arbitrariamente a la izquierda y a la derecha, de modo que la máquina de Turing siempre se suministra con la cinta que necesita para su cálculo. Las células que no se han escrito antes se supone que se llenan 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 a la derecha.
• A cabeza que puede leer y escribir símbolos en la cinta y mover la cinta izquierda y derecha (y sólo una) célula a la vez. En algunos modelos la cabeza se mueve y la cinta es estacionaria.
• A registro estatal que almacena el estado de la máquina Turing, uno de finitos muchos. Entre ellos está la especial start state con el cual se inicializa el registro estatal. Estos estados, escribe Turing, reemplazan el "estado mental" que una persona que realiza computaciones normalmente estaría en.
• Un finito cuadro de instrucciones que, dada la estado(q_i) la máquina está actualmente en y el símboloa_j) está leyendo en la cinta (símbolo actualmente bajo la cabeza), dice la máquina para hacer lo siguiente en secuencia (para los modelos 5-tuple):

1. O borrar o escribir un símbolo (replazando un_j con una_j1).
2. Mueva la cabeza (que se describe por d_k y puede tener valores: 'L' para un paso a la izquierda o 'R' por un paso derecho o 'N' para quedarse en el mismo lugar.
3. Suponga el mismo o un nuevo estado según lo prescrito (ir al estado q_i1).

En los modelos de 4 tuplas, borrar o escribir un símbolo (a_j1) y mover la cabeza hacia la izquierda o hacia la derecha (d_k) se especifican como instrucciones separadas. La tabla le dice a la máquina que (ia) borre o escriba un símbolo o (ib) mueva la cabeza hacia la izquierda o hacia la derecha, y luego (ii) asuma lo mismo o uno nuevo indique lo prescrito, pero no ambas acciones (ia) e (ib) en la misma instrucción. En algunos modelos, si no hay una entrada en la tabla para la combinación actual de símbolo y estado, la máquina se detendrá; otros modelos requieren que se llenen todas las entradas.

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 mover la cinta) es finito, discretos y distinguibles; es la cantidad ilimitada de cinta y tiempo de ejecución lo que le da una cantidad ilimitada de espacio de almacenamiento.

Definición formal

Following Hopcroft & Ullman (1979, p. 148) harvtxt error: no target: CITEREFHopcroftUllman1979 (help), a (un-tape) Máquina de Turing se puede definir formalmente como un 7-tuple ${displaystyle M=langle Q,Gammab,Sigmadeltaq_{0},Frangle }$ Donde

• ${displaystyle "Gamma"$ es un conjunto finito, no vacío símbolos de alfabeto;
• ${displaystyle bin Gamma }$ es símbolo en blanco (el único símbolo permitido a ocurrir en la cinta infinitamente a menudo en cualquier paso durante la computación);
• ${displaystyle Sigma subseteq Gamma setminus {b}$ es el conjunto de símbolos de entrada, es decir, el conjunto de símbolos permitidos para aparecer en el contenido de la cinta inicial;
• ${displaystyle Q}$ es un conjunto finito, no vacío estados;
• ${displaystyle q_{0}in Q}$ es estado inicial;
• ${displaystyle Fsubseteq Q}$ es el conjunto de estados finales o aceptar estados. El contenido de la cinta inicial se dice que aceptada por ${displaystyle M}$ si eventualmente se detiene en un estado de ${displaystyle F}$.
• ${displaystyle delta:(Qsetminus F)times Gamma not to Qtimes Gamma times {L,R}$ es una función parcial llamada función de transición, donde L es el turno izquierdo, R es el turno derecho. Si ${displaystyle delta }$ no se define en el estado actual y el símbolo de la cinta actual, entonces la máquina se detiene; intuitivamente, la función de transición especifica el siguiente estado transitado del estado actual, que símbolo para sobreescribir el símbolo actual apuntado por la cabeza, y el próximo movimiento de la cabeza.

3-estado Busy Beaver. Los iconos negros representan la ubicación y el estado de la cabeza; los colores cuadrados representan 1s (orange) y 0s (blanco); el tiempo progresa verticalmente desde la parte superior hasta la HALT estado en el fondo.

Además, la máquina de Turing también puede tener un estado de rechazo para que el rechazo sea más explícito. En ese caso hay tres posibilidades: aceptar, rechazar y correr para siempre. Otra posibilidad es considerar los valores finales de la cinta como salida. Sin embargo, si la única salida es el estado final en el que termina la máquina (o si nunca se detiene), la máquina aún puede generar efectivamente una cadena más larga tomando un número entero que le indica qué bit de la cadena generar.

Una variante relativamente poco común permite "no cambiar", dice N, como un tercer elemento del conjunto de direcciones ${displaystyle {L,R}}$.

La tupla de 7 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 ¿Qué?$ (estados);
• ${displaystyle "Gamma"$ (símbolos del alfabeto de cinta);
• ${displaystyle b=0}$ (símbolo negro);
• ${displaystyle Sigma = {1}}$ (símbolos de entrada);
• ${displaystyle q_{0}={mbox{A}}$ (Estado inicial);
• ${displaystyle F={mbox{HALT}}}$ (Estados finales);
• ${displaystyle delta =}$ ver el estado-tabla abajo (función de transición).

Inicialmente todas las celdas están marcadas con ${displaystyle 0}$.

Detalles adicionales necesarios para visualizar o implementar máquinas de Turing

En palabras de van Emde Boas (1990), p. 6: "El objeto teórico 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 se verán sus cálculos."

Por ejemplo,

• Habrá muchas decisiones sobre cómo son los símbolos, y una forma infalible de leer y escribir símbolos indefinidamente.
• El turno a la izquierda y las operaciones a la derecha pueden cambiar la cabeza de cinta a través de la cinta, pero cuando realmente la construcción de una máquina de Turing es más práctico hacer la cinta deslizarse hacia atrás y hacia adelante bajo la cabeza en lugar.
• La cinta puede ser finita, y se extiende automáticamente con blancos según sea necesario (que está más cerca de la definición matemática), pero es más común pensar en ella como estirarse infinitamente en uno o ambos extremos y ser pre-llenado con blancos excepto en el fragmento finito explícitamente dado que la cabeza de cinta está en. (Esto, por supuesto, no es implementable en la práctica.) La cinta no ser fijo en longitud, ya que eso no correspondería a la definición dada y limitaría seriamente la gama de computaciones que la máquina puede realizar a los de un autómata ligado lineal si la cinta era proporcional al tamaño de entrada, o máquina de estado finito si era estrictamente de longitud fija.

Definiciones alternativas

Las definiciones en la literatura a veces difieren ligeramente, para hacer argumentos o pruebas más fáciles o claras, pero esto siempre se hace de tal manera que la máquina resultante tiene el mismo poder computacional. Por ejemplo, el conjunto podría cambiarse de ${displaystyle {L,R}}$ a ${displaystyle {L,R,N}$, donde N ("None" o "No-operación") permitiría a la máquina permanecer en la misma celda en lugar de moverse izquierda o derecha. Esto no aumentaría el poder computacional de la máquina.

La convención más común representa cada "instrucción de Turing" en una "mesa de Turing" por una de las nueve tuplas de 5, según la convención de Turing/Davis (Turing (1936) en The Undecidable, p. 126–127 y Davis (2000) p. 152):

(definición 1): (q_i, S_j, S_k/E/N, L/R/N, q_m)

() estado actual q_i , símbolo escaneado S_j , símbolo de impresión S_k/erase E/None N , move_tape_one_square left L/right R/None N , nuevo estado q_m )

Otros autores (Minsky (1967) p. 119, Hopcroft y Ullman (1979) p. 158, Stone (1972) p. 9) adoptan una convención diferente, con el nuevo estado q_m aparece inmediatamente después del símbolo escaneado S_j:

(definición 2): (q_i, S_j, q_m, S_k/E/N, L/R/N)

() estado actual q_i , símbolo escaneado S_j , nuevo estado q_m , símbolo de impresión S_k/erase E/None N , move_tape_one_square left L/right R/None N )

Para el resto de este artículo, "definición 1" (la convención de Turing/Davis) será utilizada.

En la siguiente tabla, el modelo original de Turing permitía solo las primeras tres líneas que llamó N1, N2, N3 (cf. Turing en The Undecidable, p. 126). Permitió borrar el "cuadrado escaneado" nombrando un símbolo 0 S₀ = "borrar" o "en blanco", etc. Sin embargo, no permitió la no impresión, por lo que cada línea de instrucción incluye "símbolo de impresión S_k" o "borrar" (cf. nota al pie 12 en Post (1947), The Undecidable, p. 300). Las abreviaturas son de Turing (The Undecidable, p. 119). Después del artículo original de Turing en 1936-1937, los modelos de máquinas han permitido los nueve tipos posibles de cinco tuplas:

Cualquier tabla de Turing (lista de instrucciones) se puede construir a partir de las nueve tuplas anteriores. Por razones técnicas, los tres no imprimibles o "N" normalmente se puede prescindir de las instrucciones (4, 5, 6). Para ver ejemplos, consulte Ejemplos de máquinas de Turing.

Con menos frecuencia se encuentra el uso de tuplas de 4: estas representan una mayor atomización de las instrucciones de Turing (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); también vea más en la máquina de Post-Turing.

El "estado"

La palabra "estado" utilizado en el contexto de las máquinas de Turing puede ser una fuente de confusión, ya que puede significar dos cosas. La mayoría de los comentaristas posteriores a Turing han utilizado "estado" para significar el nombre/designador de la instrucción actual que se ejecutará, es decir, el contenido del registro estatal. Pero Turing (1936) hizo una fuerte distinción entre un registro de lo que llamó la 'configuración-m' de la máquina, y la 'configuración-m' de la máquina (o de la persona). 34;estado de progreso" a través de la computación—el estado actual del sistema total. Lo que Turing llamó "la fórmula del estado" incluye tanto la instrucción actual como todos los símbolos de la cinta:

Así, el estado de progreso de la computación en cualquier etapa está completamente determinado por la nota de instrucciones y los símbolos en la cinta. Es decir, el estado del sistema puede ser descrito por una sola expresión (secuencia de símbolos) que consiste en los símbolos en la cinta seguida por Δ (que se supone que no debe aparecer en otro lugar) y luego por la nota de instrucciones. Esta expresión se llama "fórmula estatal".

—Los indecidables, pp. 139–140, emphasis added

Anteriormente en su artículo, Turing llevó esto aún más lejos: da un ejemplo en el que colocó un símbolo de la 'configuración m' actual (la etiqueta de la instrucción) debajo del cuadrado escaneado, junto con todos los símbolos de la cinta (The Undecidable, p. 121); esto lo llama "la configuración completa" (Lo indecidible, p. 118). Para imprimir la "configuración completa" en una línea, coloca la etiqueta de estado/configuración m a la izquierda del símbolo escaneado.

Una variante de esto se ve en Kleene (1952) donde Kleene muestra cómo escribir el número de Gödel de la 'situación' de una máquina: coloca la 'configuración-m' 34; símbolo q₄ sobre el cuadrado escaneado aproximadamente en el centro de los 6 cuadrados que no están en blanco en la cinta (vea la figura de la cinta de Turing en este artículo) y lo coloca a la derecha del cuadrado escaneado. Pero Kleene se refiere a "q₄" a sí mismo como "el estado de la máquina" (Kleene, págs. 374-375). Hopcroft y Ullman llaman a este compuesto la "descripción instantánea" y siga la convención de Turing de poner el "estado actual" (etiqueta de instrucción, configuración m) a la izquierda del símbolo escaneado (p. 149), es decir, la descripción instantánea es la combinación de símbolos que no están en blanco a la izquierda, estado del máquina, el símbolo actual escaneado por la cabeza y los símbolos que no están en blanco a la derecha.

Ejemplo: estado total de un castor ocupado de 3 estados y 2 símbolos después de 3 "movimientos" (tomado del ejemplo "correr" en la figura a continuación):

1A1

Esto significa: después de tres movimientos, la cinta tiene... 000110000... en ella, la cabeza está escaneando el 1 más a la derecha, y el estado es A. Los espacios en blanco (en este caso representados por "0"s) pueden ser parte del estado total como se muestra aquí: B01; la cinta tiene un solo 1, pero la cabeza está escaneando el 0 ("en blanco") a su izquierda y el estado es B.

"Estado" en el contexto de las máquinas de Turing debe aclararse qué se está describiendo: la instrucción actual, o la lista de símbolos en la cinta junto con la instrucción actual, o la lista de símbolos en la cinta junto con la instrucción actual colocada en el a la izquierda del símbolo escaneado oa la derecha del símbolo escaneado.

El biógrafo de Turing, Andrew Hodges (1983: 107), ha señalado y discutido esta confusión.

"Estado" diagramas

La máquina de Turing "3-estado ocupado" en una representación del estado finito. Cada círculo representa un "estado" de la tabla, una "configuración m" o "instrucción". "Dirección" de un estado transición se muestra por una flecha. La etiqueta (por ejemplo. 0/P,R) cerca del estado saliente (en la cola de la flecha) especifica el símbolo escaneado que causa una transición particular (por ejemplo. 0) seguido de un golpe /, seguido por los "comportadores" subsiguientes de la máquina, por ejemplo "P impresión"entonces mueve cinta"R derecho". No existe un formato general aceptado. La convención se muestra después de McClusky (1965), Booth (1967), Hill y Peterson (1974).

A la derecha: la tabla anterior expresada como una "transición de estado" diagrama.

Por lo general, es mejor dejar las mesas grandes como mesas (Booth, p. 74). Se simulan más fácilmente por computadora en forma tabular (Booth, p. 74). Sin embargo, ciertos conceptos, p. máquinas con "reset" estados y máquinas con patrones repetitivos (cf. Hill y Peterson p. 244ff)—se pueden ver más fácilmente cuando se ven como un dibujo.

El lector debe decidir si un dibujo representa una mejora en su tabla para el contexto particular.

La evolución de la computación del castor ocupado comienza en la parte superior y procede al fondo.

Se debe 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 hasta< /i> tiempo y espacio. Mientras que cada vez que la máquina castor ocupada "funciona" siempre seguirá la misma trayectoria de estado, esto no es cierto para la "copia" máquina que se puede proporcionar con "parámetros" de entrada variable.

El diagrama "progreso del cálculo" muestra el "estado" del castor ocupado de tres estados (instrucción) progresa a través de su cálculo de principio a fin. En el extremo derecho está la "configuración completa" de Turing. (Kleene "situación", Hopcroft–Ullman "descripción instantánea") en cada paso. Si la máquina se detuviera y se borrara para dejar en blanco tanto el "registro de estado" y toda la cinta, estas "configuraciones" podría usarse para reavivar un cómputo en cualquier parte de su progreso (cf. Turing (1936) The Undecidable, pp. 139–140).

Modelos equivalentes

Muchas máquinas de las que se podría pensar que tienen más capacidad de cómputo que una simple máquina universal de Turing pueden demostrar que no tienen más poder (Hopcroft y Ullman p. 159, cf. Minsky (1967)). Quizás calculen más rápido, o utilicen menos memoria, o su conjunto de instrucciones sea más pequeño, pero no pueden computar con mayor potencia (es decir, más funciones matemáticas). (La tesis de Church-Turing plantea que esto es cierto para cualquier tipo de máquina: que cualquier cosa que pueda ser "computada" puede ser calculada por alguna máquina de Turing).

Una máquina de Turing es equivalente a un autómata pushdown de una sola pila (PDA) que se ha vuelto más flexible y conciso al relajar 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 una PDA de dos pilas con semántica LIFO estándar, ya que usa 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 Turing, es decir, tienen la misma potencia computacional que el modelo de la máquina de Turing.

Los modelos equivalentes comunes son la máquina de Turing de múltiples cintas, la máquina de Turing de múltiples pistas, las máquinas con entrada y salida y la máquina de Turing no determinista (NDTM) en oposición a la máquina de Turing determinista (DTM) para los que 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 movimiento hacia la derecha de solo lectura son equivalentes a los DFA (así como a los NFA mediante la conversión mediante el algoritmo de conversión de NDFA a DFA).

Para propósitos prácticos y didácticos, la máquina de registro equivalente puede usarse como un lenguaje de programación ensamblador habitual.

Una pregunta relevante es si el modelo de computación representado por lenguajes de programación concretos es o no equivalente a Turing. Si bien el cálculo de una computadora real se basa en estados finitos y, por lo tanto, no es capaz de simular una máquina de Turing, los lenguajes de programación en sí mismos no necesariamente tienen esta limitación. Kirner et al., 2009 han demostrado 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 equivalente a Turing, ya que todas las instancias de ANSI C (son posibles diferentes instancias ya que el estándar deja deliberadamente cierto comportamiento sin definir por razones heredadas) implica 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 idioma. Sin embargo, otros lenguajes de programación como Pascal no tienen esta característica, lo que les permite ser Turing completos en principio. En principio, es solo Turing completo, ya que se permite que falle la asignación de memoria en un lenguaje de programación, 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.

Elección c-máquinas, oráculo o-máquinas

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

...cuyo movimiento sólo está determinado parcialmente por la configuración... Cuando tal máquina alcanza una de estas configuraciones ambiguas, no puede continuar hasta que una opción arbitraria haya sido hecha por un operador externo. Este sería el caso si utilizamos máquinas para tratar sistemas axiomáticos.

—Los indecidables, pág. 118

Turing (1936) no da más detalles, excepto en una nota a pie de página en la que describe cómo usar una máquina para "encontrar todas las fórmulas comprobables del cálculo [de Hilbert]" en lugar de utilizar una máquina de elección. Él "supone[s] que las opciones están siempre entre dos posibilidades 0 y 1. Cada prueba estará entonces determinada por una secuencia de opciones i₁, i₂,..., i_n (i₁ = 0 o 1, i₂ = 0 o 1,..., i< sub>n = 0 o 1), y por lo tanto el número 2ⁿ + i₁2^n-1 + i< sub>22^n-2 +... +i_n determina completamente la prueba. La máquina automática realiza sucesivamente prueba 1, prueba 2, prueba 3,..." (Nota al pie ‡, El indecidible, p. 138)

Esta es, de hecho, la técnica mediante la cual se puede utilizar una máquina de Turing determinista (es decir, a-) 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 o máquina-o es una máquina-a de Turing que detiene su cálculo en el estado "o" mientras que, para completar su cálculo, "espera la decisión" de "el oráculo"—una entidad no especificada "aparte de decir que no puede ser una máquina" (Turing (1939), Lo indecidible, p. 166–168).

Máquinas universales de Turing

Aplicación de una máquina de Turing

Como escribió Turing en Lo indecidible, p. 128 (cursivas añadidas):

Es posible inventar un máquina individual que se puede utilizar para calcular cualquiera secuencia computable. Si esta máquina U se suministra con la cinta en el principio de la cual se escribe la cadena de quintuples separados por semicolones de alguna máquina de computación M, entonces U computará la misma secuencia M.

Este hallazgo ahora se da por sentado, pero en ese momento (1936) se consideró asombroso. El modelo de computación que Turing llamó su "máquina universal"—"U" para abreviar, es considerado por algunos (cf. Davis (2000)) como el avance teórico fundamental que condujo a la noción de computadora con programa almacenado.

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

—Minsky (1967), pág. 104

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 F. C. Hennie y R. E. Stearns. (Arora y Barak, 2009, teorema 1.9)

Comparación con máquinas reales

Una realización de la máquina de Turing utilizando piezas de Lego

A menudo se cree que las máquinas de Turing, a diferencia de los autómatas más simples, son tan poderosas como las máquinas reales y pueden ejecutar cualquier operación que pueda ejecutar un programa real. Lo que se pasa por alto en esta declaración es que, debido a que una máquina real solo puede tener un número finito de configuraciones, no es más que una máquina de estado finito, mientras que una máquina de Turing tiene una cantidad ilimitada de espacio de almacenamiento. disponible para sus cálculos.

Hay varias formas de explicar por qué las máquinas de Turing son modelos útiles de computadoras reales:

• Cualquier cosa que un ordenador real puede calcular, una máquina Turing también puede calcular. Por ejemplo: "Una máquina de Turing puede simular cualquier tipo de subrutina que se encuentre en lenguajes de programación, incluyendo procedimientos recursivos y cualquiera de los mecanismos conocidos de paso del parámetro" (Hopcroft y Ullman p. 157). Un FSA lo suficientemente grande también puede modelar cualquier ordenador real, ignorando IO. Así, una declaración sobre las limitaciones de las máquinas Turing también se aplicará a las computadoras reales.
• La diferencia radica sólo en la capacidad de una máquina Turing para manipular una cantidad sin límites de datos. Sin embargo, dada una cantidad finita de tiempo, una máquina Turing (como una máquina real) sólo puede manipular una cantidad finita de datos.
• Como una máquina Turing, una máquina real puede tener su espacio de almacenamiento ampliado según sea necesario, adquiriendo más discos u otros medios de almacenamiento.
• Las descripciones de los programas de máquinas reales utilizando modelos abstractos más simples a menudo son mucho más complejas que las descripciones usando 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 automaton finito determinista equivalente (DFA) en una máquina real determinada tiene cuadrillones. Esto hace que la representación del DFA no sea posible analizar.
• Las máquinas de Turing describen algoritmos independientes de la cantidad de memoria que utilizan. Hay un límite a la memoria poseída por cualquier máquina actual, pero este límite puede elevarse arbitrariamente en el tiempo. Las máquinas de Turing nos permiten hacer declaraciones sobre algoritmos que (teóricamente) mantendrán para siempre, independientemente de los avances en convencionales arquitectura de máquina de computación.
• Las máquinas de Turing simplifican la declaración de algoritmos. Los algoritmos que se ejecutan en las máquinas abstractas de Turing-equivalente son generalmente más generales que sus contrapartes que se ejecutan en máquinas reales, porque tienen tipos de datos arbitrarios-precisión disponibles y nunca tienen que lidiar con condiciones inesperadas (incluyendo, pero no limitadas, que se agotan de la memoria).

Otra realización de la máquina Turing

Limitaciones

Teoría de la complejidad computacional

Una limitación de las máquinas de Turing es que no modelan bien las fortalezas de un arreglo en particular. Por ejemplo, las computadoras modernas de programa almacenado son en realidad instancias de una forma más específica de máquina abstracta conocida como máquina de programa almacenado de acceso aleatorio o modelo de máquina RASP. Al igual que la máquina de Turing universal, el RASP almacena su "programa" en "memoria" externo a las 'instrucciones' de su máquina de estado finito. A diferencia de la máquina de Turing universal, el RASP tiene un número infinito de 'registros', 'celdas' de memoria distinguibles, numerados pero ilimitados. que puede contener cualquier número entero (cf. Elgot y Robinson (1964), Hartmanis (1971), y en particular Cook-Rechow (1973); referencias a máquinas de acceso aleatorio). La máquina de estados finitos del RASP está equipada con la capacidad de direccionamiento indirecto (por ejemplo, el contenido de un registro se puede usar como una dirección para especificar otro registro); por lo tanto, el "programa" del RASP's puede direccionar cualquier registro en la secuencia de registros. El resultado de esta distinción es que existen optimizaciones computacionales que se pueden realizar en función de los índices de memoria, que no son posibles en una máquina de Turing general; por lo tanto, cuando las máquinas de Turing se utilizan como base para delimitar los tiempos de ejecución, un "límite inferior falso" se puede probar en ciertos algoritmos' tiempos de ejecución (debido a la falsa suposición simplificadora de una máquina de Turing). Un ejemplo de esto es la búsqueda binaria, un algoritmo que se puede demostrar que funciona más rápidamente cuando se utiliza el modelo de cálculo RASP en lugar del modelo de la máquina de Turing.

Concurrencia

Otra limitación de las máquinas de Turing es que no modelan bien la concurrencia. Por ejemplo, hay un límite en el tamaño de un entero que puede calcularse mediante una máquina de Turing no determinista que siempre se detiene y comienza en una cinta en blanco. (Consulte el artículo sobre no determinismo ilimitado). Por el contrario, existen sistemas concurrentes que siempre se detienen sin entradas que pueden calcular un número entero de tamaño ilimitado. (Se puede crear un proceso con almacenamiento local que se inicializa con un conteo de 0 que se envía simultáneamente un mensaje de parada y uno de marcha. Cuando recibe un mensaje de marcha, incrementa su conteo en 1 y se envía a sí mismo un mensaje de marcha. Cuando recibe un mensaje de detención, se detiene con un número ilimitado en su almacenamiento local).

Interacción

En los primeros días de la informática, el uso de la computadora se limitaba típicamente al procesamiento por lotes, es decir, tareas no interactivas, cada una de las cuales producía datos de salida a partir de datos de entrada dados. La teoría de la computabilidad, que estudia la computabilidad de las funciones desde las entradas hasta las salidas, y para la cual se inventaron las máquinas de Turing, refleja esta práctica.

Desde la década de 1970, el uso interactivo de las computadoras se volvió mucho más común. En principio, es posible modelar esto haciendo que un agente externo lea la cinta y escriba en ella al mismo tiempo que una máquina de Turing, pero esto rara vez coincide con la forma en que realmente ocurre la interacción; por lo tanto, cuando se describe la interactividad, se suelen preferir alternativas como los autómatas de E/S.

Historia

Antecedentes históricos: maquinaria computacional

Robin Gandy (1919–1995), alumno de Alan Turing (1912–1954) y amigo de toda su vida, rastrea el linaje de la noción de "máquina calculadora" de vuelta a Charles Babbage (alrededor de 1834) y en realidad propone 'La tesis de Babbage':

Que todo el desarrollo y las operaciones de análisis son ahora capaces de ser ejecutados por maquinaria.

—(italics in Babbage as cited by Gandy, p. 54)

El análisis de Gandy del motor analítico de Babbage describe las siguientes cinco operaciones (cf. p. 52–53):

• Las funciones aritméticas +, −, ×, donde − indica la resta "proper" x − Sí. = 0 si Sí. ≥ x.
• Cualquier secuencia de operaciones es una operación.
• Iteración de una operación (repetir n veces una operación P).
• Iteración condicional (repetir en ocasiones una operación P condicional en el "éxito" de la prueba T).
• Transferencia condicional (es decir, "goto").

Gandy afirma que "las funciones que se pueden calcular mediante (1), (2) y (4) son precisamente aquellas que son computables por Turing." (pág. 53). Cita otras propuestas de "máquinas calculadoras universales" incluyendo las de Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937). Sin embargo:

... el énfasis es en la programación de una secuencia iterable fija de operaciones aritméticas. La importancia fundamental de la iteración condicional y la transferencia condicional para una teoría general de cálculo de máquinas no es reconocida...

—Gandy p. 55

El Entscheidungsproblem (el "problema de decisión"): la décima pregunta de Hilbert de 1900

Con respecto a los problemas de Hilbert planteados por el famoso matemático David Hilbert en 1900, un aspecto del problema n.º 10 había estado dando vueltas durante casi 30 años antes de que se enmarcara con precisión. La expresión original de Hilbert para el número 10 es la siguiente:

10. Determinación de la soledad de una ecuación Diofantina. Dada una ecuación de Diofantina con cualquier número de cantidades desconocidas y con coeficientes integrales racionales: Desarrollar un proceso según el cual se puede determinar en un número finito de operaciones si la ecuación es solvable en enteros racionales. El Entscheidungsproblem [problema de decisión para la lógica de primer orden] se resuelve cuando sabemos un procedimiento que permite que cualquier expresión lógica dada decida por finitamente muchas operaciones su validez o satisfiabilidad... El Entscheidungsproblema debe ser considerado el principal problema de la lógica matemática.

—citado, con esta traducción y el alemán original, en Dershowitz y Gurevich, 2008

Para 1922, esta noción de "Entscheidungsproblem" se había desarrollado un poco, y H. Behmann afirmó que

... la forma más general del Entscheidungsproblem [es] como sigue:

Se requiere una receta bastante definida generalmente aplicable que permitirá a uno decidir en un número finito de pasos la verdad o falsedad de una determinada afirmación puramente lógica...

—Gandy p. 57, citando a Behmann

Behmann comenta que... el problema general es equivalente al problema de decidir qué propuestas matemáticas son verdaderas.

—ibíd.

Si uno pudiera resolver el Entscheidungsproblema entonces uno tendría un "procedimiento para resolver muchos (o incluso todos) problemas matemáticos".

—ibíd., pág. 92

Para el congreso internacional de matemáticos de 1928, Hilbert "hizo sus preguntas bastante precisas. Primero, ¿fueron las matemáticas completas... Segundo, fueron las matemáticas consistentes... Y tercero, ¿fueron las matemáticas decidibles?" (Hodges p. 91, Hawking p. 1121). Las dos primeras preguntas fueron respondidas en 1930 por Kurt Gödel en la misma reunión donde Hilbert pronunció su discurso de jubilación (para disgusto de Hilbert); el tercero, el Entscheidungsproblem, tuvo que esperar hasta mediados de la década de 1930.

El problema era que una respuesta requería primero una definición precisa de "prescripción aplicable general definida", que el profesor de Princeton Alonzo Church vendría a llamar "calculabilidad efectiva", y en 1928 no existía tal definición. Pero durante los siguientes 6 a 7 años, Emil Post desarrolló su definición de un trabajador que se mueve de una habitación a otra escribiendo y borrando marcas según una lista de instrucciones (Post 1936), al igual que Church y sus dos estudiantes Stephen Kleene y J. B. Rosser mediante el uso de Cálculo lambda de Church y teoría recursiva de Gödel (1934). El artículo de Church (publicado el 15 de abril de 1936) mostró que el Entscheidungsproblem era de hecho "indecidible" y venció a Turing por casi un año (artículo de Turing presentado el 28 de mayo de 1936, publicado en enero de 1937). Mientras tanto, Emil Post presentó un breve artículo en el otoño de 1936, por lo que Turing al menos tenía prioridad sobre Post. Mientras Church arbitraba el artículo de Turing, Turing tuvo tiempo de estudiar el artículo de Church y agregar un Apéndice donde esbozaba una prueba de que el cálculo lambda de Church y sus máquinas calcularían las mismas funciones.

Pero lo que la Iglesia había hecho era algo bastante diferente, y en cierto sentido más débil.... la construcción de Turing era más directa, y proporcionó un argumento de los primeros principios, cerrando la brecha en la demostración de la Iglesia.

—Hodges p. 112

Y Post solo había propuesto una definición de calculabilidad y criticado la 'definición' de Church, pero no había probado nada.

La máquina A de Alan Turing

En la primavera de 1935, Turing, como joven estudiante de maestría en King's College, Cambridge, asumió el desafío; había sido estimulado por las conferencias del lógico M. H. A. Newman "y aprendido de ellos del trabajo de Gödel y el Entscheidungsproblem... Newman usó la palabra 'mecánico'... En su obituario de Turing 1955 Newman escribe:

A la pregunta "¿Qué es un proceso "mecánico"? Turing devolvió la respuesta característica 'Algo que puede ser hecho por una máquina' y se embarcó en la tarea altamente congénita de analizar la noción general de una máquina de computación.

—Gandy, pág. 74

Gandy afirma que:

Supongo, pero no sé, que Turing, desde el comienzo de su trabajo, tenía como objetivo una prueba de la indecisobilidad del Entscheidungsproblema. Me dijo que la "principal idea" del periódico vino a él cuando estaba tumbado en prados Grantchester en el verano de 1935. La 'principal idea' podría haber sido su análisis de la computación o su realización de que había una máquina universal, y por lo tanto un argumento diagonal para demostrar la insolvabilidad.

—ibíd., pág. 76

Si bien Gandy creía que la declaración anterior de Newman es "engañosa", esta opinión no es compartida por todos. Turing tuvo un interés de por vida en las máquinas: 'Alan había soñado con inventar máquinas de escribir cuando era niño; [su madre] la Sra. Turing tenía una máquina de escribir; y bien podría haber comenzado preguntándose qué significaba llamar a una máquina de escribir 'mecánica'. (Hodges pág. 96). Mientras estaba en Princeton haciendo su doctorado, Turing construyó un multiplicador de lógica booleana (ver más abajo). Su tesis doctoral, titulada "Sistemas de lógica basados en ordinales", contiene la siguiente definición de "una función computable":

Se dijo arriba que "una función es efectivamente calculable si sus valores pueden ser encontrados por algún proceso puramente mecánico". Podemos tomar esta declaración literalmente, entendiendo por un proceso puramente mecánico que podría ser llevado a cabo por una máquina. Es posible dar una descripción matemática, en cierta forma normal, de las estructuras de estas máquinas. El desarrollo de estas ideas conduce a la definición del autor de una función computable, y a una identificación de computabilidad con calculabilidad efectiva. No es difícil, aunque algo laborioso, probar que estas tres definiciones [el tercero es el λ-calculus] son equivalentes.

—Turing (1939) in Los indecidables, pág. 160

Alan Turing inventó la "una máquina" (máquina automática) en 1936. Turing envió su artículo el 31 de mayo de 1936 a la London Mathematical Society para sus Proceedings (cf. Hodges 1983: 112), pero se publicó a principios de 1937 y había separatas disponibles en febrero de 1937 (cf. Hodges 1983: 129) Fue el asesor de doctorado de Turing, Alonzo Church, quien más tarde acuñó el término "máquina de Turing" en una revisión. Con este modelo, Turing pudo responder negativamente a dos preguntas:

• ¿Existe una máquina que pueda determinar si cualquier máquina arbitraria en su cinta es "circular" (por ejemplo, congela o no continúa su tarea computacional)?
• ¿Existe una máquina que pueda determinar si alguna máquina arbitraria en su cinta alguna vez imprime un símbolo dado?

Por lo tanto, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo probar las propiedades de la computación en general y, en particular, la imposibilidad de calcular el Entscheidungsproblem ('problema de decisión').

Cuando Turing regresó al Reino Unido, finalmente se convirtió en responsable conjunto de descifrar los códigos secretos alemanes creados por máquinas de encriptación llamadas "El Enigma"; también se involucró en el diseño del ACE (Automatic Computing Engine), la propuesta del ACE de [Turing] era efectivamente independiente, y sus raíces no estaban en el EDVAC [los EE. UU. iniciativa], sino en su propia máquina universal" (Hodges pág. 318). Aún continúan los argumentos sobre el origen y la naturaleza de lo que Kleene (1952) ha denominado Tesis de Turing. Pero lo que Turing probó con su modelo de máquina computacional aparece en su artículo "On Computable Numbers, with an Application to the Entscheidungsproblem" (1937):

El Hilbert Entscheidungsproblema no puede tener solución... Propongo, por lo tanto, demostrar que no puede haber un proceso general para determinar si una fórmula dada U del cálculo funcional K es provable, es decir, que no puede haber una máquina que, suministrado con cualquier U de estas fórmulas, eventualmente dirá si U es provable.

—del papel de Turing como reimpreso Los indecidables, pág. 145

Ejemplo de Turing (su segunda prueba): si uno va a pedir un procedimiento general para decirnos: "¿Esta máquina alguna vez imprime 0", la pregunta es "indecidible& #34;.

1937–1970: la "computadora digital", el nacimiento de la "ciencia de la computación"

En 1937, mientras trabajaba en Princeton en su tesis doctoral, Turing construyó un multiplicador digital (lógica booleana) desde cero, haciendo sus propios relés electromecánicos (Hodges p. 138). "La tarea de Alan era incorporar el diseño lógico de una máquina de Turing en una red de interruptores operados por relé..." (Hodges pág. 138). Si bien Turing podría haber sido inicialmente curioso y experimentador, un trabajo bastante serio en la misma dirección estaba yendo en Alemania (Konrad Zuse (1938)), y en los Estados Unidos (Howard Aiken) y George Stibitz (1937); los frutos de su trabajo fueron utilizados por los ejércitos del Eje y los Aliados en la Segunda Guerra Mundial (cf. Hodges p. 298–299). A principios y mediados de la década de 1950, Hao Wang y Marvin Minsky redujeron la máquina de Turing a una forma más simple (un precursor de la máquina Post-Turing de Martin Davis); Simultáneamente, los investigadores europeos estaban reduciendo la computadora electrónica novedosa a un objeto teórico parecido a una computadora equivalente a lo que ahora se llamaba una 'máquina de Turing'. A fines de la década de 1950 y principios de la de 1960, los desarrollos coincidentemente paralelos de Melzak y Lambek (1961), Minsky (1961) y Shepherdson y Sturgis (1961) impulsaron el trabajo europeo más allá y redujeron la máquina de Turing a un modelo informático más amigable. modelo abstracto llamado contador automático; Elgot y Robinson (1964), Hartmanis (1971), Cook y Reckhow (1973) llevaron este trabajo aún más lejos con los modelos de máquinas de registro y máquinas de acceso aleatorio, pero básicamente todas son máquinas de Turing de múltiples cintas con una instrucción similar a la aritmética. colocar.

1970-presente: como modelo de computación

Hoy en día, las máquinas de contador, registro y acceso aleatorio, y su madre, la máquina de Turing, siguen siendo los modelos elegidos por los teóricos que investigan cuestiones de la teoría de la computación. En particular, la teoría de la complejidad computacional hace uso de la máquina de Turing:

Dependiendo de los objetos que uno quiere manipular en las computaciones (números como enteros no negativos o cadenas alfanuméricas), dos modelos han obtenido una posición dominante en la teoría de la complejidad basada en la máquina:

el multitape fuera de línea Máquina de tortuga..., que representa el modelo estándar para la computación orientada a cadenas, y el máquina de acceso al azar (RAM) como presentado por Cook y Reckhow... que modela el ordenador de estilo Von Neumann idealizado.

—van Emde Boas 1990:4

Sólo en el área relacionada de análisis de algoritmos este papel es asumido por el modelo RAM.

—van Emde Boas 1990:16