máquina de Turing

Modelo matemático de computación que define una máquina abstracta

Para otros usos, consulte la máquina de Turing (desambiguación) .

Máquinas de Turing
Máquina
Equivalentes de la máquina de Turing Ejemplos de máquinas de Turing Galería de la máquina de Turing
Variantes
Máquina de Turing alternante Máquina de Turing neuronal Máquina de Turing no determinista Máquina cuántica de Turing Máquina post-Turing Máquina probabilística de Turing Máquina de Turing de solo lectura Máquinas de Turing en movimiento a la derecha de solo lectura Máquina de Turing de cintas múltiples Máquina de Turing multipista Máquina de Turing simétrica Máquina de Turing total Máquina de Turing inequívoca Máquina de Turing universal Máquina zeno
Ciencias
Alan Turing Categoría: máquina de Turing
v t mi

Clases de autómatas

(Al hacer clic en cada capa se obtiene un artículo sobre ese tema)

Una máquina de Turing es un modelo matemático de cálculo que define 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, dado cualquier algoritmo informático , se puede construir una máquina de Turing capaz de simular la lógica de ese algoritmo. ^[3]

La máquina funciona con una cinta de memoria infinita ^[4] dividida en "celdas" discretas . ^[5] La máquina coloca su "cabeza" sobre una celda y "lee" o "escanea" ^[6] el símbolo allí. Luego, basándose en el símbolo y el propio estado presente de la máquina en una "tabla finita" ^[7] de instrucciones especificadas por el usuario, la máquina (i) escribe un símbolo (por ejemplo, un dígito o una letra de un alfabeto finito) en el celda (algunos modelos permiten borrar el símbolo o no escribir), ^[8] luego (ii) mueve la cinta una celda hacia la izquierda o hacia la derecha (algunos modelos no permiten movimiento, algunos modelos mueven la cabeza), ^[9]luego (iii) basándose en el símbolo observado y el propio estado de la máquina en la tabla, procede a otra instrucción o detiene el cálculo. ^[10]

La máquina de Turing fue inventada en 1936 por Alan Turing , ^{[11] [12]} quien la llamó una "máquina a" (máquina automática). ^[13] Con este modelo, Turing pudo responder dos preguntas negativamente: (1) ¿Existe una máquina que pueda determinar si cualquier máquina arbitraria en su cinta es "circular" (p. Ej., Se congela o no continúa con su tarea)? De manera similar, (2) ¿existe una máquina que pueda determinar si alguna máquina arbitraria en su cinta alguna vez imprime un símbolo dado? ^{[14] [15]} Así, al proporcionar una descripción matemática de un dispositivo muy simple capaz de realizar cálculos arbitrarios, pudo demostrar las propiedades de la computación en general, y en particular, la incomputabilidaddel Entscheidungsproblem ('problema de decisión'). ^[dieciséis]

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

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

Resumen

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

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

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

Una máquina de Turing que puede simular cualquier otra máquina de Turing se denomina máquina de Turing universal (UTM, o simplemente máquina universal). Alonzo Church introdujo una definición más orientada matemáticamente con una naturaleza "universal" similar , cuyo trabajo sobre el cálculo lambda se entrelazó con el de Turing en una teoría formal de la computación conocida como la tesis de Church-Turing . La tesis establece que las máquinas de Turing de hecho capturan la noción informal de métodos efectivos en lógica y matemáticas , y proporcionan una definición precisa de un algoritmo o "procedimiento mecánico". Estudiando sus propiedades abstractasproporciona muchos conocimientos sobre la informática y la teoría de la complejidad .

Descripción física

En su ensayo de 1948, "Maquinaria inteligente", Turing escribió que su máquina consistía en:

... una capacidad de memoria ilimitada obtenida en forma de una cinta infinita marcada en cuadrados, en cada uno de los cuales se podí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 de 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. Por lo tanto, cualquier símbolo en la cinta puede eventualmente tener una entrada. ^[18]

-  Turing 1948, pág. 3 ^[19]

Descripción

Para ver las visualizaciones de las máquinas de Turing, consulte la galería de máquinas de Turing .

La máquina de Turing modela matemáticamente una máquina que opera mecánicamente en una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, utilizando un cabezal de cinta. La operación está totalmente determinada por un conjunto finito de instrucciones elementales como "en el estado 42, si el símbolo visto es 0, escriba un 1; si el símbolo visto es 1, cambie al estado 17; en el estado 17, si el símbolo visto es 0, escriba un 1 y cambie al estado 6; " etc. En el artículo original (" Sobre números computables, con una aplicación al problema de Entscheidung ", ver también las referencias a continuación ), Turing no imagina un mecanismo, sino una persona a la que llama la "computadora", que ejecuta estas reglas mecánicas deterministas servilmente (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 de Kleene (1952) p. 375.)

Aquí, el estado interno (q ₁ ) se muestra dentro de la cabeza, y la ilustración describe la cinta como infinita y precargada con "0", el símbolo que sirve como blanco. El estado completo del sistema (su "configuración completa") consiste en el estado interno, cualquier símbolo 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 de 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 especial en blanco (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, la cabeza se mueve y la cinta está estacionaria.
• Un registro estatal que almacena el estado de la máquina de Turing, uno de los finitos. Entre estos 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 normalmente se encontraría una persona que realiza cálculos.
• Una tabla finita ^[20] de instrucciones ^[21] 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 (símbolo actualmente debajo de la cabeza), 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 por 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. 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 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 una entrada en la tabla para la combinación actual de símbolo y estado, la máquina se detendrá; otros modelos requieren que se llenen todas las entradas.

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

Definición formal

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

• ${\displaystyle Q}$es un conjunto de estados finito, no vacío ;
• ${\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 se permite aparecer en la cinta con una frecuencia infinita 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_{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, la máquina se detiene; ^[22] intuitivamente, la función de transición especifica el siguiente estado transitado desde el estado actual, qué símbolo sobrescribe 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 progresa verticalmente desde la parte superior hasta el estado HALT en la parte inferior.

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

Una variante relativamente poco común no permite "ningún cambio", 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\}}$ (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 =}$ consulte la tabla de estados a continuación (función de transición).

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

Tabla de estados para castor ocupado de 3 estados y 2 símbolos

Símbolo de cinta	Estado actual A			Estado actual B			Estado actual C
	Símbolo de escritura	Mueva la cinta	Siguiente estado	Símbolo de escritura	Mueva la cinta	Siguiente estado	Símbolo de escritura	Mueva la cinta	Siguiente estado
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	DETENER

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 se verán sus cálculos".

Por ejemplo,

• Habrá que tomar muchas decisiones sobre el aspecto real de los símbolos y una forma infalible de leer y escribir los símbolos de forma indefinida.
• Las operaciones de desplazamiento a la izquierda y desplazamiento a la derecha pueden desplazar el cabezal de la cinta a través de la cinta, pero cuando en realidad 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 (que es lo más cercano a la definición matemática), pero es más común pensar que se estira infinitamente en uno o ambos extremos y que se llena previamente con espacios en blanco excepto en el dado explícitamente un fragmento finito en el que está el cabezal de la cinta. (Esto, por supuesto, no es implementable en la práctica). La longitud de la cinta no puede ser 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 acotado lineal si la cinta era proporcional al tamaño de entrada, o máquina de estado finito si era estrictamente de longitud fija.

Definiciones alternativas

Las definiciones en la literatura a veces difieren ligeramente, para facilitar o aclarar los argumentos o las pruebas, 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 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" por una de las 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 _yo , 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 , move_tape_one_square left L / right R / none N , new state 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 _yo , 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_un_cuadrado izquierdo L / derecho R / ninguno N )

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

Ejemplo: tabla de estado para el castor ocupado de 3 estados y 2 símbolos reducida a 5 tuplas

Estado actual	Símbolo escaneado		Símbolo de impresión	Mueva la cinta	Estado final (es decir, siguiente)	5 tuplas
A	0		1	R	B	( A , 0, 1, R, B )
A	1		1	L	C	( A , 1, 1, L, C )
B	0		1	L	A	( B , 0, 1, L, A )
B	1		1	R	B	( B , 1, 1, R, B )
C	0		1	L	B	( C , 0, 1, L, B )
C	1		1	norte	H	( C , 1, 1, N, H )

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

	Configuración m actual (estado de Turing)	Símbolo de cinta	Operación de impresión	Movimiento de cinta	Configuración m final (estado de Turing)	5 tuplas	Comentarios de 5 tuplas	4 tuplas
N1	q yo	S j	Imprimir (S k )	Izquierda L	q m	(q yo , S j , S k , L, q m )	"en blanco" = S 0 , 1 = S 1 , etc.
N2	q yo	S j	Imprimir (S k )	Derecha R	q m	(q yo , S j , S k , R, q m )	"en blanco" = S 0 , 1 = S 1 , etc.
N3	q yo	S j	Imprimir (S k )	Ninguno N	q m	(q yo , S j , S k , N, q m )	"en blanco" = S 0 , 1 = S 1 , etc.	(q yo , S j , S k , q m )
4	q yo	S j	Ninguno N	Izquierda L	q m	(q yo , S j , N, L, q m )		(q yo , S j , L, q m )
5	q yo	S j	Ninguno N	Derecha R	q m	(q yo , S j , N, R, q m )		(q yo , S j , R, q m )
6	q yo	S j	Ninguno N	Ninguno N	q m	(q yo , S j , N, N, q m )	"Salto" directo	(q yo , S j , N, q m )
7	q yo	S j	Borrar	Izquierda L	q m	(q yo , S j , E, L, q m )
8	q yo	S j	Borrar	Derecha R	q m	(q yo , S j , E, R, q m )
9	q yo	S j	Borrar	Ninguno N	q m	(q yo , S j , E, N, q m )		(q yo , S j , E, q m )

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 de no impresión o "N" (4, 5, 6). Para ver ejemplos, consulte los ejemplos de máquinas de Turing .

Con menos frecuencia se encuentra 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)); también vea más en Post-Turing machine .

El "estado"

La palabra "estado" usada 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 / designador de la instrucción actual que se ejecutará, es decir, el contenido del registro de estado. 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 en la cinta:

Así, 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 sola expresión (secuencia de símbolos) que consta de los símbolos en la cinta seguidos de Δ (que suponemos que no aparece en ningún otro lugar) y luego por la nota de instrucciones. Esta expresión se llama "fórmula de estado".

-  The Undecidable , págs. 139–140, énfasis agregado

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 " ( 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 en aproximadamente el centro de los 6 no -Cuadros en blanco en la cinta (vea la figura de la cinta de Turing en este artículo) y lo coloca a la derecha del cuadrado escaneado. Pero Kleene se refiere a "q ₄ " en sí mismo como "el estado de la máquina" (Kleene, p. 374-375). Hopcroft y Ullman llaman a este compuesto la "descripción instantánea" y siguen la convención de Turing de poner el "estado actual" (etiqueta-instrucción, configuración-m) a la izquierda del símbolo escaneado (p. 149), es decir, la descripción instantánea es la combinación de los 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 del castor ocupado de 3 estados y 2 símbolos después de 3 "movimientos" (tomado del ejemplo "ejecutar" en la figura siguiente):

1 A 1

Esto significa que: después de tres movimientos de la cinta tiene ... 000 110 000 ... en él, la cabeza está explorando más a la derecha 1, y el Estado es una . 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 la cabeza está escaneando el 0 ( "blank") a su izquierda y el estado es B .

"Estado" en el contexto de las máquinas de Turing debe aclararse en cuanto a cuál se describe: ( i ) la instrucción actual, o ( ii ) la lista de símbolos en la cinta junto con la instrucción actual, o ( iii ) la lista de símbolos en la cinta junto con la instrucción actual colocada a la izquierda del símbolo escaneado oa la derecha del símbolo escaneado.

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

Diagramas de "estado" de la máquina de Turing

La tabla para el castor ocupado de 3 estados ("P" = imprimir / escribir un "1")

Símbolo de cinta	Estado actual A			Estado actual B			Estado actual C
	Símbolo de escritura	Mueva la cinta	Siguiente estado	Símbolo de escritura	Mueva la cinta	Siguiente estado	Símbolo de escritura	Mueva la cinta	Siguiente estado
0	PAG	R	B	PAG	L	A	PAG	L	B
1	PAG	L	C	PAG	R	B	PAG	R	DETENER

La máquina de Turing del "castor ocupado de 3 estados" en una representación de estado finito . 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 con una flecha. La etiqueta (por ejemplo, 0 / P, R ) cerca del estado de salida (en la "cola" de la flecha) especifica el símbolo escaneado que causa una transición particular (por ejemplo, 0 ) seguido de una barra / , seguido de los "comportamientos" subsiguientes de la máquina, por ejemplo, " P P rint", luego mueva la cinta " R R ight". No existe un formato general aceptado. La convención que se muestra es después de 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 de tabla (Booth, p. 74). Sin embargo, ciertos conceptos, por ejemplo, máquinas con estados de "reinicio" y máquinas con patrones repetidos (véase Hill y Peterson, pág. 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 mesa para el contexto particular. Consulte la máquina de estados finitos para obtener más información.

La evolución del cálculo del castor ocupado comienza en la parte superior y continúa hasta la parte inferior.

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 máquina de castor ocupada "funciona" siempre seguirá la misma trayectoria de estado, esto no es cierto para la máquina de "copia" que se puede proporcionar con "parámetros" de entrada variable.

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 ("situación" de Kleene, "descripción instantánea" de Hopcroft-Ullman) en cada paso. Si la máquina fuera detenida y despejada 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 lugar de su progreso (cf. Turing (1936) The Undecidable , págs. 139– 140).

Modelos equivalentes al modelo de la máquina de Turing

Ver también: equivalentes máquina de Turing , Registro de máquina y máquina de Post-Turing

Se puede demostrar que muchas máquinas de las 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ág. 159, cf. Minsky (1967)). Quizás computen más rápido o usen menos memoria, o su conjunto de instrucciones puede ser más pequeño, pero no pueden computar con más potencia (es decir, más funciones matemáticas). (Recuerde que la tesis de Church-Turing plantea la hipótesis de que esto es cierto para cualquier tipo de máquina: cualquier máquina de Turing puede calcular cualquier cosa que pueda "calcularse").

Una máquina de Turing es equivalente a un autómata de empuje hacia abajo de una sola pila (PDA) que se ha hecho más flexible y conciso al relajar el requisito de último en entrar , primero en salir de su pila. Además, una máquina de Turing también es equivalente a una PDA de dos pilas con semántica estándar de último en entrar, primero en salir , utilizando 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 la misma potencia computacional que el modelo de la 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) en contraposición a la máquina de Turing determinista (DTM) para la cual la tabla de acción tiene en la mayoría de una entrada para cada combinación de símbolo y estado.

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

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

Una pregunta interesante 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í mismos no tienen necesariamente esta limitación. Kirner et al., 2009 han demostrado que entre los lenguajes de programación de propósito general algunos son Turing completos y otros no. Por ejemplo, ANSI C no es equivalente a Turing, ya que todas las instancias de ANSI C (diferentes instancias son posibles ya que el estándar deja deliberadamente cierto comportamiento indefinido 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 idioma. Sin embargo, otros lenguajes de programación como Pascal no tienen esta característica, lo que les permite ser Turing completo en principio. En principio, es simplemente Turing completo, ya que la asignación de memoria en un lenguaje de programación puede fallar, lo que significa que el lenguaje de programación puede ser Turing completo cuando se ignoran asignaciones de memoria fallidas, pero los programas compilados ejecutables en una computadora real no pueden.

Elección de c-machines, oracle o-machines

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á solo parcialmente determinado 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 alguna elección arbitraria. Este sería el caso si utilizáramos máquinas para tratar 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 usar una máquina a para "encontrar todas las fórmulas demostrables del cálculo [de Hilbert]" en lugar de usar una máquina de elección. Él "supone [s] que las opciones están siempre entre dos posibilidades 0 y 1. Cada demostración estará determinada por una secuencia de opciones i ₁ , i ₂ , ..., i _n (i ₁ = 0 o 1, i ₂ = 0 o 1, ..., i _n = 0 o 1), y de ahí el número 2 ⁿ + i ₁ 2 ^n-1 + i ₂ 2 ^n-2 + ... + i _ndetermina completamente la prueba. La máquina automática realiza sucesivamente la prueba 1, la prueba 2, la prueba 3, ... "(Nota al pie ‡, Lo indecidible , p. 138)

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

Una máquina oráculo u o-máquina es una máquina-a de Turing que pausa su cálculo en el estado " o " mientras que, para completar su cálculo, "espera la decisión" de "el oráculo", una entidad no especificada, además de decir que no puede ser una máquina "(Turing (1939), The Undecidable , p. 166-168).

Máquinas universales de Turing

Artículo principal: máquina de Turing universal

Una implementación de una máquina de Turing

Como escribió Turing en The Undecidable , p. 128 (cursiva agregada):

Es posible inventar una sola máquina que se puede utilizar para calcular cualquier secuencia computable. Si esta máquina U se suministra con la cinta en el principio de que se escribe la cadena de quintuplica separados por punto y coma de algunos máquina de computación M , entonces U calculará la misma secuencia que M .

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

El 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 cintas múltiples solo 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

A menudo se dice ^{[¿ por 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 pueda realizar un programa real. 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 , esta "máquina real" no es en realidad más que una máquina de estados finitos . Por otro lado, las máquinas de Turing son equivalentes a las máquinas que tienen una cantidad ilimitada de espacio de almacenamiento para sus cálculos.

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

1. Cualquier cosa que pueda calcular una computadora real, también puede hacerlo una máquina de Turing. 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 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 la E / S. Por lo tanto, una declaración sobre las limitaciones de las máquinas de Turing también se aplicará a las computadoras reales.
2. La diferencia radica solo 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) solo puede manipular una cantidad finita de datos.
3. 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.
4. 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 algunos cientos de estados, mientras que el autómata finito determinista equivalente (DFA) en una máquina real dada tiene cuatrillones. Esto hace que la representación DFA no sea factible de analizar.
5. 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 en 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 convencional de las máquinas informáticas.
6. Las máquinas de Turing simplifican la formulación de algoritmos. Los algoritmos que se ejecutan en máquinas abstractas equivalentes a Turing suelen ser más generales que sus contrapartes 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 (que incluyen, entre otras, quedarse sin memoria ) .

Un prototipo experimental de una máquina de Turing.

Limitaciones de las máquinas de Turing

Teoría de la complejidad computacional

Más información: Teoría de la complejidad computacional

Una limitación de las máquinas de Turing es que no modelan bien los puntos fuertes de una disposición en 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 máquina de programa almacenado de acceso aleatorio o modelo de máquina RASP. Como 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 de Turing universal, el 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 máquina de acceso aleatorio). La máquina de estados finitos de 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 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 basándose en los índices de memoria, que no son posibles en una máquina de Turing general; por lo tanto, cuando las máquinas de Turing se utilizan como base para limitar los tiempos de ejecución, se puede probar un "límite inferior falso" 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 usa el modelo de cálculo RASP en lugar del modelo de la máquina de Turing.

Simultaneidad

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado . ( Abril de 2015 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

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

Interacción

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

Desde la década de 1970, el uso interactivo de computadoras se volvió mucho más común. En principio, es posible modelar esto haciendo que un agente externo lea de 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, generalmente se prefieren alternativas como los autómatas de E / S.

Historia

Ver también: Algoritmo y tesis de Church-Turing

Fueron descritos en 1936 por Alan Turing .

Antecedentes históricos: maquinaria computacional

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

Que todo el desarrollo y las operaciones de análisis ahora pueden ser ejecutadas por maquinaria .

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

Análisis de de Babbage de Gandy máquina analítica describe los siguientes cinco operaciones (cf. p 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 las que son computables por Turing ". (pág.53). Cita otras propuestas de "máquinas de cálculo universales", incluidas las de Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken ( 1937). Sin emabargo:

… 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. 55

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

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

10. Determinación de la solubilidad de una ecuación diofántica . Dada una ecuación diofántica con cualquier número de cantidades desconocidas 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 se puede resolver 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 por un número finito de operaciones su validez o satisfacibilidad ... El Entscheidungsproblem debe ser considerado 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 " 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 de aplicación general bastante definida que permita a uno 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 comenta que ... el problema general es equivalente al problema de decidir qué proposiciones matemáticas son verdaderas.

-  ibíd.

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

-  ibíd. , pag. 92

En el congreso internacional de matemáticos de 1928, Hilbert "hizo sus preguntas bastante precisas. Primero, las matemáticas estaban 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 jubilación (para disgusto de Hilbert); el tercero, el problema de la Entscheidung, tuvo que esperar hasta mediados de la década de 1930.

El problema era que una respuesta requería primero una definición precisa de " prescripción aplicable general definida ", que el profesor de Princeton Alonzo Church llegaría a llamar " calculabilidad efectiva ", y en 1928 no existía tal definición. Pero durante los siguientes 6 a 7 años, Emil Post desarrolló su definición de un trabajador que se mueve de una habitación a otra escribiendo y borrando marcas según una lista de instrucciones (Post 1936), al igual que Church y sus dos estudiantes Stephen Kleene y JB Rosser mediante el uso de Cálculo lambda de Church y teoría de la recursividad de Gödel(1934). El artículo de Church (publicado el 15 de abril de 1936) mostró que el problema de la Entscheidung era de hecho "indecidible" y le ganó a Turing 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 arbitraba el artículo de Turing, Turing tuvo tiempo de estudiar el artículo de Church 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 había hecho Church 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 desde 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, cuando era un joven estudiante de maestría en el King's College de Cambridge , Reino Unido , aceptó el desafío; había sido estimulado por las conferencias del lógico MHA Newman "y aprendió de ellas el trabajo de Gödel y el problema de Entscheidung ... Newman usó la palabra 'mecánico' ... En su obituario de Turing 1955 Newman escribe:

A la pregunta "¿qué es un proceso" mecánico "? Turing devolvió la respuesta característica "Algo que una máquina puede hacer" y se embarcó en la muy agradable tarea de analizar la noción general de una máquina de computación.

-  Gandy, pág. 74

Gandy afirma que:

Supongo, pero no sé, que Turing, desde el comienzo de su obra, tenía como objetivo una prueba de la indecidibilidad del problema de la Entscheidung. Me dijo que la "idea principal" del artículo se le ocurrió cuando estaba tendido 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 comprensión de que había una máquina universal. , y por tanto un argumento diagonal para probar la insolubilidad.

-  ibíd. , pag. 76

Si bien Gandy cree que la declaración de Newman anterior es "engañosa", esta opinión no es compartida por todos. Turing tuvo un interés de toda la vida en las máquinas: "Alan había soñado con inventar máquinas de escribir cuando era niño; [su madre] la Sra. Turing tenía una máquina de escribir; y bien podría haber comenzado preguntándose qué significaba llamar '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 dijo anteriormente que "una función es efectivamente calculable si sus valores se pueden encontrar mediante algún proceso puramente mecánico". Podemos tomar esta afirmación literalmente, entendiendo por un proceso puramente mecánico uno 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 lleva a la definición del autor de una 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 The Undecidable , p. 160

Cuando Turing regresó al Reino Unido, finalmente se convirtió en responsable conjunto de romper los códigos secretos alemanes creados por máquinas de cifrado llamadas "El Enigma"; también se involucró en el diseño del ACE ( Motor de Computación Automática ), "la propuesta ACE [de Turing] era efectivamente autónoma, y ​​sus raíces no se encontraban en la EDVAC [la iniciativa de los 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 ha sido nombrado por Kleene (1952) Turing's Thesis . 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 Entscheidung " (1937):

[que] el problema de Hilbert Entscheidung no puede tener solución ... Propongo, por lo tanto, mostrar que no puede haber un proceso general para determinar si una fórmula U dada del cálculo funcional K es demostrable, es decir, que no puede haber una 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 va a pedir 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, haciendo sus propios relés electromecánicos (Hodges p. 138). "La tarea de Alan era incorporar el diseño lógico de una máquina de Turing en una red de interruptores operados por relés ..." (Hodges p. 138). Si bien Turing pudo haber sido inicialmente curioso y experimentado, en Alemania ( Konrad Zuse (1938)) y en los Estados Unidos ( Howard Aiken ) y George Stibitz (1937) se estaba realizando un trabajo bastante serio en la misma dirección ; los frutos de su trabajo fueron utilizados tanto por el Eje como por los ejércitos aliados en la Segunda Guerra Mundial (cf. Hodges p. 298-299). A principios y mediados de la década de 1950, Hao Wang yMarvin Minsky redujo la máquina de Turing a una forma más simple (precursora de la máquina de Post-Turing de Martin Davis ); simultáneamente, los investigadores europeos estaban reduciendo la nueva computadora electrónica a un objeto teórico similar a una computadora equivalente a lo que ahora se llama una "máquina de Turing". A finales 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 lejos y redujeron la máquina de Turing a una forma más amigable, similar a una computadora. modelo abstracto llamado máquina contador ; Elgot y Robinson (1964), Hartmanis (1971), Cook y Reckhow (1973) llevaron este trabajo aún más lejos con laregistrar modelos de máquinas y máquinas de acceso aleatorio, pero básicamente todas son máquinas de Turing de varias cintas con un conjunto de instrucciones de tipo aritmético.

1970-presente: la máquina de Turing 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, continúan siendo los modelos elegidos por los teóricos que investigan cuestiones en 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 Turing de múltiples cintas fuera de línea ..., que representa el modelo estándar para el cálculo orientado a cadenas, y la máquina de acceso aleatorio (RAM) presentada por Cook y Reckhow ..., que modela la computadora idealizada de estilo Von Neumann.

-  van Emde Boas 1990: 4

Solo en el área relacionada de análisis de algoritmos, esta función es asumida por el modelo RAM.

-  van Emde Boas 1990: 16

Ver también

• Jerarquía aritmética
• Encuadernado 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
• Castor ocupado
• La constante de Chaitin u Omega (ciencias de la computación) 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 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 trata, 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 los 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 probabilística de Turing
• Máquina de Turing de acceso aleatorio
• Máquina cuántica de Turing
• Claude Shannon , otro pensador destacado en teoría de la información
• Ejemplos de máquinas de Turing
• Interruptor de turing
• Turing tarpit , cualquier sistema informático o lenguaje que, a pesar de ser Turing completo, generalmente se considera inútil para la informática práctica.
• Máquina desorganizada , 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 "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. Cf. Sipser 2002: 137. Además, Rogers 1987 (1967): 13 describe "una cinta de papel de longitud infinita en ambas direcciones". Minsky 1967: 118 dice "La cinta se considera infinita en ambas direcciones". Boolos Burgess y Jeffrey 2002: 25 incluyen la posibilidad de "hay alguien apostado en cada extremo para agregar casillas 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. Esta palabra es utilizada por, por ejemplo, Davis 2000: 151
7. Esta tabla representa un algoritmo o "procedimiento computacional efectivo" que es necesariamente finito; véase Penrose 1989: 30 y siguientes, Stone 1972: 3 y siguientes.
8. Boolos Burgess y Jeffrey 2002: 25
9. 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 observando que "¡podría ser difícil cambiar!"; é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 imaginar las cosas" y luego sugiere que "el dispositivo recibe todo su entrada de este entorno.
10. "También por convención, uno de los estados se distingue como el estado de detención y se le da el nombre de HALT" (Stone 1972: 9). La descripción original de Turing no incluía una instrucción HALT pero sí permitía una condición "circular", una "configuración desde la cual no hay movimiento posible" (ver Turing 1936 en The Undecidable 1967: 119); esta noción se añadió en la década de 1950; ver más en Detener el problema .
11. Hodges, Andrew (2012). Alan Turing: The Enigma (The Centenary ed.). Prensa de la Universidad de Princeton . ISBN 978-0-691-15564-7.
12. La idea se le ocurrió a mediados de 1935 (quizás, 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 dijo Newman, un" proceso mecánico "que podría aplicarse a un enunciado matemático, y que daría la respuesta de si era demostrable "(Hodges 1983: 93). Turing presentó su artículo el 31 de mayo de 1936 a la London Mathematical Society para sus Actas (cf. Hodges 1983: 112), pero fue publicado a principios de 1937 y las separatas estaban disponibles en febrero de 1937 (cf. Hodges 1983: 129).
13. Ver nota a pie de página en Davis 2000: 151.
14. Turing, 1936 en The Undecidable 1965: 132-134; La definición de Turing de "circular" se encuentra en la página 119.
15. Turing, Alan Mathison (1937). "Sobre números computables, con una aplicación al problema Entscheidungs". Actas de la London Mathematical Society . Serie 2. 42 (1): 230–265. doi : 10.1112 / plms / s2-42.1.230 .- Reimpresión en: Turing, Alan. "Sobre números computables, con una aplicación al Entscheidungsproblem" . El archivo digital de Turing . Consultado el 9 de julio de 2020 .
16. Turing 1936 en The Undecidable 1965: 145
17. Sipser 2006: 137 observa que "Una máquina de Turing puede hacer todo lo que puede hacer una computadora real. 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".
18. Ver la definición de " entradas " en Wikcionario
19. AM Turing (julio de 1948). Maquinaria inteligente (Informe). Laboratorio Nacional de Física. Aquí: p.3-4
20. Ocasionalmente se denomina tabla de acciones o función de transición .
21. Generalmente se quintuplica [5-tuplas]: q _i a _j → q _i1 a _j1 d _k , pero a veces se cuadruplica [4-tuplas].
22. p.149; en particular, Hopcroft y Ullman asumen queno está definido en todos los estados de${\displaystyle \delta }$${\displaystyle F}$

Referencias

Este artículo tiene un estilo de cita poco claro . Las referencias utilizadas pueden aclararse con un estilo diferente o coherente de citas y notas al pie . ( Noviembre de 2019 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

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 artículos de Turing más un borrador de carta a Emil Post sobre su crítica a la "convención de Turing" y las correcciones de Donald W. Davies a la máquina de cómputo universal de Turing. 
• Martin Davis (ed.) (1965), The Undecidable , Raven Press, Hewlett, NY.
• 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), "Inestabilidad recursiva de un problema de Thue", Journal of Symbolic Logic , vol. 12, págs. 1-11. Reimpreso en The Undecidable , págs. 293 y siguientes. En el Apéndice de este artículo, Post comenta y da 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 de computación universal y la nota a pie de página 14 con comentarios sobre la primera y segunda prueba de Turing .
• Turing, AM (1936). "Sobre números computables, con una aplicación al problema Entscheidungs". Actas de la London Mathematical Society . 2 (publicado en 1937). 42 : 230-265. doi : 10.1112 / plms / s2-42.1.230 .(y Turing, AM (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correct". Proceedings of the London Mathematical Society . 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 "Cybernetics: Key Papers". Ed. CR Evans y ADJ Robertson. Baltimore: University Park Press, 1968. pág. 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 Turing de varias cintas . 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.Algunas partes han sido reescritas significativamente por Burgess. Presentación de las máquinas de Turing en el contexto de las "máquinas ábaco" de Lambek (cf. Máquina de registro ) y funciones recursivas , mostrando su equivalencia.
• Taylor L. Booth (1967), Máquinas secuenciales y teoría de los autómatas , 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 recursividad.
• Martin Davis (1958). Computabilidad e insolubilidad . McGraw-Hill Book Company, Inc, Nueva York.. En las páginas 12-20, da ejemplos de tablas de 5 tuplas para Suma, Función Sucesora, Resta (x ≥ y), Resta adecuada (0 si x <y), Función de identidad y varias funciones de identidad, y 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–103, Hennie analiza el UTM con ejemplos y diagramas de flujo, pero sin 'código' real.
• John Hopcroft y Jeffrey Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas (1ª ed.). Addison – Wesley, Reading Mass. ISBN 0-201-02988-X. Centrado en los problemas de interpretación automática de "lenguajes", NP-completitud, 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. Claramente diferente y menos intimidante que la primera edición.
• Stephen Kleene (1952), Introducción a las metamatemáticas , North-Holland Publishing Company, Amsterdam 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 trata sobre pruebas de máquina de Turing de computabilidad de funciones recursivas, 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.. Con referencia al papel de las máquinas de Turing en el desarrollo de la computación (tanto hardware como software), ver 1.4.5 Historia y Bibliografía págs. 225ff y 2.6 Historia y Bibliografía págs. 456ff.
• 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 "Inestabilidad del problema de detención". Excelente, es decir, relativamente legible, a veces divertido.
• 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 las funciones recursivas y computabilidad efectiva , The MIT Press, Cambridge MA, edición de bolsillo 1987, edición original de McGraw-Hill 1967, ISBN 0-262-68052-1 (pbk.) 
• Michael Sipser (1997). Introducción a la Teoría de la Computación . Publicación de PWS. ISBN 0-534-94728-X. Capítulo 3: La tesis de Church-Turing, págs. 125-149.
• Stone, 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 Simulations , págs. 3-66, en Jan van Leeuwen , ed., Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity , The MIT Press / Elsevier, [lugar?], ISBN 0-444-88071-2 (Volumen A). QA76.H279 1990. Encuesta valiosa, con 141 referencias. 

Tesis de Church

• Nachum Dershowitz; Yuri Gurevich (septiembre de 2008). "Una axiomatización natural de la computabilidad y la 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. (encuesta de resultados conocidos sobre pequeñas máquinas de Turing universales)
• Stephen Wolfram , 2002, Un nuevo tipo de ciencia , Wolfram Media, ISBN 1-57955-008-8 
• Brunfiel, Geoff, premio de matemáticas para estudiantes , Nature , 24 de octubre de 2007.
• Jim Giles (2007), La 'computadora universal' más simple gana $ 25,000 para estudiantes , New Scientist, 24 de octubre de 2007.
• Alex Smith, Universalidad de Wolfram's 2, 3 Turing Machine , Presentación para el premio Wolfram 2, 3 Turing Machine Research Prize.
• 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 universal de Turing . 26 al 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 " la 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 conseguir máquinas de Turing "Laboratorio LIMOS de la Universidad Blaise Pascal (Clermont-Ferrand en Francia).

Otro

• Martin Davis (2000). Motores de la 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 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: una encuesta de medio siglo . Springer Verlag. ISBN 978-3-211-82637-9.
• Andrew Hodges , Alan Turing: The Enigma , Simon and Schuster , Nueva York. Cf. Capítulo "El espíritu de la verdad" para una historia que conduzca y una discusión de su prueba.
• 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 , The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics , 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 . Anchor Books / 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 , Petzold, Charles, 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 , sección 1.4, "Máquinas como cuerdas y la máquina universal de Turing" y 1.7, "Prueba 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, Wolf; 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

Wikimedia Commons tiene medios relacionados con las máquinas de Turing .

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