Razones históricas para la adopción de Turing Machine como modelo primario de computación.

Tengo entendido que el modelo de Turing se ha convertido en el "estándar" al describir el cálculo. Me interesa saber por qué este es el caso, es decir, por qué el modelo TM se ha vuelto más utilizado que otros modelos teóricamente equivalentes (que yo sepa), por ejemplo, μ-Recursion de Kleene o el cálculo Lambda (entiendo que el primero no apareció hasta más tarde y el segundo no fue diseñado originalmente específicamente como un modelo de cómputo, pero muestra que las alternativas han existido desde el principio).

Todo lo que puedo pensar es que el modelo TM representa más de cerca las computadoras que tenemos que sus alternativas. ¿Es esta la única razón?

Esto parece ser cierto en el contexto de (algunas áreas de) la informática, pero no en general.

Una de las razones tiene que ver con la Tesis de la Iglesia. La razón principal es que algunos expertos como Godel no creían que los argumentos de que los modelos de computación anteriores / otros capturaran exactamente el concepto intuitivo de computación fueran convincentes. Hay varios argumentos, Church tenía algunos, pero no convencieron a Godel. Por otro lado, el análisis de Turing fue convincente para Godel, por lo que fue aceptado como el modelo para el cálculo efectivo. Las equivalencias entre los diferentes modelos se prueban más tarde (creo que Kleene).

$\lambda$$\mu$

$\mu$$\lambda$. También vea estos documentos de Viggo Stoltenberg-Hansen y John V. Tucker I , II .)

Algunos recursos para leer más:

Robert I. Soare tiene varios artículos sobre la historia de estos desarrollos, personalmente me gusta el del Manual de teoría de la computabilidad. puede encontrar más al consultar las referencias en ese documento.

Otro buen recurso es el artículo de computabilidad de Neil Immerman sobre SEP, ver también el artículo de Tesis de Church-Turing de B. Jack Copeland.

Las obras recopiladas de Godel contienen mucha información sobre sus puntos de vista. Especialmente las introducciones a sus artículos están extremadamente bien escritas.

" Metamathematics " de Kleene es un libro muy bonito.

Finalmente, si aún no está satisfecho, revise los archivos de la lista de correo de FOM , y si no puede encontrar una respuesta en el archivo, envíe un correo electrónico a la lista de correo.

Me gustaría debilitar la afirmación de que las TM son el modelo primario de cómputo, o al menos apuntan hacia otra dimensión de la pregunta. Claramente, los TM son dominantes en las partes más orientadas a la complejidad y al algoritmo de la informática, pero en la teoría y práctica del lenguaje de programación, no son particularmente dominantes. Hay varias razones para esto, pero quizás la más importante es que los TM o programas que se ejecutan en TM (a diferencia de, por ejemplo, cálculos lambda o cálculos de proceso) no se construyen de manera algebraica. Esto dificulta el desarrollo de teorías de tipos, que han sido el pilar de la teoría del lenguaje de programación.

Una de las cosas buenas de las máquinas de Turing es que trabajan en cadenas en lugar de números naturales o términos lambda, porque la entrada y la salida de muchos problemas pueden formularse naturalmente como cadenas. Sin embargo, no sé si esto cuenta como una razón "histórica".

Además del hecho de que las máquinas de Turing son un modelo convincente de cálculo con lápiz y papel (la "noción intuitiva de cálculo"), creo que poseen una serie de características que a menudo son útiles, especialmente cuando se prueban teoremas sobre ellas:

• son fáciles de describir formalmente y tienen una semántica operacional simple;
• es fácil dar una definición concreta de su complejidad de tiempo y espacio;
• Los modelos más realistas (y complejos) de computadoras electrónicas, como las máquinas de acceso aleatorio, pueden ser simulados por TM con una sobrecarga polinómica, y viceversa.

Fue el primero en tener impacto y, por lo tanto, se ha establecido, especialmente en la teoría de la complejidad. Esta es una razón débil, pero la gente trabaja de esa manera. Primero trabajamos en viejos problemas abiertos en lugar de declarar nuevos.