Czy koncepcja maszyny Turinga pochodzi od automatów?

Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”?

Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down. Zakładam, że Maszyna Turinga pochodzi od automatów, jednak nie mam ostatecznego dowodu ani wyjaśnienia. Mogę się po prostu pomylić… być może zostały opracowane w izolacji.

Proszę! Uwolnij ten umysł od wiecznych stycznych splątania.

Ani!

Najlepszym sposobem, aby zobaczyć tę niezależność, jest przeczytanie oryginalnych artykułów .

• Artykuł Turinga z 1936 r. Przedstawiający maszyny Turinga nie odnosi się do żadnego prostszego typu (abstrakcyjnego) automatu skończonego.

• Artykuł McCullocha i Pittsa z 1943 r., Wprowadzający „sieci nerwowe”, prekursory współczesnych maszyn o stanie skończonym, zaproponował je jako uproszczone modele aktywności neuronowej, a nie obliczenia per se.

Ciekawą wczesną perspektywą jest ankieta Claude'a Shannona z 1953 r. , Która zawiera całą sekcję na temat maszyn Turinga, ale nie mówi nic o automatach skończonych, jak moglibyśmy je dziś rozpoznać (chociaż przytacza raport Kleene z 1951 r.).

Nowoczesne automaty skończone prawdopodobnie zaczynają się od artykułu Kleene z 1956 r. , Pierwotnie opublikowanego jako raport techniczny RAND w 1951 r., Który definiuje wyrażenia regularne. Kleene z pewnością był świadomy wyników Turinga, sam sam opublikował podobne wyniki (w języku pierwotnych funkcji rekurencyjnych) prawie w tym samym czasie. Niemniej jednak jedyne odniesienie Kleene do Turinga jest wyjaśnieniem, że maszyny Turinga nie są automatami skończonymi z powodu ich nieograniczonych taśm. Oczywiście jest możliwe, że na myśl Kleene miała wpływ abstrakcja Turinga, ale definicje Kleene wydają się (dla mnie) niezależne.

W tomie z 1956 r. Pod redakcją Shannona i McCarthy'ego , w którym ostatecznie opublikowano zarówno artykuł Kleene na temat regularnych wypraw, jak i artykuł Moore'a na temat przetworników skończonych, automaty skończone i maszyny Turinga zostały omówione obok siebie, ale prawie całkowicie niezależnie. Moore cytuje również Turinga, ale tylko w przypisie stwierdzającym, że maszyny Turinga nie są automatami skończonymi.

( Niedawny artykuł Kline opowiada raczej o burzliwej historii tego tomu i związanej z nim konferencji w Dartmouth, zwanej czasem „miejscem narodzin AI”).

(Jeszcze wcześniejsza wersja sieci neuronowych znajduje się w pracy Turinga nad „maszynami typu B”, jak przedrukowano w książce „The Essential Turing” z około 1937 roku. Wydaje się prawdopodobne, że wiele osób bawiło się tym pomysłem na czasu, ponieważ nawet dzisiaj wielu studentów CS myśli, że „wynalazł” go w pewnym momencie swoich badań, zanim odkrył jego historię).

wymieniasz konkretnie PDA. Uwaga: maszyna Turinga jest odpowiednikiem urządzenia PDA z dwoma stosami. Oryginalne uzasadnienie PDA wydaje się być ściśle związane z rozwojem „teorii języka” ala chomsky.

patrz np. Analiza syntaktyczna i sklep Downdown, „Proceedings of Symposia in Applied Mathematics (vol. 12). Providence, RI: American Mathematical Society, 1961

jest to jedno z najwcześniejszych odniesień, jakie widziałem Oettinger, „Automatyczna analiza składniowa i przechowywanie w dół” p104, nie wiem, czy istnieją wcześniejsze odwołania do PDA.

wiele lat zajęło badanie wszystkich zintegrowanych automatów, aby zacząć opracowywać jednoczącą teorię (wciąż w budowie). kompletne koncepcje Turinga zostały opracowane pod koniec lat 30. XX wieku, gdy okazało się, że rachunek lambda (opracowany niezależnie przez Kościół) był równoważny z maszynami Turinga, a równoważność z maszynami pocztowymi została pokazana mniej więcej w tym samym czasie (chociaż te 3 modele zostały opracowane nieco niezależnie i nie od razu uświadomiono sobie, że jest odpowiednikiem Turinga w ich oryginalnej konstrukcji).

wciąż opracowywane są nowe modele, np. Automaty komórkowe mają znacznie nowszą historię i wykazano, że pod wieloma względami Turing jest kompletny.

wydaje się słuszne stwierdzenie, że większość osób pracujących w informatyce znała przełomowy artykuł Turingsa z 1936 r. i że miała duży wpływ na wszystkie późniejsze formuły konstrukcji automatów (szczególnie na koncepcję tabeli zmian stanu, która wydaje się być wprowadzona przez Turinga)

Do diabła z tym:

Patrząc wstecz, jakie znaczenie miałby dokument Turinga z 1936 roku dotyczący problemu Entscheidungs?

Zawsze czułem, że ludzie lubią tworzyć piosenki i tańczyć. Coś w tym jest związane z doktryną Trójcy, podczas gdy inżynierowi wystarczy, że dowiesz się o idei zapisanego programu i od razu powiesz: „To absolutnie pierwszorzędne, to jest sposób, aby to zrobić”. To wszystko, co musiałem wiedzieć.

W tym artykule nie było rozróżnienia, które miało jakiekolwiek praktyczne znaczenie. Miał szczęście, że w ogóle go opublikowano, ale bardzo się cieszę, że to zrobił. Mam na myśli, że [Alonzo] Churchl uzyskał ten sam wynik innymi metodami.

Lubiłem Turinga; Mam na myśli bardzo dobrze się dogadywaliśmy. Lubił ustanawiać prawo, co mi go nie podobało, ale nieźle się dogadywaliśmy. Ludzie czasem mówią, że nie rozumiałem Turinga, ale to po prostu nieprawda. Ale wtedy bardzo ostrożnie nie angażowałem się.

Maurice Wilkes. http://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext