máquina de Turing

Modelo computacional que define una máquina abstracta.

Un modelo físico de máquina de Turing. 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 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 alfabeto de la máquina. Tiene una "cabeza" que, en cualquier punto del funcionamiento de la máquina, se sitúa sobre una de estas celdas, y un "estado" seleccionado entre un conjunto finito de estados. En cada paso de su operación, el cabezal lee el símbolo en su celda. Luego, basándose en el símbolo y 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ó "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 puede continuar con su tarea computacional)?
• ¿Existe una máquina que pueda determinar si alguna máquina arbitraria en su cinta imprime alguna vez un símbolo determinado? ^{[11] [12]}

Así, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo demostrar las 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 de la computación mecánica. ^[14] Si bien pueden expresar cálculos arbitrarios, su diseño minimalista los hace demasiado lentos 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 modelo computacional o un sistema de instrucciones para simular una máquina de Turing. Un lenguaje de programación que sea 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.

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 realizada por una computadora, y la máquina canónica utiliza 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 algún subconjunto arbitrario de cadenas válidas de un alfabeto . Un conjunto de cadenas que se pueden enumerar de esta manera se denomina lenguaje recursivamente enumerable . La máquina de Turing puede definirse de manera 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 eventualmente producirá s . 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 informática.

La máquina de Turing es capaz de procesar una gramática ilimitada , lo que implica además que es capaz de evaluar de forma sólida la lógica de primer orden en un número infinito de formas. Esto se demuestra mediante el 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 máquina universal). Alonzo Church introdujo otro formalismo matemático, el cálculo lambda , con una naturaleza "universal" similar . 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 computacionales similares 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 se puede razonar acerca de un algoritmo o "procedimiento mecánico" de manera matemática. manera precisa sin estar atado a ningún formalismo particular. El estudio de las propiedades abstractas de las máquinas de Turing ha aportado muchos conocimientos sobre la 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 constaba de:

...una capacidad de memoria ilimitada obtenida en forma de una cinta infinita dividida 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 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 delante y hacia atrás a través de la máquina, siendo ésta una de las operaciones elementales de la máquina. Por lo tanto, cualquier símbolo en la cinta puede tener eventualmente una entrada. ^[15]

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

Descripción

La máquina de Turing modela matemáticamente una máquina que funciona 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á totalmente 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 números computables, con una aplicación al problema de Entscheidungs ", véanse también las referencias más abajo), Turing no imagina un mecanismo, sino una persona a la que llama "computadora", que ejecuta servilmente estas reglas mecánicas deterministas. (o como dice Turing, "de manera inconexa").

La cabeza siempre está sobre un cuadrado particular de la cinta; sólo se muestra un tramo finito de cuadrados. La instrucción a realizar (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", siendo el símbolo el 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 que incluyen espacios en blanco, es decir, "011B". ". (Dibujo según 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 algún alfabeto finito. El alfabeto contiene un símbolo en blanco especial (aquí escrito como '0') y uno o más símbolos más. 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 recibe tanta cinta como necesita 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 mover la cinta hacia la izquierda y hacia la derecha una (y solo una) celda a la vez. En algunos modelos el cabezal se mueve y la cinta permanece fija.
• Un registro estatal que almacena el estado de la máquina de Turing, una entre un número finito. Entre ellos se encuentra el estado de inicio especial con el que se inicializa el registro estatal. Estos estados, escribe Turing, reemplazan el "estado mental" en el que normalmente se encontraría una persona que realiza cálculos.
• Una tabla finita ^[17] de instrucciones ^[18] que, dado el estado (qi ₎ en el que se encuentra actualmente la máquina y el símbolo ( _aj ) que está leyendo en la cinta (símbolo actualmente debajo del encabezado), le dice 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 con una _j1 ).
2. Mueve 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. Asuma 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 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 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, 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 usada 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 proporciona una cantidad ilimitada de espacio de almacenamiento .

Definicion formal

Siguiendo a Hopcroft y Ullman (1979, p. 148), una máquina de Turing (de una cinta) puede definirse 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, no vacío, de símbolos alfabéticos en cinta ;
• ${\displaystyle b\in \Gamma }$es el símbolo en blanco (el único símbolo que se permite que aparezca en la cinta con infinitas veces 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 de estados finito y no vacío ;
• ${\displaystyle q_{0}\in Q}$es el estado inicial ;
• ${\displaystyle F\subseteq Q}$es el conjunto de estados finales o estados aceptantes . Se dice que el contenido inicial de la cinta es aceptado 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 el desplazamiento a la izquierda y R es el desplazamiento a la derecha. Si no está definido el estado actual y el símbolo de la cinta actual, 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 señalado por la cabeza y el siguiente movimiento de la cabeza. ${\displaystyle \delta }$

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

Una variante relativamente poco común permite "sin 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 los ejemplos de máquinas de Turing ):

• ${\displaystyle Q=\{{\mbox{A}},{\mbox{B}},{\mbox{C}},{\mbox{HALT}}\}}$(estados);
• ${\displaystyle \Gamma =\{0,1\}}$(cinte los símbolos del alfabeto);
• ${\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 =}$consulte la tabla de estados a continuación (función de transición).

Inicialmente, todas las celdas de la cinta 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 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 una forma infalible de leer y escribir símbolos 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 cinta, 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 que se extiende infinitamente en uno o ambos extremos y que está precargada con espacios en blanco excepto en el otro. Fragmento finito dado explícitamente en el que se encuentra el cabezal de la cinta. (Esto, por supuesto, no se puede implementar en la práctica.) La longitud de la cinta no se puede fijar, 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 era proporcional al tamaño de entrada, o una máquina de estados finitos si tenía una longitud estrictamente 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 claros, pero esto siempre se hace de tal manera que la máquina resultante tenga el mismo poder 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 cinta en lugar de moverse hacia la izquierda o hacia 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. 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 , símbolo de impresión S _k /borrar E /ninguno N , mover_tape_one_square 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 , símbolo de impresión S _k /borrar E /ninguno N , mover_tape_one_square 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 sólo las tres primeras 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 "imprimir símbolo S _k " o "borrar" (cf. nota al pie 12 en Post (1947), The Undecidable , p. 300). Las abreviaturas son de Turing ( El indecidible , p. 119). Posteriormente al 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 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 menos frecuencia se encuentra el uso de 4-tuplas: éstas representan una mayor atomización de las instrucciones de Turing (cf. Post (1947), Boolos & Jeffrey (1974, 1999), Davis-Sigal-Weyuker (1994)); Vea 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 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/designador de la instrucción actual que debe realizarse, 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 el "estado de progreso" de la máquina (o de la persona) a través del cálculo: 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 avance del cálculo en cualquier etapa está completamente determinado por la nota de las 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 consta de los símbolos de la cinta seguidos de Δ (que se supone que no aparece en ningún otro lugar) y luego de la nota de instrucciones. Esta expresión se llama "fórmula estatal".

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

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); a 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 el símbolo de "configuración m" q ₄ sobre el cuadrado escaneado aproximadamente en el centro de los 6 no. -Cuadrados en blanco en la cinta (consulte la figura de la cinta de Turing en este artículo) y los coloca 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, el valor instantáneo. La descripción es la combinación de símbolos que no están en blanco a la izquierda, el estado de la máquina, el símbolo actual escaneado por el cabezal 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 "ejecutar" en la siguiente figura):

1 un 1

Esto significa: después de tres movimientos, la cinta tiene... 000110000..., el cabezal escanea 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, 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 describe: 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. colocado 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 observado y discutido esta confusión.

Diagramas de "estado"

"La máquina de Turing del "castor ocupado 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 ), seguida de una barra / , seguida de los "comportamientos" posteriores. de la máquina, por ejemplo " P imprimir " y luego mover la cinta " R hacia la derecha ". No existe ningún formato generalmente aceptado. La convención que se muestra es posterior a McClusky (1965), Booth (1967), Hill y Peterson (1974).

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

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 (por ejemplo, máquinas con estados de "reinicio" y máquinas con patrones repetitivos (cf. Hill y Peterson p. 244 y siguientes)) pueden verse 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 del cálculo del castor ocupado comienza en la parte superior y continúa hacia abajo.

Se debe advertir nuevamente al lector que tales 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 ocupada máquina castora "se ejecuta" 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álculo" muestra el progreso del "estado" (instrucción) del castor ocupado de tres estados a través de su cálculo de principio a fin. En el extremo derecho está la "configuración completa" de Turing (la "situación" de Kleene, la "descripción instantánea" de Hopcroft-Ullman) en cada paso. Si la máquina se detuviera y se borrara para dejar en blanco tanto el "registro de estado" como la cinta completa, estas "configuraciones" podrían usarse para reavivar un cálculo en cualquier parte de su progreso (cf. Turing (1936) The Undecidable , págs. 139– 140).

Modelos equivalentes

Se puede demostrar que muchas máquinas que se podría pensar que tienen más capacidad computacional que una simple máquina universal de Turing no tienen más potencia (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 calcular con más potencia (es decir, más funciones matemáticas). (La tesis de Church-Turing plantea la hipótesis de que esto es cierto para cualquier tipo de máquina: que 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 empuje de pila única (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 utiliza 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, tener la misma potencia de cálculo que el modelo de máquina de Turing.

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

Las máquinas de Turing de solo lectura y que se mueven hacia la derecha son equivalentes a las DFA (así como a las NFA mediante conversión utilizando el algoritmo de conversión de NDFA a DFA ).

Con fines prácticos y didácticos, la máquina de registro equivalente se puede utilizar como lenguaje de programación ensamblador habitual .

Una pregunta relevante es si el modelo de cálculo representado por lenguajes de programación concretos es 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í 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) implican una memoria de espacio finito. Esto se debe a que el tamaño de los tipos de datos de referencia de la 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. En principio, es simplemente Turing completo, ya que se permite que la asignación de memoria en un lenguaje de programación falle, lo que significa que el lenguaje de programación puede ser Turing completo al ignorar las asignaciones de memoria fallidas, pero los programas compilados ejecutables en una computadora real no pueden.

Elección de máquinas C, máquinas O de Oracle

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

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

—  Lo indecidible , p. 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. Él "supone que las opciones son 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 _n = 0 o 1), y por tanto el número 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... +i _n determina completamente la demostración. La máquina automática realiza sucesivamente la prueba 1, la prueba 2, la prueba 3,..." (Nota a pie de página ‡, Lo indecidible , p. 138)

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

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, 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), The Undecidable , p. 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 agregada):

Es posible inventar una sola máquina que pueda usarse para calcular cualquier secuencia computable. Si a esta máquina U se le suministra la cinta al principio de la cual está escrita la cadena de quíntuplos separados por punto y coma de alguna máquina informática M , entonces U calculará la misma secuencia que M.

Este hallazgo hoy se da por sentado, pero en su momento (1936) se consideró sorprendente. ^{[ cita necesaria ]} Algunos (cf. Davis (2000)) consideran que el modelo de computación que Turing llamó su "máquina universal" (" U " para abreviar) fue el avance teórico fundamental que condujo a la noción de almacenamiento . -programa de computadora .

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 de Turing universal de múltiples cintas sólo necesita ser más lenta por un factor logarítmico en comparación con las máquinas que simula. Este resultado fue obtenido en 1966 por FC Hennie y RE Stearns . (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

A menudo se cree ^{[ ¿según quién? ]} 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 un programa real pueda realizar. Lo que se pasa por alto en esta afirmación es que, debido a que una máquina real sólo 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 formas de explicar por qué las máquinas de Turing son modelos útiles de computadoras reales:

• Todo lo que una computadora real puede calcular, también lo puede calcular una máquina de Turing. Por ejemplo: "Una máquina de Turing puede simular cualquier tipo de subrutina que se encuentra en los lenguajes de programación, incluidos los procedimientos recursivos y cualquiera de los mecanismos conocidos de paso de parámetros" (Hopcroft y Ullman p. 157). Una FSA lo suficientemente grande también puede modelar cualquier computadora real, sin tener en cuenta IO. Por tanto, una afirmación sobre las limitaciones de las máquinas de Turing también se aplicará a las computadoras reales.
• La diferencia radica únicamente en la capacidad de una máquina de Turing para manipular una cantidad ilimitada de datos. Sin embargo, 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 (DFA) equivalente en una máquina real determinada tiene cuatrillones. Esto hace que la representación DFA 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 informáticas convencionales .
• Las máquinas de Turing simplifican el enunciado de algoritmos. ^{[ dudoso ]} Los algoritmos que se ejecutan en máquinas abstractas equivalentes a Turing suelen ser más generales que sus homólogos que se ejecutan en máquinas reales, porque tienen tipos de datos de precisión arbitraria disponibles y nunca tienen que lidiar con condiciones inesperadas (incluyendo, 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 una disposición particular. Por ejemplo, las computadoras modernas con programas almacenados son en realidad instancias de una forma más específica de máquina abstracta conocida como máquina de programas almacenados de acceso aleatorio o modelo de máquina RASP. Al igual que la máquina universal de Turing, el 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: "células" de memoria que pueden contener cualquier número entero (cf. Elgot y Robinson (1964), Hartmanis (1971), y en particular Cook -Rechow (1973); referencias en 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 utilizar como dirección para especificar otro registro); por lo tanto, el "programa" del RASP puede abordar 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, lo que no es posible en una máquina de Turing general; por lo tanto, cuando las máquinas de Turing se utilizan como base para limitar los tiempos de ejecución, se puede demostrar un "falso límite inferior" en los tiempos de ejecución de ciertos algoritmos (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 máquina de Turing.

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 determinados. La teoría de la computabilidad, que estudia la computabilidad de 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 cómo ocurre realmente la interacción; por lo tanto, al describir la interactividad, normalmente se prefieren alternativas como los autómatas de E/S .

Comparación con el modelo aritmético de computación.

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

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

• El algoritmo euclidiano se ejecuta en tiempo polinomial en el modelo de Turing, pero no en el modelo aritmético.
• El algoritmo que lee n números y luego los calcula elevando al cuadrado repetidamente se ejecuta en tiempo polinomial 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 polinómico en el modelo aritmético y, además, la longitud binaria de todos los números involucrados es polinómica en la longitud de la entrada, entonces siempre es tiempo polinómico en el modelo de Turing. Se dice que un algoritmo de este tipo se ejecuta en un tiempo fuertemente polinomial .

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" hasta Charles Babbage (alrededor de 1834) y, de hecho, propone la "tesis de Babbage". :

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

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

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

1. Las funciones aritméticas +, −, ×, donde − indica una resta "adecuada": x − y = 0 si y ≥ x .
2. Cualquier secuencia de operaciones es una operación.
3. Iteración de una operación (repitiendo n veces una operación P).
4. Iteración condicional (repitiendo n veces una operación P condicionada 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 por Turing ". (pág. 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á en programar una secuencia iterable fija de operaciones aritméticas. No se reconoce la importancia fundamental de la iteración condicional y la transferencia condicional para una teoría general de las máquinas calculadoras...

—Gandy  pág. 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úmero 10 había estado flotando durante casi 30 años antes de que se formulara con precisión. La expresión original de Hilbert para el número 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 integrales racionales: Idear un proceso según el cual se pueda determinar en un número finito de operaciones si la ecuación es solucionable 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 alemán, en Dershowitz y Gurevich, 2008

En 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] 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 determinada afirmación puramente lógica...

—Gandy  pág. 57, citando a Behmann

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

—  ibídem.

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

—  ibídem. , pag. 92

En el congreso internacional de matemáticos de 1928, Hilbert "hizo sus preguntas bastante precisas. En primer lugar, ¿estaban completas las matemáticas ... En segundo lugar, eran las matemáticas consistentes ... Y en tercer lugar, ¿eran las matemáticas 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 jubilación (para disgusto de Hilbert); el tercero, 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 tal definición no existía. Pero durante los siguientes 6 a 7 años, Emil Post desarrolló su definición de trabajador que se movía de una habitación a otra escribiendo y borrando marcas siguiendo una lista de instrucciones (Post 1936), al igual que Church y sus dos estudiantes Stephen Kleene y JB Rosser mediante el uso de El cálculo lambda de Church y la teoría de la recursividad 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 esbozó 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 fue más directa y proporcionó 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 demostrado nada.

La máquina A de Alan Turing

En la primavera de 1935, Turing, siendo un joven estudiante de maestría en el King's College de Cambridge , aceptó el desafío; lo habían estimulado las conferencias del lógico MHA Newman "y de ellas aprendió 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 devolvió la respuesta característica: "Algo que puede ser hecho por una máquina" y se embarcó en la muy agradable tarea de analizar la noción general de una máquina informática.

—Gandy  , pág. 74

Gandy afirma que:

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

—  ibídem. , pag. 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 por las máquinas durante toda su vida: "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 preguntándose qué significaba llamar 'mecánica' a una máquina de escribir". (Hodges pág. 96). Mientras estaba en Princeton realizando 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 afirmó anteriormente que "una función es efectivamente calculable si sus valores pueden encontrarse mediante algún proceso puramente mecánico". Podemos tomar esta afirmación literalmente, entendiendo por proceso puramente mecánico aquel que podría ser realizado 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 función computable y a la identificación de computabilidad con 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. 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 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). Fue el asesor doctoral de Turing, Alonzo Church , quien más tarde acuñó el término "máquina de Turing" en una reseña. ^[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 puede continuar con su tarea computacional)?
• ¿Existe una máquina que pueda determinar si alguna máquina arbitraria en su cinta imprime alguna vez un símbolo determinado? ^{[25] [26]}

Así, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo demostrar las 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, finalmente se convirtió en coresponsable de descifrar los códigos secretos alemanes creados por máquinas de cifrado llamadas "El Enigma"; También participó en el diseño del ACE ( Automatic Computing Engine ), "la propuesta ACE [de Turing] era efectivamente autónoma y sus raíces no estaban en el EDVAC [la iniciativa de EE. UU.], 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 la Tesis de Turing . Pero lo que Turing demostró con su modelo de máquina computacional aparece en su artículo " Sobre números computables, con una aplicación al problema de Entscheidungs " (1937):

[que] el problema de Hilbert Entscheidungs ​​no puede tener solución... Por lo tanto, propongo 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, suministrado con cualquiera de estas fórmulas, eventualmente dirá si U es demostrable.

—  Del artículo de Turing reimpreso en The Undecidable , p. 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 "informática"

En 1937, mientras estaba en Princeton trabajando en su tesis doctoral, 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 al principio Turing pudo haber sentido curiosidad y experimentación, en Alemania ( Konrad Zuse (1938)) y en Estados Unidos ( Howard Aiken ) y George Stibitz (1937) se estaban realizando trabajos bastante serios en la misma dirección; los frutos de su trabajo fueron utilizados tanto por los ejércitos del Eje como por los Aliados en la Segunda Guerra Mundial (cf. Hodges, págs. 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 (precursora de la máquina Post-Turing de Martin Davis ); Al mismo tiempo, los investigadores europeos estaban reduciendo la novedosa computadora electrónica a un objeto teórico similar a una computadora equivalente a lo que ahora se llamaba una "máquina de Turing". A finales de los años cincuenta y principios de los sesenta, los desarrollos casualmente 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 una versión más amigable, parecida a una computadora. modelo abstracto llamado máquina contadora ; Elgot y Robinson (1964), Hartmanis (1971), Cook y Reckhow (1973) llevaron este trabajo aún más lejos con la máquina de registro y los modelos de 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 padre, 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 quiera 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 del análisis de algoritmos este papel lo asume el modelo RAM.

—  van Emde Boas 1990:16

Ver también

• Jerarquía aritmética
• Limitado por Bekenstein , que muestra la imposibilidad de máquinas de Turing de cinta infinita de tamaño finito y energía limitada.
• BlooP y FlooP
• La constante de Chaitin o Omega (informática) para obtener información sobre el problema de la detención
• habitación china
• El juego de la vida de Conway , un autómata celular completo de Turing
• infinito digital
• La nueva mente del emperador
• Enumerador (en informática teórica)
• genetix
• Gödel, Escher, Bach: An Eternal Golden Braid , un famoso libro que analiza, entre otros temas, la tesis de Church-Turing.
• Problema de detención , para más referencias.
• Arquitectura de Harvard
• Programación imperativa
• La hormiga de Langton y las turmitas , simples análogos bidimensionales de la máquina de Turing
• Lista de cosas que llevan el nombre de Alan Turing
• Arquitectura de Harvard modificada
• Máquina cuántica de Turing
• Claude Shannon , otro destacado pensador de la teoría de la información
• Ejemplos de máquinas de Turing
• interruptor de turing
• Turing tarpit , cualquier sistema o lenguaje informático que, a pesar de ser Turing completo, generalmente se considera inútil para la informática práctica.
• Máquina no organizada , para las primeras ideas de Turing sobre redes neuronales.
• Arquitectura 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 "Esta" máquina "es un modelo matemático abstracto", también cf. 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 refiere a un "tipo específico de máquina idealizada".
3. Sipser 2006:137 "Una máquina de Turing puede hacer todo lo que puede hacer una computadora real".
4. Cfr. Sipser 2002:137. Además, Rogers 1987 (1967):13 describe "una cinta de papel de longitud infinita en ambas direcciones". Minsky 1967:118 afirma que "la cinta se considera infinita en ambas direcciones". Boolos Burgess y Jeffrey 2002:25 incluyen la posibilidad de que "hay alguien estacionado en cada extremo para agregar cuadrados en blanco adicionales según sea necesario".
5. Cfr. 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 ilustran la máquina moviéndose 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 cambiarla!"; él "prefiere pensar que la cinta representa 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 todo su entrada desde este entorno. Algunas variaciones del modelo de 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). Prensa de la Universidad de Princeton . ISBN 978-0-691-15564-7.
8. La idea se le ocurrió a mediados de 1935 (quizás, vea 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 lo expresó Newman, un" proceso mecánico "que podría aplicarse a un enunciado matemático, y que arrojaría la respuesta sobre 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 nota a pie de página en Davis 2000:151.
10. ver nota previa a Las obras completas de Alonzo Church ( Burge, Tyler; Enderton, Herbert, eds. (23 de abril de 2019). Las obras completas de Alonzo Church. Cambridge, MA, EE. UU.: MIT Press. ISBN 978-0-262-02564-5.)
11. Turing 1936 en Lo indecidible 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 Entscheidungsproblem ". Actas de la Sociedad Matemática de Londres . Serie 2. 42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712.— Reimpresión en: Turing, Alan. "Sobre números computables, con aplicación al Entscheidungsproblem". El archivo digital de Turing . Consultado el 9 de julio de 2020 .^{[ enlace muerto permanente ]}
13. Turing 1936 en Lo indecidible 1965:145
14. Sipser 2006:137 observa que "Una máquina de Turing puede hacer todo lo que puede hacer una computadora real. Sin embargo, ni siquiera una máquina de Turing 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. Consulte la definición de "entradas" en Wikcionario .
16. AM Turing (julio de 1948). Maquinaria inteligente (Reporte). Laboratorio Nacional de Física.Aquí: p.3-4
17. Ocasionalmente se denomina tabla de acciones o función de transición .
18. Generalmente se quintuplica [5-tuplas]: q _i a _j →q _i1 a _j1 d _k , pero a veces se cuadriplica [4-tuplas].
19. página 149; en particular, Hopcroft y Ullman suponen que no está definido en todos los estados de ${\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, señor  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 la relación entre conjuntos recursivamente enumerables y conjuntos diofánticos finalmente queda al descubierto.
24. ver nota previa a Las obras completas de Alonzo Church ( Burge, Tyler; Enderton, Herbert, eds. (23 de abril de 2019). Las obras completas de Alonzo Church. Cambridge, MA, EE. UU.: MIT Press. ISBN 978-0-262-02564-5.)
25. Turing 1936 en Lo indecidible 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 Entscheidungsproblem ". Actas de la Sociedad Matemática de Londres . Serie 2. 42 (1): 230–265. doi :10.1112/plms/s2-42.1.230. S2CID  73712.— Reimpresión en: Turing, Alan. "Sobre números computables, con aplicación al Entscheidungsproblem". El archivo digital de Turing . Consultado el 9 de julio de 2020 .^{[ enlace muerto permanente ]}
27. Turing 1936 en Lo indecidible 1965:145

Referencias

Literatura primaria, reimpresiones y compilaciones.

• B. Jack Copeland ed. (2004), The Essential Turing: escritos fundamentales sobre informática, lógica, filosofía, inteligencia artificial y vida artificial más Los secretos del enigma, Clarendon Press (Oxford University Press), Oxford Reino Unido, ISBN 0-19-825079-7 . Contiene los artículos de Turing más un borrador de carta a Emil Post sobre su crítica de la "convención de Turing" y las correcciones de Donald W. Davies a la máquina de computación universal de Turing. 
• 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 , págs. 289 y siguientes.
• Emil Post (1947), "Insolubilidad recursiva de un problema de Thue", Journal of Symbolic Logic , vol. 12, págs. 1-11. Reimpreso en Lo indecidible , págs. 293 y siguientes. En el Apéndice de este artículo, publique comentarios y correcciones al artículo de Turing de 1936-1937. En particular, véanse las notas a pie de página 11 con correcciones a la codificación de la máquina informática universal y la nota a pie de página 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 Entscheidungs". Actas de la Sociedad Matemática de Londres . 2 (publicado en 1937). 42 : 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 Entscheidungsproblem: una corrección". Actas de la Sociedad Matemática de Londres . 2 (publicado en 1937). 43 (6): 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 "Cibernética: artículos clave". 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". Filosofía Matemática . 4 (3): 256–260. doi : 10.1093/philmat/4.3.256 .
• FC Hennie y RE Stearns . Simulación en 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; Juan Burgess; Richard Jeffrey (2002). Computabilidad y Lógica (4ª ed.). Cambridge Reino Unido: Cambridge University Press. ISBN 0-521-00758-5.Burgess ha reescrito significativamente 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 registro ) y funciones recursivas , mostrando su equivalencia.
• Taylor L. Booth (1967), Teoría de máquinas secuenciales y autómatas , John Wiley and Sons, Inc., Nueva York. Texto de ingeniería a nivel de posgrado; abarca una amplia variedad de temas, el Capítulo IX Máquinas de Turing incluye algo de teoría de la recursividad.
• Martín Davis (1958). Computabilidad e insolubilidad . McGraw-Hill Book Company, Inc, Nueva York.. En las páginas 12 a 20, ofrece 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 de identidad y varias funciones de identidad, y la multiplicación.
• Davis, Martín; Ron Sigal; Elaine J. Weyuker (1994). Computabilidad, complejidad y lenguajes y lógica: fundamentos de la informática teórica (2ª ed.). San Diego: Prensa académica, Harcourt, Brace & Company. ISBN 0-12-206382-1.
• Hennie, Fredrick (1977). Introducción a la Computabilidad . Addison – Wesley, Reading, Massachusetts QA248.5H4 1977.. En las páginas 90 a 103, Hennie analiza el UTM con ejemplos y diagramas de flujo, pero sin un "código" real.
• Hopcroft, John ; Ullman, Jeffrey (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Addison – Wesley, Masa de lectura. ISBN 0-201-02988-X.Centrado en cuestiones de interpretación automática de "lenguajes", integridad de NP, etc.
• Hopcroft, John E.; Rajeev Motwani; Jeffrey D. Ullman (2001). Introducción a la teoría, los lenguajes y la computación de los autómatas (2ª ed.). Misa de lectura: 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 impresión (con correcciones de la sexta reimpresión de 1971). Texto de nivel de posgrado; la mayor parte del Capítulo XIII Funciones computables se basa en pruebas de computabilidad de funciones recursivas de 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, Massachusetts: Addison – Wesley Publishing Company.. Con referencia al papel de las máquinas de Turing en el desarrollo de la computación (tanto hardware como software), consulte 1.4.5 Historia y bibliografía, págs. 225 y siguientes, y 2.6 Historia y bibliografía, págs. 456 y siguientes.
• Zohar Manna , 1974, Teoría matemática de la computación . Reimpreso, Dover, 2003. ISBN 978-0-486-43238-0 
• Marvin Minsky , Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc., Nueva Jersey, 1967. Consulte el Capítulo 8, Sección 8.2 "Insolubilidad del problema de la detención".
• Christos Papadimitriou (1993). Complejidad computacional (1ª ed.). Addison Wesley. ISBN 0-201-53082-1.Capítulo 2: Máquinas de Turing, págs. 19–56.
• Hartley Rogers, Jr. , Teoría de funciones recursivas y computabilidad efectiva , The MIT Press, Cambridge MA, edición de bolsillo de 1987, edición original de McGraw-Hill de 1967, ISBN 0-262-68052-1 (pbk.) 
• Michael Sipser (1997). Introducción a la Teoría de la Computación. Publicación PWS. ISBN 0-534-94728-X.Capítulo 3: La tesis de Church-Turing, págs. 125-149.
• Piedra, Harold S. (1972). Introducción a la organización informática y las estructuras de datos (1ª ed.). Nueva York: McGraw-Hill Book Company. ISBN 0-07-061726-0.
• Peter van Emde Boas 1990, Machine Models and Simulators , págs. 3–66, en Jan van Leeuwen , ed., Handbook of Theoretical Computer Science, Volumen A: Algoritmos y complejidad , The MIT Press/Elsevier, [¿lugar?], ISBN 0-444-88071-2 (Volumen A). QA76.H279 1990. 

La tesis de la iglesia

• Nachum Dershowitz; Yuri Gurevich (septiembre de 2008). "Una axiomatización natural de la computabilidad y prueba de la tesis de Church" (PDF) . Boletín de Lógica Simbólica . 14 (3) . Consultado el 15 de octubre de 2008 .
• Roger Penrose (1990) [1989]. La nueva mente del emperador (2ª ed.). Oxford University Press, Nueva York. ISBN 0-19-851973-7.

Pequeñas máquinas de Turing

• Rogozhin, Yurii, 1998, "A Universal Turing Machine with 22 States and 2 Symbols", Revista rumana de ciencia y tecnología de la información , 1(3), 259–265, 1998. (estudia resultados conocidos sobre pequeñas máquinas universales de Turing)
• Stephen Wolfram , 2002, Un nuevo tipo de ciencia, Wolfram Media, ISBN 1-57955-008-8 
• Brunfiel, Geoff, Estudiante obtiene premio de matemáticas, Nature , 24 de octubre de 2007.
• Jim Giles (2007), La 'computadora universal' más simple gana 25.000 dólares para estudiantes, New Scientist, 24 de octubre de 2007.
• Alex Smith, Universalidad de la máquina de Turing 2, 3 de Wolfram, Presentación para el premio de investigación de la máquina de Turing Wolfram 2, 3.
• Vaughan Pratt, 2007, "Máquinas de Turing simples, universalidad, codificaciones, etc.", lista de correo electrónico de FOM. 29 de octubre de 2007.
• Martin Davis, 2007, "La máquina universal más pequeña" y Definición de la lista de correo electrónico FOM de la máquina de Turing universal. 26 y 27 de octubre de 2007.
• Alasdair Urquhart, 2007 "La máquina universal más pequeña", lista de correo electrónico de FOM. 26 de octubre de 2007.
• Héctor Zenil (Wolfram Research), 2007 "máquina universal más pequeña", lista de correo electrónico de FOM. 29 de octubre de 2007.
• Todd Rowland, 2007, "Confusion on FOM", foro de mensajes de Wolfram Science, 30 de octubre de 2007.
• Olivier y Marc RAYNAUD, 2014, Un prototipo programable para lograr máquinas de Turing Archivado el 14 de enero de 2016 en Wayback Machine "Laboratorio LIMOS de la Universidad Blaise Pascal (Clermont-Ferrand en Francia).

Otro

• Martín Davis (2000). Motores de lógica: los matemáticos y el origen de la computadora (1ª ed.). WW Norton & Company, Nueva York. ISBN 978-0-393-32229-3.
• Robin Gandy , "La confluencia de ideas en 1936", págs. 51-102 en Rolf Herken, ver más abajo.
• Stephen Hawking (editor), 2005, Dios creó los números enteros: los avances matemáticos que cambiaron la historia , Running Press, Filadelfia, ISBN 978-0-7624-1922-7 . Incluye el artículo de Turing de 1936-1937, con un breve comentario y una biografía de Turing escrita por Hawking. 
• Rolf Herken (1995). La máquina universal de Turing: un estudio de medio siglo . Springer Verlag. ISBN 978-3-211-82637-9.
• Andrew Hodges , Alan Turing: El Enigma , Simon and Schuster , Nueva York. Cf. Capítulo "El Espíritu de la Verdad" para una historia que conduce a su prueba y una discusión sobre ella.
• Ivars Peterson (1988). El turista matemático: instantáneas de las matemáticas modernas (1ª ed.). WH Freeman and Company, Nueva York. ISBN 978-0-7167-2064-5.
• Roger Penrose , La nueva mente del emperador: sobre las computadoras, las mentes y las leyes de la física , Oxford University Press , Oxford y Nueva York, 1989 (correcciones de 1990), ISBN 0-19-851973-7 . 
• Paul Strathern (1997). Turing y la computadora: la gran idea. Libros ancla/Doubleday. ISBN 978-0-385-49243-0.
• Hao Wang , "Una variante de la teoría de las máquinas informáticas de Turing", Revista de la Asociación de Maquinaria de Computación (JACM) 4, 63–92 (1957).
• Charles Petzold , El Turing anotado, John Wiley & Sons, Inc., ISBN 0-470-22905-5 
• Arora, Sanjeev; Barak, Boaz, "Teoría de la complejidad: un enfoque moderno", Cambridge University Press, 2009, ISBN 978-0-521-42426-4 , sección 1.4, "Máquinas como cuerdas y la máquina universal de Turing" y 1.7, "Demostración del teorema 1,9" 
• Kantorovitz, Isaiah Pinchas (1 de diciembre de 2005). "Una nota sobre la computabilidad de la máquina de Turing de sistemas controlados por reglas". Noticias SIGACT . 36 (4): 109–110. doi :10.1145/1107523.1107525. S2CID  31117713.
• Kirner, Raimund; Zimmermann, Lobo; Richter, Dirk: "Sobre los resultados de indecidibilidad de los lenguajes de programación reales", en 15. Kolloquium Programmiersprachen und Grundlagen der Programmierung (KPS'09), Maria Taferl, Austria, octubre de 2009.

enlaces externos

• "Máquina de Turing", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Máquina de Turing - Enciclopedia de Filosofía de Stanford
• Redes Causales de la Máquina de Turing por Enrique Zeleny como parte del Proyecto de Demostraciones Wolfram .
• Máquinas de Turing en Curlie