¿Por qué son máquinas de Turing el modelo preferido de cómputo?

Question

En la actualidad, el modelo más ampliamente enseñado de cómputo (al menos en el mundo de habla inglesa) es que de las máquinas de Turing, sin embargo, no era el primer Turing-completo modelo ahi: funciones μ-recurrentes llegaron unos años antes, y λ-cálculo llegó un año anteriormente. Por qué es que las máquinas de Turing son tan populares hoy. ¿Recurso intuitivo? ¿La profundidad o la notoriedad del trabajo de Turing? O es el modelo percibido como "natural" en algún sentido y si es así, ¿por qué?

Answer 1

Hay varias razones de la popularidad de las máquinas de Turing:

(1) máquinas de Turing encajar bien en un curso de teoría de autómatas: usted puede comenzar mediante la introducción de modelos más sencillos, como los autómatas finitos o pushdown autómatas y, a continuación, pasar a la Emt.

(2) La declaración de los más famosos problema abierto en la informática teórica, es decir, P = NP, y, más generalmente, la teoría de la complejidad Computacional depende en gran medida de la Emt.

(3) El concepto es bastante flexible y admite varias extensiones como la Alternancia de TMs, Probabilísticos, TMs, Quantum TMs, sólo para nombrar unos pocos.

Algunas personas también podrían ser tal vez fascinado por el Busy Beaver problema(ver Busy Beaver Partituras y las letras del Alfabeto Tamaño de los recientes resultados) y sus aplicaciones a Goldbach de la conjetura: hay un 47 estado, 2-símbolo, 1-cinta de máquina de Turing que detiene el iff Goldbach la conjetura es falsa.

Answer 2

Si usted lee Turing original de 1936 papel, verá cómo él trató de obtener en los ingredientes fundamentales de un ser humano después de algunos sistemático proceso de manipulación de símbolos. La palabra "efectiva" se usa algunas veces en este contexto: un cálculo o algoritmo es "eficaz" cuando un ser humano puede realizar. E. g división Larga es un algoritmo eficaz porque podemos hacerlo. De hecho, cuando estamos realizando una división larga, somos el 'equipo'. De hecho, en Turing del tiempo en que un 'equipo' era a menudo entendido como un ser humano de realizar algunos cálculos. El proyecto Manhattan, por ejemplo, utiliza muchos ordenadores humanos, y la reciente película Oculta Cifras mostraron que los humanos, los equipos empleados de la NASA en el momento del Proyecto Apollo.

Turing conceptual del camino que lo llevó a su "Máquinas de Turing" es en realidad bastante sencillo. Cualquier equipo de Turing dijo, manipula un montón de símbolos, que podemos pensar escritas en una hoja de papel. Ahora, mientras la informática, la computadora toma pasos discretos, donde cada paso que se da es que depende de en qué etapa o estado del proceso, y lo que los símbolos de la computadora ve en frente de ella.

Volviendo a la adición de números, por ejemplo, es posible que en algún momento nos encontramos en el 'estado' de tener que añadir dos dígitos, seguido por el 'estado' de tener que escribir el resultado, etc. Ahora, Turing dijo, mientras nuestro lenguaje natural, la descripción de estos estados pueden utilizar palabras como 'la adición de dos dígitos' o 'escribir el resultado", todo lo que es realmente importante es que el equipo es capaz de distinguir entre los diferentes estados. Es decir, para todos los que el equipo de cuidados, los diferentes estados en que simplemente podría ser numeradas $1$, $2$, $3$, etc. y todo lo que el equipo necesita saber para hacer su siguiente movimiento, es para saber si estamos en el estado $1$, $2$, o de cualquier otro estado no puede estar allí.

Una historia similar ocurre para los símbolos de Turing argumentó. Es decir, mientras estamos acostumbrados a la representación decimal de los números, se podría, por supuesto, el uso de cualquier otro tipo de esquema de representación. De nuevo, Turing argumentó que lo único que importa es que somos capaces de distinguir un símbolo de un símbolo diferente. O, un poco más técnico, si se utiliza un conjunto de símbolos $s_1$, $s_2$, $s_3$, etc. entonces, todo lo que debe importar a la computadora es que el equipo sea capaz de reconocer que algunos escritos símbolo es decir, el símbolo de $s_2$, más que cualquier de los otros símbolos. En resumen, el equipo simplemente se necesita tener un alfabeto de símbolos que el equipo es capaz de leer y escribir.

¿Cómo son los símbolos organizado? Turing escribe:

La informática se hace normalmente por escrito ciertos símbolos en el papel. Podemos suponer, este documento se divide en plazas como la de un niño en un libro de aritmética. En la escuela primaria aritmética de las 2 dimensiones de los caracteres de las de papel se utiliza a veces. Pero tal uso siempre es evitable, y creo que va a estar de acuerdo en que el carácter bidimensional de papel no esenciales de la computación. Supongo entonces que el cálculo se lleva a cabo en una dimensión de papel, en una cinta dividida en cuadrados.

Turing hace aquí el punto de que todo lo que se puede calcular utilizando una de dos dimensiones (o incluso de mayores dimensiones, como en el caso de utilizar varias hojas de papel) diseño de los símbolos, siempre podemos simular el uso de un uno-dimensional de diseño, ya que siempre puede "cadena", que reúne todas las líneas y convertirlo en una larga cadena de símbolos, posiblemente el uso de símbolos especiales para demarcar lo que normalmente sería de línea, página, u otros descansos.

También, ya que no es previsible cuánto 'scratch' el trabajo que uno tiene que hacer mientras se realiza el cálculo de Turing decidió que podemos pensar en tener una cinta con un infinito número de plazas, y que los símbolos pueden ser colocados en cada una de esas casillas. O, tal vez de manera más realista, que uno siempre tiene la capacidad de extender la cinta mediante la adición de plazas en cualquier dirección, de modo que uno está garantizado de cualquier cantidad de "espacio de trabajo", según sea necesario.

Cómo muchos estados y símbolos puede haber? Turing dijo que podía ser cualquier número, el tiempo es finito. Turing abogó por tanto para ser finito, diciendo que la mente humana y de la memoria humana es limitada. También, suponiendo un tamaño finito de las plazas en la cinta en la que colocar nuestros símbolos , sólo puede haber un número finito de símbolos diferentes, o bien las diferencias entre los símbolos sería venir infinitamente pequeño, y no seríamos capaces de reconocer y discriminar el símbolo de la siguiente:

También voy a suponer que el número de símbolos que puede ser impreso es finito. Si vamos a permitir una infinidad de símbolos, entonces no sería símbolos diferentes para una arbitrariamente pequeña medida.

Finalmente, como un equipo, se debe ser capaz de ir a cualquier lugar en esta larga cadena de símbolos. Pero para eso, Turing argumentado, todo lo que se requiere es una habilidad para ir ya sea a la izquierda o a la derecha una casilla relativa de un cuadrado es actualmente viendo: donde uno quiere ir, finalmente, uno debe ser capaz de llegar hasta allí. Por lo tanto, Turing se imaginaba que habría una "lectura/escritura" de la cabeza que en cualquier punto particular en el tiempo sería la 'a' algunos plaza particular, en la cinta, y que esta "cabeza" puede moverse a la izquierda o a la derecha, un cuadrado en un momento.

Y ahí lo tienen: todos los componentes que ahora llamamos una máquina de Turing!

Por otra parte, este mismo argumento es el que hace la Turing-Church Tesis plausible que cualquier cálculo se puede realizar utilizando Turing-computación.... por lo que es importante que los instructores que cubre Turing-máquinas deben relacionarse de Turing del análisis a los estudiantes, en lugar de inmediatamente partiendo de una definición de Turing-máquinas como por desgracia muchos de los instructores de hacer.