Recentemente, eu estava tendo uma discussão sobre as Máquinas de Turing quando me perguntaram: "A Máquina de Turing é derivada de autômatos, ou é o contrário"?
Eu não sabia a resposta, é claro, mas estou curioso para descobrir. A máquina de Turing é basicamente uma versão um pouco mais sofisticada de um autômato push-down. A partir disso, eu assumiria que a Máquina de Turing era derivada de autômatos, no entanto, não tenho provas ou explicações definitivas. Eu posso estar completamente errado ... talvez eles tenham sido desenvolvidos isoladamente.
Por favor! Liberte essa mente das tangentes eternas do emaranhado.
fl.formal-languages
computability
automata-theory
turing-machines
ho.history-overview
Emmanuel M. Smith
fonte
fonte
Respostas:
Nem!
A melhor maneira de ver essa independência é ler os documentos originais .
O artigo de Turing de 1936, introduzindo máquinas de Turing, não se refere a nenhum tipo mais simples de autômato finito (abstrato).
O artigo de McCulloch e Pitts, de 1943, que introduzia "redes nervosas", os precursores das máquinas de estado finito dos dias atuais, as propôs como modelos simplificados de atividade neural, e não computação por si só.
Para uma interessante perspectiva inicial, consulte a pesquisa de 1953 de Claude Shannon , que tem uma seção inteira sobre máquinas de Turing, mas não diz nada sobre autômatos finitos, como os reconheceríamos hoje (embora ele cite o relatório de Kleene de 1951).
Os autômatos finitos modernos podem começar com um artigo de Kleene de 1956 , originalmente publicado como um relatório técnico da RAND em 1951, que definia expressões regulares. Kleene certamente estava ciente dos resultados de Turing, tendo publicado resultados semelhantes (na linguagem das funções recursivas primitivas) quase ao mesmo tempo. No entanto, a única referência de Kleene a Turing é uma explicação de que as máquinas de Turing não são autômatos finitos, por causa de suas fitas ilimitadas. É claro que é possível que o pensamento de Kleene tenha sido influenciado pela abstração de Turing, mas as definições de Kleene parecem (para mim) independentes.
No volume da pesquisa de 1956 editado por Shannon e McCarthy , no qual os artigos de Kleene sobre expansões regulares e de Moore sobre transdutores de estado finito foram finalmente publicados, autômatos finitos e máquinas de Turing foram discutidos lado a lado, mas quase completamente de forma independente. Moore também cita Turing, mas apenas em uma nota de rodapé afirmando que as máquinas de Turing não são autômatos finitos.
( Um artigo recente da Kline relata a história bastante tempestuosa deste volume e a conferência de Dartmouth associada, às vezes chamada de "berço da IA").
(Uma versão ainda mais antiga das redes neurais é encontrada no trabalho de Turing sobre "máquinas do tipo B", reimpresso no livro "The Turing essencial", de cerca de 1937, eu acho. Parece provável que muitas pessoas estavam brincando com a idéia no até o momento, como ainda hoje muitos graduandos de CS acham que o "inventaram" em algum momento de seus estudos antes de descobrir sua história.)
fonte
você menciona PDAs especificamente. note que uma máquina de Turing é equivalente a um PDA com duas pilhas. A lógica original dos PDAs parece estar intimamente relacionada ao desenvolvimento da "teoria da linguagem" ala chomsky.
ver, por exemplo, Análise sintática e a loja de empilhamento, "Procedimentos de simpósios em matemática aplicada (Vol. 12). Providence, RI: Sociedade Americana de Matemática, 1961
esta é uma das primeiras referências que vi por Oettinger, "Análise sintática automática e armazenamento de empilhamento" p104, não sei se existem referências anteriores ao PDA.
foram necessários muitos anos de estudo de todos os autômatos interelacionados para começar a conceber uma teoria unificadora (ainda em construção). os conceitos completos de Turing foram criados por volta do final dos anos 30, quando se observou que o cálculo lambda (desenvolvido independentemente pela Church) era equivalente às máquinas de Turing e a equivalência às máquinas Post foi mostrada na mesma época (embora esses três modelos tenham sido concebidos de alguma maneira independentemente e não imediatamente percebido como sendo equivalente a Turing em sua construção original).
novos modelos ainda estão sendo criados, por exemplo, o Cellular Automata tem uma história muito mais recente e demonstrou estar em vários sentidos, Turing completo.
parece justo dizer que a maioria dos que trabalham em ciência da computação estava familiarizada com o artigo de Turings seminal de 1936 e que influenciou muito todas as formulações posteriores de construções de autômatos (particularmente o conceito da tabela de transição de estado que parece ter sido introduzida por Turing)
fonte
Apenas para o inferno:
Maurice Wilkes. http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
fonte