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.
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.
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.
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.
fuente