Máquina de Turing

Computation model defining an abstract machine

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

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 de acuerdo con una tabla de reglas. ^[2] A pesar de la simplicidad del modelo, es capaz de implementar cualquier algoritmo informático . ^[3]

La máquina funciona con una cinta de memoria infinita ^[4] dividida en celdas discretas ^[5] , cada una de las cuales puede contener un único 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 posiciona 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, basándose en 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 ^[6] , o detiene el cálculo. La elección de qué símbolo de reemplazo escribir, en qué dirección mover la cabeza y si detenerse se basa en una tabla finita que especifica qué hacer para cada combinación del estado actual y el símbolo que se lee. Como 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] [8]} quien la llamó una "a-machine" (máquina automática). ^[9] Fue el asesor doctoral de Turing, Alonzo Church , quien más tarde acuñó el término "máquina de Turing" en una reseña. ^[10] 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, se 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? ^{[11] [12]}

De esta manera, 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 ('problema de decisión'). ^[13]

Las máquinas de Turing demostraron la existencia de limitaciones fundamentales en el poder del cálculo mecánico. ^[14] Si bien pueden expresar cálculos arbitrarios, su diseño minimalista las hace demasiado lentas para el cálculo 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 computacional o un sistema de instrucciones para simular una máquina de Turing. Un lenguaje de programación que es completo en términos de Turing es teóricamente capaz de expresar todas las tareas que pueden realizar las computadoras; casi todos los lenguajes de programación son completos en términos de Turing si se ignoran las limitaciones de la memoria finita.

Descripción general

Una máquina de Turing es un modelo idealizado de una unidad central de procesamiento (CPU) que controla toda la manipulación de datos que realiza una computadora. La máquina canónica utiliza una memoria secuencial para almacenar datos. Normalmente, la memoria secuencial se representa como una cinta de longitud infinita en la que 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 se puede definir 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á eventualmente s . Esto se debe al hecho de que el problema de detención es irresoluble, lo que tiene implicaciones importantes 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 de forma robusta la lógica de primer orden de un número infinito de maneras. 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 llama máquina de Turing universal (UTM, o simplemente una 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 de Church-Turing . Esta tesis afirma que las máquinas de Turing, el cálculo lambda y otros formalismos similares de computación efectivamente capturan la noción informal de métodos efectivos en lógica y matemáticas y, por lo tanto, proporcionan un modelo a través del cual uno puede razonar sobre un algoritmo o "procedimiento mecánico" de una manera 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 producido muchos conocimientos sobre la ciencia informática , la teoría de la computabilidad y la teoría de la complejidad .

Descripción física

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

...una capacidad de memoria ilimitada obtenida en forma de una cinta infinita marcada en cuadrados, en cada uno de los cuales se puede 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 otros lugares no afectan el comportamiento de la máquina. Sin embargo, la cinta se puede mover hacia adelante y hacia atrás a través de la máquina, siendo esta una de las operaciones elementales de la máquina. Cualquier símbolo en la cinta puede, por lo tanto, eventualmente tener una entrada. ^[15]

—  Turing 1948, pág. 3 ^[16]

Descripción

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 la vez, utilizando un cabezal de cinta. El funcionamiento está completamente determinado por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escribe un 1; si el símbolo visto es 1, cambia al estado 17; en el estado 17, si el símbolo visto es 0, escribe un 1 y cambia al estado 6", etc. En el artículo original (" Sobre los números computables, con una aplicación al problema de la endoscopia ", ver también las referencias más abajo), Turing no imagina un mecanismo, sino una persona a la que llama "computadora", que ejecuta estas reglas mecánicas deterministas de manera servil (o como dice Turing, "de manera desganada").

La cabeza siempre se encuentra sobre un cuadrado particular de la cinta; sólo se muestra una extensión finita de cuadrados. La instrucción que se debe ejecutar (q ₄ ) se muestra sobre el cuadrado escaneado. (Dibujo según Kleene (1952) p. 375.)

Aquí, el estado interno (q ₁ ) se muestra dentro del cabezal, y la ilustración describe la cinta como infinita y precargada con "0", el símbolo que sirve como espacio en blanco. El estado completo del sistema (su "configuración completa") consiste en el estado interno, cualquier símbolo que no esté en blanco en la cinta (en esta ilustración "11B"), y la posición del cabezal en relación con esos símbolos, incluidos los espacios en blanco, es decir, "011B". (Dibujo basado en Minsky (1967) p. 121.)

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 se puede extender arbitrariamente hacia la izquierda y hacia la derecha, de modo que la máquina de Turing siempre tenga tanta cinta como necesite para su cálculo. Se supone que las celdas que no se han escrito antes están llenas 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 que puede leer y escribir símbolos en la cinta y moverla hacia la izquierda y hacia la derecha una (y sólo una) celda a la vez. En algunos modelos, el cabezal se mueve y la cinta permanece fija.
• Un registro de estado que almacena el estado de la máquina de Turing, uno de los muchos que existen. Entre ellos se encuentra el estado de inicio especial con el que se inicializa el registro de estado. Estos estados, escribe Turing, reemplazan el "estado mental" en el que se encontraría normalmente una persona que realiza cálculos.
• Una tabla finita ^[17] de instrucciones ^[18] 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 debajo del cabezal), le indica a la máquina que haga lo siguiente en secuencia (para los modelos de 5 tuplas ):

1. Borre o escriba un símbolo (reemplazando una _j por una _j1 ).
2. Mover la cabeza (que se describe con d _k y puede tener valores: 'L' para un paso a la izquierda o '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 hacia la izquierda o hacia la derecha (d _k ) se especifican como instrucciones separadas. La tabla le indica a la máquina que (ia) borre o escriba un símbolo o (ib) mueva el cabezal hacia la izquierda o hacia la derecha, y luego (ii) asuma el mismo estado o uno nuevo según lo prescrito, pero no ambas acciones (ia) y (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, entonces la máquina se detendrá; otros modelos requieren que se completen todas las entradas.

Cada parte de la máquina (es decir, su estado, colecciones de símbolos y cinta utilizada en un momento dado) y sus acciones (como imprimir, borrar y mover la cinta) son finitas , discretas y distinguibles ; es la cantidad ilimitada de cinta y tiempo de ejecución lo que le otorga una cantidad ilimitada de espacio de almacenamiento .

Definición formal

Siguiendo a Hopcroft y Ullman (1979, p. 148), una máquina de Turing (de una cinta) se puede definir formalmente como una tupla de 7 donde ${\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle }$

• ${\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 pueden aparecer en el contenido inicial de la cinta;
• ${\displaystyle Q}$es un conjunto finito y no vacío de estados ;
• ${\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 si finalmente se detiene en un estado de . ${\displaystyle M}$ ${\displaystyle F}$
• ${\displaystyle \delta :(Q\setminus F)\times \Gamma \not \to Q\times \Gamma \times \{L,R\}}$es una función parcial llamada función de transición , donde L es desplazamiento a la izquierda, R es desplazamiento a la derecha. Si no está definido en el estado actual y el símbolo de cinta actual, entonces la máquina se detiene; ^[19] 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 \delta }$

Castor atareado de 3 estados. Los íconos negros representan la ubicación y el estado de la cabeza; los colores cuadrados representan los 1 (naranja) y los 0 (blanco); el tiempo avanza verticalmente desde la parte superior hasta el estado HALT en la parte inferior.

Una variante relativamente poco común permite "ningún desplazamiento", digamos N, como 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 ejemplos de máquinas de Turing ):

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

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

Se requieren detalles adicionales para visualizar o implementar máquinas de Turing

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

Por ejemplo,

• Será necesario tomar muchas decisiones sobre cómo se verán realmente los símbolos y encontrar una forma infalible de leerlos y escribirlos indefinidamente.
• Las operaciones de desplazamiento a la izquierda y desplazamiento a la derecha pueden desplazar el cabezal de la cinta a lo largo de la misma, pero cuando se construye una máquina de Turing es más práctico hacer que la cinta se deslice hacia adelante y hacia atrás debajo del cabezal.
• La cinta puede ser finita y extenderse automáticamente con espacios en blanco según sea necesario (lo que se acerca más a la definición matemática), pero es más común pensar en ella como si se estirara infinitamente en uno o ambos extremos y se llenara previamente con espacios en blanco, excepto en el fragmento finito explícitamente dado en el que 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 correspondería a 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 una máquina de estados finitos si fuera estrictamente de longitud fija.

Definiciones alternativas

Las definiciones en la literatura a veces difieren ligeramente, para hacer que los argumentos o las pruebas sean más fáciles o más claras, pero esto siempre se hace de tal manera que la máquina resultante tenga la misma potencia computacional. Por ejemplo, el conjunto podría cambiarse de a , donde N ("Ninguno" o "Sin operación") permitiría que la máquina permaneciera en la misma celda de la cinta en lugar de moverse hacia la izquierda o la derecha. Esto no aumentaría la potencia computacional de la máquina. ${\displaystyle \{L,R\}}$ ${\displaystyle \{L,R,N\}}$

La convención más común representa cada "instrucción de Turing" en una "tabla de Turing" mediante una de nueve 5-tuplas, según la convención de Turing/Davis (Turing (1936) en The Undecidable , pág. 126-127 y Davis (2000) pág. 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 , imprimir símbolo S _k /borrar E /ninguno N , mover cinta un cuadrado a la izquierda L /derecha R /ninguno 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 listado 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 , imprimir símbolo S _k /borrar E /ninguno N , mover_cinta_un_cuadrado_a_la_izquierda L /derecha R /ninguno N )

En el resto de este artículo se utilizará la "definición 1" (la convención de Turing/Davis).

En la siguiente tabla, el modelo original de Turing permitía solo las tres primeras líneas, que él llamó N1, N2, N3 (cf. Turing en The Undecidable , p. 126). Permitió el borrado del "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 "imprimir símbolo 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áquina han permitido los nueve tipos posibles de cinco-tuplas:

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

Con menor frecuencia se encuentran el uso de 4-tuplas: estas representan una atomización adicional de las instrucciones de Turing (cf. Post (1947), Boolos y Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); consulte también más en Máquina Post–Turing .

El "estado"

La palabra "estado" utilizada 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 referirse al nombre o designador de la instrucción actual que se debe ejecutar, es decir, el contenido del registro de estado. Pero Turing (1936) hizo una clara distinción entre un registro de lo que llamó la "configuración m" de la máquina y el "estado de progreso" de la máquina (o persona) a través del cómputo, es decir, el estado actual del sistema total. Lo que Turing llamó "la fórmula de estado" incluye tanto la instrucción actual como todos los símbolos de la cinta:

De este modo, el estado de progreso del cálculo 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 describirse mediante una única expresión (secuencia de símbolos) que consiste en los símbolos en la cinta seguidos de Δ (que se supone que no aparece en ningún otro lugar) y luego por la nota de instrucciones. Esta expresión se denomina "fórmula de estado".

—  Lo indecidible , págs. 139-140, énfasis añadido

En un artículo anterior, 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); a esto lo llama "la configuración completa " ( The Undecidable , 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 el símbolo de "configuración m" q ₄ sobre el cuadrado escaneado aproximadamente en el centro de los 6 cuadrados no en blanco en la cinta (ver la figura de la cinta de Turing en este artículo) y lo pone a la derecha del cuadrado escaneado. Pero Kleene se refiere a "q ₄ " en sí mismo como "el estado de la máquina" (Kleene, p. 374-375). Hopcroft y Ullman llaman a esta composición la "descripción instantánea" y siguen 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 composición de los símbolos no en blanco a la izquierda, el estado de la máquina, el símbolo actual escaneado por el cabezal y los símbolos no 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 "ejecutar" en la figura siguiente):

1 un 1

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

"Estado" en el contexto de las máquinas de Turing debe aclararse en cuanto a 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 a la izquierda del símbolo escaneado o a la derecha del símbolo escaneado.

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

Diagramas de "estado"

La máquina de Turing del "castor atareado de 3 estados" en una representación de estados finitos . Cada círculo representa un "estado" de la tabla: una "configuración m" o "instrucción". La "dirección" de una transición de estado se muestra mediante 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 una barra / , seguida de los "comportamientos" subsiguientes de la máquina, por ejemplo, " P imprimir " y luego mover la cinta " R a la derecha ". No existe un formato general aceptado. La convención que se muestra es la de McClusky (1965), Booth (1967), Hill y Peterson (1974).

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

Por lo general, es mejor dejar las tablas grandes como tablas (Booth, p. 74). Se pueden simular más fácilmente por computadora en forma 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. 244ff)) se pueden ver más fácilmente cuando se ven como un dibujo.

Si un dibujo representa una mejora con respecto a su tabla, es algo que debe decidir el lector en el contexto particular.

La evolución del cálculo del castor ocupado comienza desde arriba y continúa hacia abajo.

El lector debe tener en cuenta nuevamente 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 cada vez que la atareada máquina castor "funciona" siempre seguirá la misma trayectoria de estado, esto no es cierto para la máquina "copiadora" a la que se le pueden proporcionar "parámetros" de entrada variables.

El diagrama "progreso del cómputo" muestra el progreso del "estado" (instrucción) del castor atareado de tres estados a través de su cómputo desde el principio hasta el final. En el extremo derecho se encuentra la "configuración completa" de Turing ("situación" de Kleene, "descripción instantánea" de Hopcroft-Ullman) en cada paso. Si la máquina se detuviera y se borrara el "registro de estado" y la cinta entera, estas "configuraciones" podrían usarse para reavivar un cómputo en cualquier parte de su progreso (cf. Turing (1936) The Undecidable , pp. 139-140).

Modelos equivalentes

Se puede demostrar que muchas máquinas que podrían tener una capacidad computacional mayor que una simple máquina universal de Turing no tienen más potencia (Hopcroft y Ullman, pág. 159; cf. Minsky (1967)). Tal vez calculen más rápido o utilicen menos memoria, o su conjunto de instrucciones sea menor, pero no pueden calcular con mayor potencia (es decir, más funciones matemáticas). (La tesis de Church-Turing plantea la hipótesis de que esto es cierto para cualquier tipo de máquina: cualquier cosa que pueda ser "calculada" puede ser calculada por alguna máquina de Turing.)

Una máquina de Turing es equivalente a un autómata de pila única (PDA, por sus siglas en inglés) que se ha vuelto más flexible y conciso al relajar el requisito de último en entrar, primero en salir (LIFO, por sus siglas en inglés) 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, al usar una pila para modelar la cinta a la izquierda de la cabeza 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 el mismo poder computacional que el modelo de máquina de Turing.

Los modelos equivalentes comunes son la máquina de Turing multicinta , la máquina de Turing multipista , 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 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 y movimiento hacia la derecha son equivalentes a los DFA (así como a los NFA mediante conversión utilizando el algoritmo de conversión de NFA a DFA ).

Para fines prácticos y didácticos, la máquina de registros equivalentes puede utilizarse como lenguaje de programación ensamblador habitual .

Una pregunta relevante es si el modelo computacional representado por lenguajes de programación concretos es equivalente a Turing o no. Mientras que 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 lo son. Por ejemplo, ANSI C no es Turing completo, ya que todas las instancias de ANSI C (diferentes instancias son posibles ya que el estándar deja deliberadamente cierto comportamiento sin definir por razones de legado) 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 simplemente 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 cuando ignora las asignaciones de memoria fallidas, pero los programas compilados ejecutables en una computadora real no pueden.

Selección de máquinas C y máquinas O de Oracle

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 está determinado sólo 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 realizado una elección arbitraria. Este sería el caso si estuviéramos utilizando máquinas para tratar con sistemas axiomáticos.

—  Lo indecidible , 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 utilizar una máquina a para "encontrar todas las fórmulas demostrables del cálculo [de Hilbert]" en lugar de utilizar una máquina de elección. "Supone que las elecciones son siempre entre dos posibilidades 0 y 1. Cada prueba estará determinada entonces 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, ..." (Nota a pie de página ‡, The Undecidable , p. 138)

Esta es, de hecho, la técnica mediante la cual una máquina de Turing determinista (es decir, a-) puede utilizarse 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 mayor consideración.

Una máquina oráculo o máquina-o es una máquina-a de Turing que pausa su cálculo en el estado " o " mientras, para completar su cálculo, "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), Lo indecidible , pág. 166-168).

Máquinas universales de Turing

Una implementación de una máquina de Turing

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

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

Este hallazgo hoy se da por sentado, pero en su momento (1936) se consideró asombroso. ^{[ cita requerida ]} 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 la computadora con programa almacenado .

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

—  Minsky (1967), pág. 104

En términos de complejidad computacional , una máquina universal de Turing de múltiples cintas sólo necesita ser más lenta en 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 . (Arora y Barak, 2009, teorema 1.9)

Comparación con máquinas reales

Realización de una máquina de Turing utilizando piezas de Lego

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 empuje . 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 ejecutar. Lo que se pasa por alto en esta afirmación es que, como 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 tiene una cantidad ilimitada de espacio de almacenamiento disponible para sus cálculos.

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

• Todo lo que un ordenador real puede calcular, una máquina de Turing también puede calcularlo. Por ejemplo: "Una máquina de Turing puede simular cualquier tipo de subrutina que se encuentre en los lenguajes de programación, incluidos los procedimientos recursivos y cualquiera de los mecanismos de paso de parámetros conocidos" (Hopcroft y Ullman, pág. 157). Un FSA lo suficientemente grande también puede modelar cualquier ordenador real, sin tener en cuenta la E/S. Por lo tanto, una afirmación sobre las limitaciones de las máquinas de Turing también se aplicará a los ordenadores reales.
• La única diferencia radica en la capacidad de una máquina de Turing para manipular una cantidad ilimitada de datos. Sin embargo, dada una cantidad finita de tiempo, una máquina de Turing (como una máquina real) sólo 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 que utilizan modelos abstractos más simples 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 del AFD sea inviable de analizar.
• Las máquinas de Turing describen algoritmos independientemente de la cantidad de memoria que utilicen. Existe un límite para la memoria que posee cualquier máquina actual, pero este límite puede aumentar arbitrariamente con el tiempo. Las máquinas de Turing nos permiten hacer afirmaciones sobre algoritmos que (teóricamente) se mantendrán para siempre, 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 tener tipos de datos de precisión arbitraria disponibles y nunca tienen que lidiar con condiciones inesperadas (incluida, entre otras, quedarse sin memoria ).

Otra realización de la máquina de 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 particular. Por ejemplo, las computadoras modernas con programa almacenado son en realidad instancias de una forma más específica de máquina abstracta conocida como la máquina de programa almacenado de acceso aleatorio o modelo de máquina RASP. Al igual que la máquina universal de Turing, la RASP almacena su "programa" en una "memoria" externa a las "instrucciones" de su máquina de estados finitos. A diferencia de la máquina universal de Turing, la RASP tiene un número infinito de "registros" distinguibles, numerados pero ilimitados: "celdas" de memoria que pueden contener cualquier número entero (cf. Elgot y Robinson (1964), Hartmanis (1971), y en particular Cook-Rechow (1973); referencias en random-access machine ). La máquina de estados finitos de la RASP está equipada con la capacidad de direccionamiento indirecto (por ejemplo, el contenido de un registro puede usarse como una dirección para especificar otro registro); por lo tanto, el "programa" de la RASP 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 se utilizan máquinas de Turing como base para limitar los tiempos de ejecución, se puede demostrar un "límite inferior falso" en los tiempos de ejecución de ciertos algoritmos (debido al supuesto de simplificación falsa 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 máquina de Turing.

Interacción

En los primeros tiempos de la informática, el uso de las computadoras se limitaba generalmente al procesamiento por lotes , es decir, tareas no interactivas, cada una de las cuales generaba 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 ha vuelto 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 ocurre realmente la interacción; por lo tanto, al describir la interactividad, generalmente se prefieren alternativas como los autómatas de E/S .

Comparación con el modelo aritmético de cálculo

El modelo aritmético de cálculo difiere del modelo de Turing en dos aspectos: ^{[20] : 32}

• 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 de la cantidad 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 polinómico 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 realiza los cálculos elevando al cuadrado repetidamente se ejecuta en tiempo polinómico en el modelo aritmético, pero no en el modelo de Turing. Esto se debe a que la cantidad de bits necesarios para representar el resultado es exponencial en el tamaño de entrada. ${\displaystyle 2^{2^{n}}}$

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 en la longitud de la entrada, entonces siempre es tiempo polinomial en el modelo de Turing. Se dice que un algoritmo de este tipo se ejecuta en tiempo fuertemente polinomial .

Historia

Antecedentes históricos: maquinaria computacional

Robin Gandy (1919-1995), alumno de Alan Turing (1912-1954) y su amigo de toda la vida, rastrea el linaje de la noción de "máquina calculadora" hasta Charles Babbage (circa 1834) y, de hecho, propone la "Tesis de Babbage":

Que todo el desarrollo y las operaciones de análisis ahora pueden ser ejecutados por máquinas .

—  (cursiva en Babbage, citado por Gandy, p. 54)

El análisis de Gandy de la máquina analítica de Babbage describe las siguientes cinco operaciones (cf. p. 52-53):

1. Las funciones aritméticas +, −, ×, donde − indica resta "adecuada": x − y = 0 si y ≥ x .
2. Cualquier secuencia de operaciones es una operación.
3. Iteración de una operación (repetir n veces una operación P).
4. Iteración condicional (repetir n veces una operación P condicional al "éxito" de la prueba T).
5. Transferencia condicional (es decir, " goto " condicional ).

Gandy afirma que "las funciones que pueden calcularse mediante (1), (2) y (4) son precisamente aquellas que son computables mediante el método de Turing " (p. 53). Cita otras propuestas de "máquinas calculadoras universales", incluidas las de Percy Ludgate (1909), Leonardo Torres Quevedo (1914), ^{[21] [22]} Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken (1937). Sin embargo:

… el énfasis está puesto en programar una secuencia iterable fija de operaciones aritméticas. No se reconoce la importancia fundamental de la iteración condicional y de la transferencia condicional para una teoría general de las máquinas de cálculo…

—  Gandy pág. 55

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

En relación con 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 formulara con precisión. La expresión original de Hilbert para el n.° 10 es la siguiente:

10. Determinación de la solubilidad de una ecuación diofántica . Dada una ecuación diofántica con cualquier número de incógnitas y con coeficientes enteros racionales: Idear un proceso según el cual se pueda determinar en un número finito de operaciones si la ecuación es resoluble en números enteros racionales. El Entscheidungsproblem [problema de decisión para lógica de primer orden ] se resuelve cuando conocemos un procedimiento que permite que cualquier expresión lógica dada decida mediante un número finito de operaciones su validez o satisfacibilidad... El Entscheidungsproblem debe considerarse el principal problema de la lógica matemática.

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

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

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

Se requiere una prescripción bastante definida y de aplicación general que permita decidir en un número finito de pasos la verdad o falsedad de una afirmación puramente lógica dada...

—  Gandy p. 57, citando a Behmann

Behmann señala que... el problema general es equivalente al problema de decidir qué proposiciones matemáticas son verdaderas.

—  ibíd.

Si uno fuera capaz de resolver el Entscheidungsproblem entonces tendría un "procedimiento para resolver muchos (o incluso todos) los problemas matemáticos".

—  ibíd. , pág. 92

En el congreso internacional de matemáticos de 1928, Hilbert "formuló sus preguntas con bastante precisión. En primer lugar, ¿las matemáticas eran completas ?... En segundo lugar, ¿las matemáticas eran consistentes ?... Y en tercer lugar, ¿las matemáticas eran decidibles ?" (Hodges, pág. 91; Hawking, pág. 1121). Las dos primeras preguntas fueron respondidas en 1930 por Kurt Gödel en la misma reunión en la que Hilbert pronunció su discurso de retiro (para gran disgusto de Hilbert); la tercera -el Entscheidungsproblem- tuvo que esperar hasta mediados de los años treinta.

El problema era que una respuesta requería primero una definición precisa de "prescripción general aplicable definida", que el profesor de Princeton Alonzo Church llegaría a llamar " calculabilidad efectiva ", y en 1928 no existía tal definición. Pero durante los siguientes 6-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), como lo hicieron Church y sus dos estudiantes Stephen Kleene y JB Rosser mediante el uso del cálculo lambda de Church y la teoría de la recursión de Gödel (1934). El artículo de Church (publicado el 15 de abril de 1936) demostró que el Entscheidungsproblem era de hecho "indecidible" ^[23] y se adelantó a Turing por casi un año (el 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 evaluaba el artículo de Turing, Turing tuvo tiempo de estudiarlo 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 Church 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 proporcionaba un argumento a partir de los primeros principios, cerrando la brecha en la demostración de Church.

—  Hodges pág. 112

Y Post sólo 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 el King's College, Cambridge , aceptó el desafío; había sido estimulado por las conferencias del lógico MHA Newman "y había aprendido de ellas sobre el trabajo de Gödel y el Entscheidungsproblem ... Newman usó la palabra 'mecánico' ... En su obituario de Turing de 1955, Newman escribe:

A la pregunta "¿qué es un proceso "mecánico"?", Turing respondió con la típica frase "algo que puede realizar una máquina" y se embarcó en la muy agradable tarea de analizar el concepto general de máquina de computación.

—  Gandy, pág. 74

Gandy afirma que:

Supongo, pero no lo sé, que Turing, desde el comienzo de su trabajo, tuvo como objetivo probar la indecidibilidad del Entscheidungsproblem. Me dijo que la "idea principal" del artículo se le ocurrió cuando estaba tumbado en los prados de Grantchester en el verano de 1935. La "idea principal" podría haber sido su análisis de la computación o su descubrimiento de que existía una máquina universal y, por tanto, un argumento diagonal para demostrar la insolubilidad.

—  ibíd. , pág. 76

Aunque Gandy creía que la afirmación de Newman antes mencionada es "engañosa", no todos comparten esta opinión. Turing siempre estuvo interesado en las máquinas: "Alan había soñado con inventar máquinas de escribir cuando era niño; [su madre] la señora Turing tenía una máquina de escribir; y bien podría haber comenzado por preguntarse qué significaba llamar "mecánica" a una máquina de escribir" (Hodges, pág. 96). Mientras estudiaba su doctorado en Princeton, Turing construyó un multiplicador de lógica booleana (véase 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 ha afirmado anteriormente que «una función es efectivamente calculable si sus valores pueden hallarse mediante algún proceso puramente mecánico». Podemos tomar esta afirmación en sentido literal, entendiendo por proceso puramente mecánico aquel 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 la computabilidad con la calculabilidad efectiva. No es difícil, aunque algo laborioso, demostrar que estas tres definiciones [la tercera es el cálculo λ] son ​​equivalentes.

—  Turing (1939) en Lo indecidible , pág. 160

Alan Turing inventó la "máquina a" (máquina automática) en 1936. ^[7] Turing presentó su artículo el 31 de mayo de 1936 a la London Mathematical Society para sus Actas (cf. Hodges 1983:112), pero se publicó a principios de 1937 y las separatas estuvieron disponibles en febrero de 1937 (cf. Hodges 1983:129). Fue el asesor doctoral de Turing, Alonzo Church , quien más tarde acuñó el término "máquina de Turing" en una revisión. ^[24] 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, se 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? ^{[25] [26]}

De esta manera, 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 ('problema de decisión'). ^[27]

Cuando Turing regresó al Reino Unido, se convirtió en corresponsable de descifrar los códigos secretos alemanes creados por las máquinas de cifrado llamadas "Enigma"; también participó en el diseño de la ACE ( Automatic Computing Engine ), "la propuesta de la ACE [de Turing] era efectivamente autónoma, y ​​sus raíces no se encontraban en la EDVAC [iniciativa de los EE. UU.], sino en su propia máquina universal" (Hodges, p. 318). Todavía continúan los debates sobre el origen y la naturaleza de lo que Kleene (1952) denominó la tesis de Turing . Pero lo que Turing demostró con su modelo de máquina computacional aparece en su artículo " Sobre los números computables, con una aplicación al problema de la entscheidung " (1937):

[que] el problema de determinación de Hilbert no puede tener solución... Propongo, por tanto, demostrar que no puede haber un proceso general para determinar si una fórmula dada U del cálculo funcional K es demostrable, es decir, que no puede haber ninguna máquina que, suministrada con cualquiera de estas fórmulas U, diga eventualmente si U es demostrable.

—  del artículo de Turing reproducido en The Undecidable , pág. 145

El ejemplo de Turing (su segunda prueba): si uno pide un procedimiento general que nos diga: "¿Esta máquina alguna vez imprime 0?", la pregunta es "indecidible".

1937-1970: La «computadora digital», el nacimiento de la «ciencia informática»

En 1937, mientras trabajaba en su tesis doctoral en Princeton, Turing construyó un multiplicador digital (lógica booleana) desde cero, fabricando 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és..." (Hodges p. 138). Si bien Turing puede haber sido inicialmente curioso y experimental, se estaba realizando un trabajo bastante serio en la misma dirección en Alemania ( Konrad Zuse (1938)) y en los Estados Unidos ( Howard Aiken ) y George Stibitz (1937); los frutos de sus trabajos fueron utilizados tanto por los ejércitos del Eje como por 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 ); Al mismo tiempo, los investigadores europeos reducían la novedosa computadora electrónica a un objeto teórico similar a una computadora, equivalente a lo que ahora se denominaba 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) llevaron el trabajo europeo más allá y redujeron la máquina de Turing a un modelo abstracto más amigable y similar a una computadora, llamado la máquina contadora ; Elgot y Robinson (1964), Hartmanis (1971), Cook y Reckhow (1973) llevaron este trabajo aún más lejos con los modelos de máquina de registro y máquina de acceso aleatorio , pero básicamente todos son simplemente máquinas de Turing de múltiples cintas con un conjunto de instrucciones de tipo aritmético.

1970-presente: como modelo de computación

En la actualidad, las máquinas de contadores, registros y acceso aleatorio y su antecesora, la máquina de Turing, siguen siendo los modelos preferidos 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 desea manipular en los cálculos (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 máquinas:

la máquina de Turing multicinta fuera de línea ..., que representa el modelo estándar para la computación orientada a cadenas, y la máquina de acceso aleatorio (RAM) introducida por Cook y Reckhow..., que modela la computadora idealizada de estilo Von Neumann.

—Van  Emde Boas 1990:4

Sólo en el área relacionada con el análisis de algoritmos, este papel lo asume el modelo RAM.

—Van  Emde Boas 1990:16

Véase también

• Jerarquía aritmética
• Límite de Bekenstein , que muestra la imposibilidad de máquinas de Turing de cinta infinita de tamaño finito y energía limitada
• BlooP y FlooP
• Constante de Chaitin u Omega (informática) para obtener información relacionada con el problema de la detención
• Habitación china
• El juego de la vida de Conway , un autómata celular Turing-completo
• Infinito digital
• La nueva mente del emperador
• Enumerador (en informática teórica)
• Genética
• Gödel, Escher, Bach: Una eterna trenza de oro , un famoso libro que aborda, entre otros temas, la tesis de Church-Turing
• Problema de parada , para más referencias
• Arquitectura de Harvard
• Programación imperativa
• La hormiga de Langton y Turmites , análogos bidimensionales simples de la máquina de Turing
• Lista de cosas que llevan el nombre de Alan Turing
• Arquitectura Harvard modificada
• Máquina cuántica de Turing
• Claude Shannon , otro pensador destacado en la teoría de la información
• Ejemplos de máquinas de Turing
• Interruptor de Turing
• Tarpit de Turing , cualquier sistema informático o lenguaje que, a pesar de ser Turing completo, generalmente se considera inútil para la computación práctica.
• Máquina no organizada , para las primeras ideas de Turing sobre redes neuronales
• Arquitectura de von Neumann

Notas

1. Minsky 1967:107 "En su artículo de 1936, AM Turing definió la clase de máquinas abstractas que ahora llevan su nombre. Una máquina de Turing es una máquina de estados finitos asociada con un tipo especial de entorno - su cinta - en el que puede almacenar (y luego recuperar) secuencias de símbolos", también Stone 1972:8 donde la palabra "máquina" está entre comillas.
2. Stone 1972:8 afirma que "Esta "máquina" es un modelo matemático abstracto", cf. también Sipser 2006:137ff que describe el "modelo de máquina de Turing". Rogers 1987 (1967):13 se refiere a la "caracterización de Turing", Boolos Burgess y Jeffrey 2002:25 se refieren a un "tipo específico de máquina idealizada".
3. Sipser 2006:137 "Una máquina de Turing puede hacer todo lo que una computadora real puede hacer".
4. Cf. Sipser 2002:137. Asimismo, Rogers 1987 (1967):13 describe "una cinta de papel de longitud infinita en ambas direcciones". Minsky 1967:118 afirma "La cinta se considera infinita en ambas direcciones". Boolos Burgess y Jeffrey 2002:25 incluyen la posibilidad de que "hay alguien ubicado en cada extremo para agregar cuadrados en blanco adicionales según sea necesario".
5. Cf. Rogers 1987 (1967):13. Otros autores utilizan la palabra "cuadrado", por ejemplo Boolos Burgess Jeffrey 2002:35, Minsky 1967:117, Penrose 1989:37.
6. Boolos Burgess Jeffry 2002:25 ilustra la máquina como si se moviera a lo largo de la cinta. Penrose 1989:36-37 se describe a sí mismo como "incómodo" con una cinta infinita y observa que "¡podría ser difícil de mover!"; él "prefiere pensar en la cinta como si representara algún entorno externo a través del cual nuestro dispositivo finito puede moverse" y después de observar que el "'movimiento' es una forma conveniente de representar las cosas", sugiere que "el dispositivo recibe toda su información de este entorno". Algunas variaciones del modelo de la máquina de Turing también permiten que la cabeza permanezca en la misma posición en lugar de moverse o detenerse.
7. Hodges, Andrew (2012). Alan Turing: El enigma (edición del centenario). Princeton University Press . ISBN 978-0-691-15564-7.
8. La idea se le ocurrió a mediados de 1935 (tal vez, ver más en la sección de Historia) después de una pregunta planteada por MHA Newman en sus conferencias: "¿Había un método definido, o como Newman lo expresó, un "proceso mecánico" que pudiera aplicarse a un enunciado matemático, y que diera la respuesta a si era demostrable?" (Hodges 1983:93). Turing presentó su artículo el 31 de mayo de 1936 a la Sociedad Matemática de Londres para sus Actas (cf. Hodges 1983:112), pero se publicó a principios de 1937 y las separatas estuvieron disponibles en febrero de 1937 (cf. Hodges 1983:129).
9. Véase la nota a pie de página en Davis 2000:151.
10. ver nota en el prólogo de The Collected Works of Alonzo Church ( Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). ​​The Collected Works of Alonzo Church. Cambridge, MA, EE. UU.: MIT Press. ISBN 978-0-262-02564-5.)
11. Turing 1936 en The Undecidable 1965:132-134; la definición de Turing de "circular" se encuentra en la página 119.
12. Turing, Alan Mathison (1937). "Sobre números computables, con una aplicación al problema de Entscheidung ". Actas de la London Mathematical Society . Serie 2. 42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712.
13. Turing 1936 en Lo indecidible 1965:145
14. Sipser 2006:137 observa que "una máquina de Turing puede hacer todo lo que una computadora real puede hacer. Sin embargo, incluso una máquina de Turing no puede resolver ciertos problemas. En un sentido muy real, estos problemas están más allá de los límites teóricos de la computación".
15. Véase la definición de "entradas" en Wikcionario
16. AM Turing (julio de 1948). Maquinaria inteligente (informe). Laboratorio Nacional de Física.Aquí: p.3-4
17. En ocasiones se la denomina tabla de acciones o función de transición .
18. Generalmente quintuplica [5-tuplas]: q _i a _j →q _i1 a _j1 d _k , pero a veces cuadruplica [4-tuplas].
19. p.149; en particular, Hopcroft y Ullman suponen que no está definido en todos los estados desde ${\displaystyle \delta }$ ${\displaystyle F}$
20. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr.  1261419
21. L. Torres Quevedo. Ensayos sobre Automática – Su definición. Extensión teórica de sus aplicaciones, Revista de la Academia de Ciencias Exacta, Revista 12, págs. 391–418, 1914.
22. Torres Quevedo. L. (1915). "Essais sur l'Automatique - Sa définition. Etendue théorique de ses apps", Revue Génerale des Sciences Pures et Appliquées , vol. 2, págs. 601–611.
23. La cuestión más específica planteada en el décimo problema de Hilbert , sobre las ecuaciones diofánticas , permanece sin resolver hasta 1970, cuando finalmente queda al descubierto la relación entre los conjuntos enumerables recursivamente y los conjuntos diofánticos .
24. ver nota en el prólogo de The Collected Works of Alonzo Church ( Burge, Tyler; Enderton, Herbert, eds. (2019-04-23). ​​The Collected Works of Alonzo Church. Cambridge, MA, EE. UU.: MIT Press. ISBN 978-0-262-02564-5.)
25. Turing 1936 en The Undecidable 1965:132-134; la definición de Turing de "circular" se encuentra en la página 119.
26. Turing, Alan Mathison (1937). "Sobre números computables, con una aplicación al problema de Entscheidung ". Actas de la London Mathematical Society . Serie 2. 42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712.
27. Turing 1936 en Lo indecidible 1965:145

Referencias

Literatura primaria, reimpresiones y compilaciones

• B. Jack Copeland ed. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma, Clarendon Press (Oxford University Press), Oxford, Reino Unido, ISBN 0-19-825079-7 . Contiene los documentos de Turing más un borrador de carta a Emil Post sobre su crítica de la "convención de Turing", y Correcciones a la máquina de computación universal de Turing de Donald W. Davies 
• Martin Davis (ed.) (1965), Lo indecidible , Raven Press, Hewlett, Nueva York.
• Emil Post (1936), "Procesos combinatorios finitos: Formulación 1", Journal of Symbolic Logic , 1, 103–105, 1936. Reimpreso en The Undecidable , pp. 289ff.
• Emil Post (1947), "Recursive Unsolvability of a Problem of Thue", Journal of Symbolic Logic , vol. 12, pp. 1–11. Reimpreso en The Undecidable , pp. 293ff. En el Apéndice de este artículo, Post comenta y realiza correcciones al artículo de Turing de 1936–1937. En particular, véanse las notas al pie 11 con correcciones a la codificación de la máquina de computación universal y la nota al pie 14 con comentarios sobre la primera y segunda pruebas de Turing .
• Turing, AM (1936). "Sobre números computables, con una aplicación al problema de Entscheidung". Actas de la London Mathematical Society . 2. 42 (publicado en 1937): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712.(y Turing, AM (1938). "Sobre números computables, con una aplicación al problema de Entscheidung: una corrección". Actas de la London Mathematical Society . 2. 43 (6) (publicado en 1937): 544–6. doi :10.1112/plms/s2-43.6.544.). Reimpreso en muchas colecciones, por ejemplo en The Undecidable , págs. 115-154; disponible en la web en muchos lugares.
• Alan Turing, 1948, "Maquinaria inteligente". Reimpreso en "Cybernetics: Key Papers". Ed. CR Evans y ADJ Robertson. Baltimore: University Park Press, 1968. p. 31. Reimpreso en Turing, AM (1996). "Maquinaria inteligente, una teoría herética". Philosophia Mathematica . 4 (3): 256–260. doi : 10.1093/philmat/4.3.256 .
• FC Hennie y RE Stearns . Simulación de dos cintas de máquinas de Turing multicinta . JACM , 13(4):533–546, 1966.

Teoría de la computabilidad

• Boolos, George; Richard Jeffrey (1999) [1989]. Computabilidad y lógica (3.ª ed.). Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-20402-X.
• Boolos, George; John Burgess; Richard Jeffrey (2002). Computabilidad y lógica (4.ª ed.). Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-00758-5.Burgess ha reescrito en gran medida algunas partes. Presentación de las máquinas de Turing en el contexto de las "máquinas de ábaco" de Lambek (cf. Máquina de registros ) y de las funciones recursivas , mostrando su equivalencia.
• Taylor L. Booth (1967), Sequential Machines and Automata Theory , John Wiley and Sons, Inc., Nueva York. Texto de ingeniería de nivel de posgrado; abarca una amplia variedad de temas; el capítulo IX, Máquinas de Turing, incluye algo de teoría de la recursión.
• Martin Davis (1958). Computabilidad e insolubilidad . McGraw-Hill Book Company, Inc., Nueva York.En las páginas 12 a 20, da ejemplos de tablas de 5 tuplas para la suma, la función sucesora, la resta (x ≥ y), la resta propia (0 si x < y), la función identidad y varias funciones identidad, y la multiplicación.
• Davis, Martin; Ron Sigal; Elaine J. Weyuker (1994). Computabilidad, complejidad y lenguajes y lógica: fundamentos de la informática teórica (2.ª ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 0-12-206382-1.
• Hennie, Fredrick (1977). Introducción a la computabilidad . Addison–Wesley, Reading, Mass. QA248.5H4 1977.En las páginas 90 a 103, Hennie analiza el UTM con ejemplos y diagramas de flujo, pero sin ningún "código" real.
• Hopcroft, John ; Ullman, Jeffrey (1979). Introducción a la teoría de autómatas, lenguajes y computación (1.ª ed.). Addison–Wesley, Reading Mass. ISBN 0-201-02988-X.Centrado en cuestiones de interpretación de "lenguajes" por parte de máquinas, NP-completitud, etc.
• Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría de autómatas, lenguajes y computación (2.ª ed.). Reading Mass: Addison–Wesley. ISBN 0-201-44124-1.
• Stephen Kleene (1952), Introducción a las metamatemáticas , North–Holland Publishing Company, Ámsterdam, Países Bajos, décima edición (con correcciones de la sexta reimpresión, 1971). Texto de nivel de posgrado; la mayor parte del Capítulo XIII Funciones computables trata sobre pruebas de la computabilidad de funciones recursivas con la máquina de Turing, etc.
• Knuth, Donald E. (1973). Volumen 1/Algoritmos fundamentales: el arte de la programación informática (2.ª ed.). Reading, Mass.: Addison–Wesley Publishing Company.. With reference to the role of Turing machines in the development of computation (both hardware and software) see 1.4.5 History and Bibliography pp. 225ff and 2.6 History and Bibliographypp. 456ff.
• Zohar Manna, 1974, Mathematical Theory of Computation. Reprinted, Dover, 2003. ISBN 978-0-486-43238-0
• Marvin Minsky, Computation: Finite and Infinite Machines, Prentice–Hall, Inc., N.J., 1967. See Chapter 8, Section 8.2 "Unsolvability of the Halting Problem."
• Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 2: Turing machines, pp. 19–56.
• Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability, The MIT Press, Cambridge MA, paperback edition 1987, original McGraw-Hill edition 1967, ISBN 0-262-68052-1 (pbk.)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Chapter 3: The Church–Turing Thesis, pp. 125–149.
• Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1st ed.). New York: McGraw–Hill Book Company. ISBN 0-07-061726-0.
• Peter van Emde Boas 1990, Machine Models and Simulations, pp. 3–66, in Jan van Leeuwen, ed., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, [place?], ISBN 0-444-88071-2 (Volume A). QA76.H279 1990.

Church's thesis

• Nachum Dershowitz; Yuri Gurevich (September 2008). "A natural axiomatization of computability and proof of Church's Thesis" (PDF). Bulletin of Symbolic Logic. 14 (3). Retrieved 2008-10-15.
• Roger Penrose (1990) [1989]. The Emperor's New Mind (2nd ed.). Oxford University Press, New York. ISBN 0-19-851973-7.

Small Turing machines

• Rogozhin, Yurii, 1998, "A Universal Turing Machine with 22 States and 2 Symbols", Romanian Journal of Information Science and Technology, 1(3), 259–265, 1998. (surveys known results about small universal Turing machines)
• Stephen Wolfram, 2002, A New Kind of Science, Wolfram Media, ISBN 1-57955-008-8
• Brunfiel, Geoff, Student snags maths prize, Nature, October 24. 2007.
• Jim Giles (2007), Simplest 'universal computer' wins student $25,000, New Scientist, October 24, 2007.
• Alex Smith, Universality of Wolfram's 2, 3 Turing Machine, Submission for the Wolfram 2, 3 Turing Machine Research Prize.
• Vaughan Pratt, 2007, "Simple Turing machines, Universality, Encodings, etc.", FOM email list. October 29, 2007.
• Martin Davis, 2007, "Smallest universal machine", and Definition of universal Turing machine FOM email list. October 26–27, 2007.
• Alasdair Urquhart, 2007 "Smallest universal machine", FOM email list. October 26, 2007.
• Hector Zenil (Wolfram Research), 2007 "smallest universal machine", FOM email list. October 29, 2007.
• Todd Rowland, 2007, "Confusion on FOM", Wolfram Science message board, October 30, 2007.
• Olivier and Marc RAYNAUD, 2014, A programmable prototype to achieve Turing machines Archived 2016-01-14 at the Wayback Machine" LIMOS Laboratory of Blaise Pascal University (Clermont-Ferrand in France).

Other

• Martin Davis (2000). Engines of Logic: Mathematicians and the origin of the Computer (1st ed.). W. W. Norton & Company, New York. ISBN 978-0-393-32229-3.
• Robin Gandy, "The Confluence of Ideas in 1936", pp. 51–102 in Rolf Herken, see below.
• Stephen Hawking (editor), 2005, God Created the Integers: The Mathematical Breakthroughs that Changed History, Running Press, Philadelphia, ISBN 978-0-7624-1922-7. Includes Turing's 1936–1937 paper, with brief commentary and biography of Turing as written by Hawking.
• Rolf Herken (1995). The Universal Turing Machine—A Half-Century Survey. Springer Verlag. ISBN 978-3-211-82637-9.
• Andrew Hodges, Alan Turing: The Enigma, Simon and Schuster, New York. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
• Ivars Peterson (1988). The Mathematical Tourist: Snapshots of Modern Mathematics (1st ed.). W. H. Freeman and Company, New York. ISBN 978-0-7167-2064-5.
• Roger Penrose, The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics, Oxford University Press, Oxford and New York, 1989 (1990 corrections), ISBN 0-19-851973-7.
• Paul Strathern (1997). Turing and the Computer—The Big Idea. Anchor Books/Doubleday. ISBN 978-0-385-49243-0.
• Hao Wang, "A variant to Turing's theory of computing machines", Journal of the Association for Computing Machinery (JACM) 4, 63–92 (1957).
• Charles Petzold, The Annotated Turing, John Wiley & Sons, Inc., ISBN 0-470-22905-5
• Arora, Sanjeev; Barak, Boaz, "Complexity Theory: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4, section 1.4, "Machines as strings and the universal Turing machine" and 1.7, "Proof of theorem 1.9"
• Kantorovitz, Isaiah Pinchas (December 1, 2005). "A note on turing machine computability of rule driven systems". SIGACT News. 36 (4): 109–110. doi:10.1145/1107523.1107525. S2CID 31117713.
• Kirner, Raimund; Zimmermann, Wolf; Richter, Dirk: "On Undecidability Results of Real Programming Languages", In 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, Oct. 2009.

External links

• "Turing machine", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Turing Machine – Stanford Encyclopedia of Philosophy
• Turing Machine Causal Networks by Enrique Zeleny as part of the Wolfram Demonstrations Project.
• Turing Machines at Curlie