¿Importancia práctica de las máquinas de Turing?

27

Soy ingeniero eléctrico, y solo tuve un curso de CS en la universidad hace 26 años. Sin embargo, también soy un usuario devoto de Mathematica.

Tengo la sensación de que las máquinas de Turing son muy importantes en informática. ¿Es la importancia solo en la teoría de la informática? Si hay implicaciones / aplicaciones prácticas, ¿cuáles son algunas de ellas?

Ted Ersek
fuente

Respuestas:

21

La importancia de las máquinas de Turing es doble. Primero, las máquinas de Turing fueron uno de los primeros (si no el primero) modelos teóricos para computadoras, que datan de 1936. Segundo, se ha desarrollado mucha informática teórica teniendo en cuenta las máquinas de Turing, por lo que muchos de los resultados básicos son en el lenguaje de las máquinas de Turing. Una razón para esto es que las máquinas de Turing son simples y muy susceptibles de análisis.

Dicho esto, las máquinas de Turing no son un modelo práctico para la informática. Como ingeniero y usuario de Mathematica, no deberían preocuparte en absoluto. Incluso en la comunidad teórica de la informática, las máquinas RAM más realistas se utilizan en las áreas de algoritmos y estructuras de datos.

De hecho, desde el punto de vista de la teoría de la complejidad, las máquinas de Turing son polinomialmente equivalentes a muchos otros modelos de máquinas, por lo que las clases de complejidad como P y NP se pueden definir de manera equivalente en términos de estos modelos. (Otras clases de complejidad son más delicadas).

Yuval Filmus
fuente
11

Las máquinas de Turing fueron uno de los primeros modelos de computación, es decir, se desarrollaron cuando la computación en sí misma no se entendía muy bien (alrededor de 1940). Quiero centrarme en dos aspectos que (posiblemente) los llevaron a ser el modelo preferido en ese momento, lo que llevó a ser el modelo más establecido y, por lo tanto, finalmente estándar.

  1. Simplicidad de las pruebas
    Como modelo teórico, las máquinas de Turing tienen el encanto de ser "simples" en el sentido de que el estado actual de la máquina solo tiene un tamaño constante. Toda la información que necesita para determinar el siguiente estado de la máquina es un símbolo y un número de estado (de control). El cambio al estado de la máquina es igualmente pequeño, agregando solo el movimiento del cabezal de la máquina. Eso simplifica considerablemente las pruebas (formales), en particular el número de casos a distinguir.

    Compare este aspecto con el modelo RAM (cuando no se utiliza en su forma minimalista): la siguiente operación puede ser cualquiera de varias operaciones, que pueden acceder a cualquiera (dos) registros. También hay múltiples estructuras de control.

  2. Tiempo de ejecución y uso del espacio
    Hubo (solo) dos modelos principales de cómputo que surgieron casi simultáneamente con las Máquinas de Turing, a saber, cálculo de Church y las funciones recursivas Kleene . Respondieron la misma pregunta que hizo Turing, el problema Entscheidungs de Hilbert, pero se prestaron mucho menos fácilmente (si es que lo hicieron ) para definir el tiempo de ejecución y el uso del espacio. En cierto sentido, son demasiado abstractos para relacionarse así con modelos de máquina más realistas.λμ

    Sin embargo, para las máquinas de Turing, ambas nociones se definen fácilmente (y estaban en el primer artículo de Turing sobre su modelo, si no recuerdo mal). Dado que las consideraciones de eficiencia pronto fueron muy importantes para hacer cosas, esta era una clara ventaja de las máquinas Turing.

Por lo tanto, las máquinas de Turing se han establecido como el modelo de cálculo, que podría verse como una combinación de "accidente" histórico y algunas de sus propiedades clave. Sin embargo, muchos modelos se han definido desde entonces y se utilizan con avidez, en particular para superar las deficiencias de las máquinas Turing; por ejemplo, son tediosos para "programar" (es decir, definir).

No conozco ninguna aplicación directa en la práctica. En particular, la práctica de la computación evolucionó en paralelo a (y, al principio, en su mayoría independientemente de) la teoría de la computación. Los lenguajes de programación se desarrollaron sin modelos formales de máquina. Sin embargo, está claro (en retrospectiva) que muchos avances en la práctica de la computación fueron permitidos por la teoría.

Además, tenga en cuenta que el valor que un concepto teórico ha tenido para la práctica debe medirse considerando a todos los descendientes, es decir, el trabajo de seguimiento, los resultados y las nuevas ideas posibles gracias a ese concepto. Y en ese sentido, creo que es justo decir que el concepto de máquinas de Turing (entre otros) ha revolucionado el mundo.

Rafael
fuente
4

La única aplicación razonablemente práctica que se me ocurre (en el sentido de que realmente podría implementar una máquina de Turing) es demostrar que un lenguaje de algún tipo tiene suficiente poder.

Si está diseñando algún tipo de lenguaje de programación (o cualquier otra cosa que esté destinada a computar cosas), entonces es posible que desee asegurarse de que sea completo de Turing (es decir, capaz de computar cualquier cosa que sea computable) implementando una máquina de Turing en eso.

Por supuesto, también podría implementar cualquier otra cosa que sea completa de Turing (como C o lógica combinatoria), pero a veces una máquina de Turing es la opción más fácil.

Peter
fuente
-1

La máquina de Turing es un modelo matemático de computación. Sus beneficios son: -

1. Verifique la capacidad de determinación Si TM no puede resolver un problema en un tiempo contable, entonces no podría haber ningún algoritmo que pudiera resolver ese problema (es decir, el problema es indecidible).

Para un problema de decisión si su TM se detiene en tiempo contable para todas las entradas de longitud finita, entonces podemos decir que el problema podría resolverse mediante un algoritmo en tiempo contable.

2. Classify Problem TM ayuda a clasificar los problemas decidibles en clases de jerarquía polinómica.

Supongamos que encontramos que el problema es decidible. Entonces nuestro objetivo se convierte en cuán eficientemente podemos resolverlo. La eficiencia se calculó en número de pasos, espacio extra utilizado, longitud del código / tamaño del FSM.

3. Diseñar e implementar algoritmos para máquinas prácticas TM ayuda a propagar la idea del algoritmo en otras máquinas prácticas. Después de la verificación exitosa de los criterios 1,2 podemos usar nuestros dispositivos / computadoras prácticas para diseñar e implementar algoritmos.

Subhankar Ghosal
fuente
3
Las máquinas de Turing no le permiten "verificar la capacidad de decisión"; solo dan una definición de lo que es la capacidad de decisión. La clasificación de problemas es perfectamente posible utilizando otros modelos de computación, como las máquinas de acceso aleatorio. Los algoritmos que funcionan en las máquinas de Turing rara vez se adaptan a otros modelos de máquinas, ya que los algoritmos de las máquinas de Turing implican grandes cantidades de mezcla aleatoria que no ocurre en otros lugares.
David Richerby
TM da definición de decidablity. Correcto. Para verificar la decidabilidad, ¿no estamos tomando la ayuda de TM? "La clasificación de problemas es perfectamente posible utilizando otros modelos de computación". Correcto, pero también podemos hacerlo usando TM. Al implementar el algoritmo, debe estar seguro de la dureza de ese problema.
Subhankar Ghosal
-3

Las máquinas de Turing son un buen ejercicio mental con poco uso práctico. No hay daño en no tener uno. Todas las aplicaciones de una máquina de Turing son intuitivas o de religión porque no se pueden probar ni refutar.

Valery Gavrilov
fuente
2
"Todas las aplicaciones de una máquina de Turing son intuitivas o de religión [...]" Y, por lo tanto, todos los campos de la teoría de la computabilidad y la teoría de la complejidad fueron descartados en catorce palabras.
David Richerby
Estos no estaban destinados a descartar esas teorías. Todo lo que decía era que las aplicaciones de una máquina de Turing son obvias, pueden entenderse intuitivamente o requieren creencias sin pruebas.
Valery Gavrilov
"una cuestión de religión porque no pueden ser probados o refutados". ¿Um que? La interpretación más generosa de esto que puedo inventar es que te estás refiriendo a la tesis de Church-Turing, pero cada aplicación específica de esto se puede probar (simplemente realiza el tedioso trabajo de diseñar la máquina de Turing adecuada; o, simplemente escriba un algoritmo apropiado en su lenguaje de programación favorito y use la equivalencia habitual), y CT no es una aplicación, solo una forma de simplificar la exposición de pruebas (y si uno duda seriamente de su aplicación, siempre puede dar una formal prueba).
Noah Schweber
Además, no entiendo cómo "se puede entender intuitivamente" es un inconveniente. Todas las matemáticas pueden entenderse intuitivamente; ¿eso significa que las matemáticas son solo un ejercicio mental con poco uso práctico?
Noah Schweber