Je venais tout juste d'avoir une discussion sur les machines de Turing quand on m'a demandé: "La machine de Turing dérive-t-elle d'automates, ou est-ce l'inverse"?
Je ne connaissais pas la réponse bien sûr, mais je suis curieux de le savoir. La machine de Turing est fondamentalement une version légèrement plus sophistiquée d'un automate push-down. De cela, je suppose que la machine de Turing était dérivée d'automates, mais je n'ai aucune preuve ou explication définitive. Je me trompe peut-être tout simplement ... peut-être qu'ils ont été développés de manière isolée.
S'il vous plaît! Libérez cet esprit des tangentes éternelles de l'intrication.
fl.formal-languages
computability
automata-theory
turing-machines
ho.history-overview
Emmanuel M. Smith
la source
la source
Réponses:
Ni!
La meilleure façon de voir cette indépendance est de lire les articles originaux .
Le document de Turing de 1936 présentant les machines de Turing ne fait référence à aucun type plus simple d'automate fini (abstrait).
L'article de McCulloch et Pitts de 1943 présentant les «filets nerveux», les précurseurs des machines à états finis modernes, les proposait comme des modèles simplifiés de l'activité neuronale, et non du calcul en soi.
Pour une première perspective intéressante, voir l' enquête de 1953 de Claude Shannon , qui a une section entière sur les machines de Turing, mais ne dit rien sur les automates finis tels que nous les reconnaîtrions aujourd'hui (même s'il cite le rapport de Kleene de 1951).
Les automates finis modernes commencent sans doute par un article de Kleene de 1956 , initialement publié en tant que rapport technique RAND en 1951, qui définissait les expressions régulières. Kleene était certainement au courant des résultats de Turing, ayant publié lui- même des résultats similaires (dans le langage des fonctions récursives primitives) presque en même temps. Néanmoins, la seule référence de Kleene à Turing est une explication que les machines de Turing ne sont pas des automates finis, en raison de leurs bandes illimitées. Il est bien sûr possible que la pensée de Kleene ait été influencée par l'abstraction de Turing, mais les définitions de Kleene me semblent (indépendantes).
Dans le volume d'enquête de 1956 édité par Shannon et McCarthy , dans lequel à la fois l'article de Kleene sur les experssions régulières et l'article de Moore sur les transducteurs à états finis ont finalement été publiés, les automates finis et les machines de Turing ont été discutés côte à côte, mais presque complètement indépendamment. Moore cite également Turing, mais seulement dans une note de bas de page indiquant que les machines Turing ne sont pas des automates finis.
( Un article récent de Kline raconte l'histoire plutôt houleuse de ce volume et de la conférence de Dartmouth associée, parfois appelée le «lieu de naissance de l'IA».)
(Une version encore plus récente des réseaux de neurones se trouve dans les travaux de Turing sur les "machines de type B", comme réimprimé dans le livre "The essential Turing", vers 1937 je pense. Il semble probable que beaucoup de gens jouaient avec l'idée au temps, comme encore aujourd'hui de nombreux étudiants de premier cycle CS pensent qu'ils l'ont "inventé" à un moment donné de leurs études avant de découvrir son histoire.)
la source
vous mentionnez spécifiquement les PDA. notez qu'une machine de Turing est équivalente à un PDA avec deux piles. La justification originale des PDA semble avoir été étroitement liée au développement de la "théorie du langage" ala chomsky.
voir par exemple Syntactic Analysis and the Pushdown Store, "Proceedings of Symposia in Applied Mathematics (Vol. 12). Providence, RI: American Mathematical Society, 1961
il s'agit de l'une des premières références que j'ai vues par Oettinger, "Analyse syntaxique automatique et magasin déroulant" p104, je ne sais pas s'il existe des références antérieures au PDA.
il a fallu de nombreuses années d'étude de tous les automates entrelacés pour commencer à concevoir une théorie unificatrice (toujours en construction). les concepts complets de Turing ont été conçus vers la fin des années 30 environ quand on a vu que le calcul lambda (développé indépendamment par Church) était équivalent aux machines de Turing et que l'équivalence avec les machines à poste a été montrée à peu près au même moment (bien que ces 3 modèles aient été quelque peu conçus indépendamment et pas immédiatement réalisé comme étant équivalent de Turing sur leur construction d'origine).
de nouveaux modèles sont encore en cours d'élaboration, par exemple les automates cellulaires ont une histoire beaucoup plus récente et se sont avérés, à divers égards, achevés.
il semble juste de dire que la plupart des informaticiens connaissaient le papier de référence de Turings de 1936 et qu'il a fortement influencé toutes les formulations ultérieures de constructions d'automates (en particulier le concept de la table de transition d'état qui semble avoir été introduit par Turing)
la source
Juste pour l'enfer:
Maurice Wilkes. http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
la source