Hace poco tuve una discusión sobre las máquinas de Turing cuando me preguntaron: "¿La máquina de Turing se deriva de autómatas o es al revés"?
No sabía la respuesta, por supuesto, pero tengo curiosidad por averiguarlo. La máquina de Turing es básicamente una versión un poco más sofisticada de un autómata push-down. A partir de eso, supondría que la máquina de Turing se deriva de autómatas, sin embargo, no tengo ninguna prueba o explicación definitiva. Podría estar simplemente equivocado ... tal vez se desarrollaron de forma aislada.
¡Por favor! Libera esta mente de tangentes eternas de enredo.
fl.formal-languages
computability
automata-theory
turing-machines
ho.history-overview
Emmanuel M. Smith
fuente
fuente
Respuestas:
¡Ninguno!
La mejor manera de ver esta independencia es leer los documentos originales .
El documento de Turing de 1936 que presenta las máquinas de Turing no se refiere a ningún tipo más simple de autómata finito (abstracto).
El artículo de McCulloch y Pitts de 1943 que introdujo las "redes nerviosas", los precursores de las máquinas modernas de estados finitos, los propuso como modelos simplificados de actividad neuronal, no como cómputo per se.
Para una perspectiva temprana interesante, vea la encuesta de 1953 de Claude Shannon , que tiene una sección completa sobre las máquinas de Turing, pero no dice nada sobre autómatas finitos como los reconoceríamos hoy (aunque cita el informe de 1951 de Kleene).
Podría decirse que los autómatas finitos modernos comienzan con un artículo de Kleene de 1956 , publicado originalmente como un informe técnico RAND en 1951, que definía expresiones regulares. Kleene ciertamente estaba al tanto de los resultados de Turing, ya que él mismo había publicado resultados similares (en el lenguaje de las funciones recursivas primitivas) casi al mismo tiempo. Sin embargo, la única referencia de Kleene a Turing es una explicación de que las máquinas de Turing no son autómatas finitos, debido a sus cintas ilimitadas. Por supuesto, es posible que el pensamiento de Kleene haya sido influenciado por la abstracción de Turing, pero las definiciones de Kleene parecen (para mí) ser independientes.
En el volumen de la encuesta de 1956 editado por Shannon y McCarthy , en el que tanto el artículo de Kleene sobre las expresiones regulares como el documento de Moore sobre los transductores de estado finito finalmente se publicaron, los autómatas finitos y las máquinas de Turing se discutieron uno al lado del otro, pero de manera casi completamente independiente. Moore también cita a Turing, pero solo en una nota al pie que indica que las máquinas de Turing no son autómatas finitos.
( Un artículo reciente de Kline relata la tormentosa historia de este volumen y la conferencia de Dartmouth asociada, a veces llamada el "lugar de nacimiento de la IA").
(Una versión aún más antigua de las redes neuronales se encuentra en el trabajo de Turing sobre "máquinas tipo B", como se reimprime en el libro "The esencial Turing", de alrededor de 1937, creo. Parece probable que muchas personas estuvieran jugando con la idea en el tiempo, como incluso hoy en día muchos estudiantes universitarios de CS piensan que lo han "inventado" en algún momento de sus estudios antes de descubrir su historia).
fuente
Usted menciona PDA específicamente. tenga en cuenta que una máquina de Turing es equivalente a una PDA con dos pilas. La justificación original de los PDA parece haber estado estrechamente relacionada con el desarrollo de la "teoría del lenguaje" ala chomsky.
véase, por ejemplo, Syntactic Analysis and the Pushdown Store, "Proceedings of Symposia in Applied Mathematics (Vol. 12). Providence, RI: American Mathematical Society, 1961
Esta es una de las primeras referencias que he visto por Oettinger, "Análisis sintáctico automático y la tienda pushdown" p104, no sé si hay referencias anteriores al PDA.
Tomó muchos años de estudio de todos los autómatas interrelacionados para comenzar a idear una teoría unificadora (aún en construcción). los conceptos completos de Turing se idearon a finales de los años 30 más o menos cuando se vio que el cálculo lambda (desarrollado independientemente por Church) era equivalente a las máquinas de Turing y la equivalencia a las máquinas de correos se mostró al mismo tiempo (aunque estos 3 modelos se idearon de alguna manera independientemente y no se dio cuenta de inmediato de ser equivalente a Turing en su construcción original).
todavía se están ideando nuevos modelos, por ejemplo, los autómatas celulares tienen una historia mucho más reciente y se ha demostrado que están completos en varios sentidos.
parece justo decir que la mayoría de los que trabajan en ciencias de la computación estaban familiarizados con el artículo seminal de Turings de 1936 y que influyó mucho en todas las formulaciones posteriores de construcciones de autómatas (particularmente el concepto de la tabla de transición de estado que parece haber sido introducido por Turing)
fuente
Sólo por el placer de hacerlo:
Maurice Wilkes. http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
fuente