Jakie oświecenie powinienem osiągnąć po przestudiowaniu automatów skończonych?

Przeglądam teorię obliczeń dla zabawy i to pytanie nęka mnie od dłuższego czasu (zabawne, że nie pomyślałem o tym, gdy nauczyłem się teorii automatu w mojej szkole licencjackiej). Więc „dlaczego” dokładnie badamy deterministyczne i niedeterministyczne automaty skończone (DFA / NFA)? Oto kilka odpowiedzi, które wymyśliłem po monologowaniu, ale wciąż nie widzę ich ogólnego wkładu w moment „aha”:

1. Studiować, czym są i nie są w stanie np. Mieć ograniczeń
   • Dlaczego?
2. Ponieważ są one podstawowymi modelami obliczeń teoretycznych i stanowiłyby podstawę innych, bardziej wydajnych modeli obliczeń.
   • Co czyni je „podstawowymi”? Czy to dlatego, że mają tylko jeden bit pamięci i przejścia stanu?
3. OK, a co z tego? W jaki sposób wszystko to przyczynia się do odpowiedzi na pytanie dotyczące obliczalności? Wydaje się, że maszyny Turinga naprawdę dobrze to rozumieją i istnieją „mniejsze” modele obliczeń, takie jak PDA, DFA / NFAs / Regexes itp. Ale jeśli nie znamy FA, ​​to na czym im brakuje?

Więc chociaż „rozumiem” do pewnego stopnia, nie jestem w stanie odpowiedzieć sobie na to pytanie? Jak najlepiej wytłumaczysz „po co studiować D / N-FA”? Na jakie pytanie chcą odpowiedzieć? Jak to pomaga i dlaczego jest to pierwsza rzecz nauczana w teorii automatów?

PS: Mam świadomość różnych aplikacji leksykograficznych i dopasowywania wzorców, które można zaimplementować jako takie. Nie chcę jednak wiedzieć, do czego można go używać praktycznie, ale jaki był powód jego użycia / wynalazku / projektu podczas kulminacji studiowania teorii obliczeń. Historycznie rzecz biorąc, co doprowadziło nas do tego i do czego to ma prowadzić zrozumienie „aha”? Jeśli miałbyś wyjaśnić ich znaczenie studentom CS dopiero rozpoczynającym naukę teorii automatów, jak to zrobiłeś?

Osobiście podobało mi się kilka Aha! chwile od studiowania podstawowej teorii automatów. NFA i DFA tworzą mikrokosmos dla teoretycznej informatyki jako całości.

1. Czy niedeterminizm prowadzi do efektywności? Istnieją standardowe przykłady, w których minimalny deterministyczny automat dla języka jest wykładniczo większy niż minimalny niedeterministyczny automat. Zrozumienie tej różnicy w maszynach Turinga stanowi rdzeń (teoretycznej) informatyki. NFA i DFA to najprostszy przykład, jaki znam, gdzie wyraźnie widać ścisłą lukę między determinizmem a niedeterminizmem.
2. Obliczalność! = Złożoność. NFAs i DFAS zarówno reprezentacji regularnych języków i są równoważne w co oni obliczyć. Różnią się sposobem obliczania.
3. Maszyny Udoskonalaj języki. To inne podejście do tego, co obliczamy i jak obliczamy. Możesz myśleć o językach obliczeniowych (i funkcjach) jako o definicji klasy równoważności automatów. Jest to fundamentalna zmiana perspektywy w TCS, w której skupiamy się nie tylko na tym, co, ale na sposobie obliczeń i staramy się wybrać właściwe „jak” podczas projektowania algorytmu lub zrozumieć przestrzeń różnych sposobów studiowania klas złożoności.
4. Wartość reprezentacji kanonicznej. DFA są kwintesencją przykładu struktury danych dopuszczającej reprezentację kanoniczną. Każdy zwykły język ma unikalny, minimalny DFA. Oznacza to, że przy minimalnym DFA ważne operacje, takie jak włączenie języka, uzupełnianie i sprawdzanie akceptacji słowa, stają się banalne. Opracowywanie i wykorzystywanie reprezentacji kanonicznych jest przydatną sztuczką podczas opracowywania algorytmów.
5. Brak reprezentacji kanonicznych. Nie ma dobrze przyjętej kanonicznej reprezentacji wyrażeń regularnych lub NFA. Tak więc, pomimo powyższego punktu, reprezentacje kanoniczne nie zawsze istnieją. Zobaczysz ten punkt w wielu różnych obszarach informatyki. (na przykład formuły logiczne zdań również nie mają reprezentacji kanonicznych, podczas gdy ROBDD mają).
6. Koszt reprezentacji kanonicznej. Możesz nawet zrozumieć różnicę między NFA i DFA jako algorytmiczne twierdzenie o braku obiadu . Jeśli chcemy sprawdzić włączenie języka lub uzupełnienie NFA, możesz je określić i zminimalizować i kontynuować od tego momentu. Jednak operacja „redukcji” wiąże się z pewnym kosztem. Zobaczysz przykłady kanonizacji kosztem w kilku innych obszarach informatyki.
7. Nieskończony! = Nierozstrzygalny. Powszechnym nieporozumieniem jest to, że problemy o charakterze nieskończonym są z natury nierozstrzygalne. Zwykłe języki zawierają nieskończenie wiele ciągów znaków, a mimo to mają kilka rozstrzygających właściwości. Teoria zwykłych języków pokazuje, że sama nieskończoność nie jest źródłem nierozstrzygalności.
8. Trzymaj Infinity w dłoni swojego automatu. Automat skończony można postrzegać wyłącznie jako strukturę danych do reprezentowania zbiorów nieskończonych. ROBDD to struktura danych do reprezentowania funkcji boolowskich, którą można rozumieć jako reprezentującą zbiory skończone. Automat skończony to naturalne, nieskończone rozszerzenie ROBDD.
9. Pokorny procesor. Współczesny procesor ma w sobie wiele, ale można to zrozumieć jako automat skończony. Właśnie ta realizacja sprawiła, że ​​architektura komputera i konstrukcja procesora były dla mnie mniej zastraszające. Pokazuje to również, że w praktyce, jeśli starannie konstruujesz i manipulujesz stanami, możesz osiągnąć bardzo daleko za pomocą automatów skończonych.
10. Perspektywa algebraiczna. Zwykłe języki tworzą monoid składniowy i można je badać z tej perspektywy. Mówiąc bardziej ogólnie, w późniejszych badaniach można również zapytać, jaka jest właściwa struktura algebraiczna odpowiadająca niektórym problemom obliczeniowym.
11. Perspektywa kombinatoryczna. Automat skończony to wykres oznaczony etykietą. Sprawdzenie, czy słowo jest akceptowane, sprowadza się do znalezienia ścieżki na wykresie oznaczonym etykietą. Algorytmy automatów odpowiadają transformacjom grafów. Zrozumienie struktury automatów dla różnych podrodzin języków zwykłych jest aktywnym obszarem badawczym.
12. Trójkąt miłosny Algebra-Język-Kombinatoryka. Twierdzenie Myhill-Nerode pozwala rozpocząć od języka i wygenerować automat lub składniowy monoid. Matematycznie uzyskujemy tłumaczenie między bardzo różnymi typami obiektów matematycznych. Warto pamiętać o takich tłumaczeniach i szukać ich w innych obszarach informatyki oraz przemieszczać się między nimi w zależności od aplikacji.
13. Matematyka jest językiem wielkich obrazów. Języki regularne można scharakteryzować za pomocą NFA (wykresy), wyrażeń regularnych (gramatyka formalna), maszyn Turinga tylko do odczytu (maszyna), monoidów składniowych (algebra), algebry Kleene (algebra), logiki monadycznej drugiego rzędu itp. Bardziej ogólne Zjawiskiem jest to, że ważne, trwałe koncepcje mają wiele różnych matematycznych cech, z których każda wnosi różne smaki do naszego zrozumienia tego pomysłu.
14. Lemmy dla pracującego matematyka. Pumping Lemma to świetny przykład teoretycznego narzędzia, które można wykorzystać do rozwiązania różnych problemów. Praca z Lemmas jest dobrą praktyką w zakresie prób wykorzystania istniejących wyników.
15. Konieczne! = Wystarczające. Twierdzenie Myhill-Nerode zapewnia niezbędne i wystarczające warunki dla prawidłowego języka. Pumping Lemma daje nam niezbędne warunki. Porównanie tych dwóch i użycie ich w różnych sytuacjach pomogło mi zrozumieć różnicę między koniecznymi a wystarczającymi warunkami w praktyce matematycznej. Dowiedziałem się również, że niezbędnym i wystarczającym warunkiem wielokrotnego użytku jest luksus.
16. Perspektywa języka programowania. Wyrażenia regularne są prostym i pięknym przykładem języka programowania. Podsumowując, masz analogiczny skład sekwencyjny, a u gwiazdy Kleene analogiczny iteracja. Definiując składnię i semantykę wyrażeń regularnych, robisz mały krok w kierunku programowania języka programowania, widząc definicje indukcyjne i semantykę kompozycji.
17. Perspektywa kompilatora. Tłumaczenie z wyrażenia regularnego na automat skończony jest również prostym, teoretycznym kompilatorem. Możesz zobaczyć różnicę między parsowaniem, generowaniem kodu pośredniego i optymalizacją kompilatora, ze względu na różnicę w czytaniu wyrażeń regularnych, generowaniu automatu, a następnie minimalizowaniu / określaniu automatu.
18. Moc iteracji. Widząc, co możesz zrobić w automacie skończonym z pętlą i bez niej, możesz docenić moc iteracji. Pomoże to zrozumieć różnice między obwodami i maszynami lub między logiką klasyczną a logiką punktu stałego.
19. Algebra i Coalgebra. Zwykłe języki tworzą monoid składniowy, który jest strukturą algebraiczną. Skończone automaty tworzą coś, co w języku teorii kategorii nazywa się węgielnicą. W przypadku deterministycznego automatu możemy łatwo przechodzić między reprezentacją algebraiczną i węglową, ale w przypadku NFA nie jest to takie łatwe.
20. Perspektywa arytmetyczna. Istnieje ścisły związek między obliczeniami a teorią liczb. Możesz to rozumieć jako stwierdzenie o potędze teorii liczb i / lub uniwersalności obliczeń. Zwykle wiesz, że automaty skończone potrafią rozpoznać parzystą liczbę symboli i że nie mogą policzyć wystarczającej liczby pasujących do nawiasów. Ale ile potrafią arytmetyki? Automaty skończone mogą decydować o formułach arytmetycznych Presburger. Najprostsza procedura decyzyjna, którą znam dla arytmetyki Presburgera, redukuje formułę do automatu. To jedno spojrzenie, z którego można przejść do 10. problemu Hilberta, a jego rozwiązanie doprowadziło do odkrycia związku między równaniami diofantycznymi a maszynami Turinga.
21. Logiczna perspektywa. Obliczenia można zrozumieć z czysto logicznej perspektywy. Automaty skończone można scharakteryzować słabą, monadyczną logiką drugiego rzędu w stosunku do skończonych słów. To mój ulubiony, nietrywialny przykład logicznej charakterystyki urządzenia obliczeniowego. Opisowa teoria złożoności pokazuje, że wiele klas złożoności ma również charakter czysto logiczny.
22. Skończone automaty chowają się w miejscach, o których nigdy nie marzyłeś. (Wskazówka do komentarza Martina Bergera na temat związku z teorią kodowania) Nagroda Nobla w dziedzinie chemii z 2011 r. Została przyznana za odkrycie quasi-kryształów. Matematyka stojąca za quasi-kryształami związana jest z aperiodycznymi nachyleniami. Jedno szczególne aperiodyczne układanie płaszczyzny nazywa się układaniem płytek Cartwheel, które składa się z kształtu latawca i kształtu muszki. Możesz zakodować te kształty w kategoriach 0 i 1, a następnie zbadać właściwości tych sekwencji, które kodują sekwencje wzorów. W rzeczywistości, jeśli zamapujesz od 0 do 01 i od 1 do 0, i wielokrotnie zastosujesz tę mapę do cyfry 0, otrzymasz 0, 01, 010, 01001 itd. Zauważ, że długości tych łańcuchów są zgodne z sekwencją Fibonacciego. Słowa generowane w ten sposób nazywane są słowami Fibonacciego. Pewne sekwencje kształtów zaobserwowane w nachyleniach Penrose'a mogą być kodowane jako słowa Fibonacciego. Takie słowa zostały przestudiowane z punktu widzenia teorii automatów i zgadnij, co, niektóre rodziny słów są akceptowane przez automaty skończone, a nawet dostarczają przykłady najgorszego zachowania dla standardowych algorytmów, takich jak algorytm minimalizacji Hopcrofta. Powiedz mi, że masz zawroty głowy.

Mógłbym kontynuować. (I dalej.) * Uważam, że warto mieć automaty z tyłu głowy i co jakiś czas je przywoływać, aby zrozumieć nową koncepcję lub uzyskać intuicję na temat matematycznych pomysłów na wysokim poziomie. Wątpię, aby wszystko, o czym wspomniałem powyżej, można było przekazać w kilku pierwszych wykładach kursu, a nawet w pierwszym kursie. Są to długoterminowe nagrody oparte na początkowej inwestycji dokonanej w początkowych wykładach kursu teorii automatów.

Aby odnieść się do twojego tytułu: Nie zawsze szukam oświecenia, ale kiedy to robię, wolę skończone automaty. Pozostań spragniony, przyjacielu.

Istnieje wiele dobrych teoretycznych powodów, aby badać N / DFA. Dwa, które natychmiast przychodzą na myśl, to:

1. Maszyny Turinga (naszym zdaniem) rejestrują wszystko, co jest obliczalne. Możemy jednak zapytać: jakie części maszyny Turinga są „niezbędne”? Co się stanie, gdy ograniczysz maszynę Turinga na różne sposoby? DFA to bardzo poważne i naturalne ograniczenie (pozbawianie pamięci). PDA są mniej surowym ograniczeniem itp. Teoretycznie interesujące jest zobaczyć, co daje ci pamięć i co się stanie, gdy przejdziesz bez niej. Wydaje mi się to bardzo naturalnym i podstawowym pytaniem.

2. Maszyny Turinga potrzebują nieskończonej taśmy. Nasz wszechświat jest skończony, więc w pewnym sensie każde urządzenie komputerowe jest DFA. Wydaje się, że jest to ważny i znowu naturalny temat do nauki.

Pytanie, dlaczego warto studiować DFA, przypomina pytanie, dlaczego należy nauczyć się twierdzenia Godela o kompletności, gdy prawdziwą interesującą rzeczą jest jego twierdzenie o niekompletności .

Powodem, dla którego są pierwszym tematem w teorii automatów jest to, że naturalne jest budowanie do bardziej skomplikowanych trybów od mniej skomplikowanych.

Aby dodać jeszcze jedną perspektywę do pozostałych odpowiedzi: ponieważ możesz robić rzeczy za pomocą automatów skończonych, w przeciwieństwie do maszyn Turinga.

Niemal każda interesująca właściwość maszyn Turinga jest nierozstrzygalna. Przeciwnie, w przypadku automatów skończonych prawie wszystko jest rozstrzygalne. Równość językowa, integracja, pustka i uniwersalność są rozstrzygalne. W połączeniu z tymi skończonymi automatami są zamknięte pod prawie każdą operacją, o której myślisz, a że operacje te są obliczalne, możesz zrobić prawie wszystko, co kiedykolwiek chciałbyś zrobić z automatami skończonymi.

Oznacza to, że jeśli możesz uchwycić coś za pomocą automatów skończonych, automatycznie zyskujesz wiele narzędzi do analizy. Na przykład podczas testowania oprogramowania systemy i ich specyfikacje można modelować jako automaty skończone. Następnie można automatycznie przetestować, czy system poprawnie implementuje specyfikację.

Maszyny Turinga i skończone automaty uczą zatem ludzi interesującego i wszechobecnego kontrastu: więcej mocy opisowej idzie w parze z mniejszą łatwością obsługi. Automaty skończone niewiele mogą opisać, ale możemy przynajmniej z nimi coś zrobić.

Stan. musisz nauczyć się, że można modelować świat (w przypadku niektórych problemów) jako skończoną przestrzeń stanu i w tych ustawieniach można myśleć o obliczeniach. Jest to prosty wgląd, ale niezwykle przydatny, jeśli wykonujesz jakiekolwiek programowanie - możesz napotkać stan raz za razem, a FA daje ci sposób na ich przemyślenie. Uważam to za wystarczającą wymówkę do nauczania całej klasy. Oczywiście stan może być deterministyczny lub niedeterministyczny. Tak więc DFA i NFA, ale możesz konwertować między nimi itp.

Drugą rzeczą do nauczenia jest twierdzenie Haltinga. Co jest związane z twierdzeniem o niekompletności Godela. (Nie możesz zbudować maszyny, która może obliczyć wszystko, i istnieją matematyczne twierdzenia, których nie można ani udowodnić, ani obalić, i jako takie musiały być traktowane jako aksjomaty. To znaczy, żyjemy w świecie, który nie ma skończonego opisu ani prawdziwego wyrocznie - tak dla nas!)

Teraz zrobiłem licencjat z matematyki i przyzwyczaiłeś się do myśli, że uczysz się rzeczy, których nie masz pojęcia, dlaczego się uczysz (teoria grupy, teoria miar, teoria mnogości, przestrzenie Hilberta itp. Itd. Itd.) , BTW]). Jest coś do powiedzenia na temat uczenia się, jak się uczyć - następnym razem będziesz musiał nauczyć się dziwnej matematyki (ponieważ musisz jej użyć, aby zrobić coś tam w prawdziwym świecie), która wygląda bardzo dziwnie. Trzecią rzeczą, której należy się nauczyć, jest dojrzałość matematyczna - umiejętność dyskutowania na różne tematy, wiedza o tym, czy dowody są poprawne czy nie, spisywanie dowodów itp. Jeśli już to masz, ten kurs jest łatwy i nie przejmujesz się tym zbytnio wiele, dlaczego się tego uczysz.

Z wyjątkiem tych, kurs jest całkowitą stratą czasu, podobnie jak wszystko inne. W szczególności możesz prowadzić szczęśliwe życie, nie znając tych rzeczy. Ale to dosłownie prawda o całej wiedzy. Mniej więcej. Dla mnie warto studiować na uniwersytecie, jeśli spojrzysz na świat inaczej po nauce. To zdecydowanie jeden z kursów, który zmienił sposób myślenia o świecie. O co jeszcze możesz zapytać?

Chociaż tak naprawdę nie jest to powód, dla którego zostały pierwotnie zbadane, skończone automaty i rozpoznawane przez nich zwykłe języki są na tyle łatwe do przełożenia, że ​​zostały użyte jako elementy składowe bardziej skomplikowanych teorii matematycznych. W tym kontekście zobacz szczególnie automatyczne grupy (grupy, w których elementy mogą być reprezentowane przez łańcuchy w zwykłym języku i w których produkty elementów przez generatory grup można obliczyć za pomocą przetworników skończonych stanów) i miękkie przesunięcia (pod przesunięcia przestrzeni przesunięcia, których zakazane słowa tworzą zwykły język). Istnieją więc powody, aby je studiować, nawet jeśli interesuje Cię czysta matematyka, a nie informatyka.

Automaty skończone zostały również wykorzystane w projektowaniu algorytmów dla innych rodzajów obiektów. Na przykład algorytm Culika do testowania odwracalności jednowymiarowego automatu komórkowego obejmuje konstruowanie, modyfikowanie i testowanie właściwości niektórych NFA. A artykuł FOCS z 1986 roku autorstwa Natarajana pokazał, jak rozwiązać pewien problem w projektowaniu mechanicznych linii montażowych, redukując go do obliczeń dotyczących automatów skończonych.

Zadajesz (przynajmniej) dwa różne pytania: (a) Jakie części teorii opierają się obecnie na automatach skończonych? (b) Dlaczego przede wszystkim opracowano automaty skończone? Myślę, że najlepszym sposobem rozwiązania tego ostatniego jest przyjrzenie się starym papierom, takim jak:

• Rabin, Scott, Finite Automata i ich problemy decyzyjne , 1959

Oto dwa pierwsze akapity:

Maszyny Turinga są powszechnie uważane za abstrakcyjny prototyp komputerów cyfrowych; jednak pracownicy w terenie coraz bardziej odczuwali, że pojęcie maszyny Turinga jest zbyt ogólne, aby służyć jako dokładny model rzeczywistych komputerów. Powszechnie wiadomo, że nawet w przypadku prostych obliczeń nie jest możliwe podanie a priori górnej granicy ilości taśmy, której maszyna Turinga będzie potrzebować do dowolnego obliczenia. Właśnie ta cecha sprawia, że ​​koncepcja Turinga jest nierealna.

W ostatnich latach w literaturze pojawiła się idea skończonego automatu . Są to maszyny posiadające tylko skończoną liczbę stanów wewnętrznych, które można wykorzystać do pamięci i obliczeń. Wydaje się, że ograniczenie skończoności lepiej przybliża ideę fizycznej maszyny. Oczywiście takie maszyny nie są w stanie zrobić tyle, co maszyny Turinga, ale przewaga wynikająca z możliwości obliczenia dowolnej ogólnej funkcji rekurencyjnej jest wątpliwa, ponieważ bardzo niewiele z tych funkcji pojawia się w praktycznych zastosowaniach.

Krótko mówiąc, zostały one opracowane jako model prawdziwych komputerów, które mają ograniczone zasoby.

Innym powodem są stosunkowo praktyczne modele teoretyczne. Maszyna Turinga, oprócz niemożliwości nieskończonej taśmy, jest dość niezręczna w stosunku do tego, jak to jest programować komputer (zwróć uwagę, że nie jest to dobra analogia na początek!). PDA i DFA są jednak całkiem podatne na bycie modelami rzeczywistych programów w tym sensie, że projekt PDA / DFA często można łatwo przekształcić w prawdziwy program. Na przykład projekt kompilatora wykorzystuje je w szerokim zakresie. Tak więc w tego rodzaju punktach łączących teorię i praktykę rozumiemy, w jaki sposób wszystko to łączy się oraz co możemy, a czego nie możemy zrobić.

Sprawdź grę „Living Binary Adder” tutaj: http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html Kiedyś prezentowałem tę grę moim studentom we wczesnych rozdziałach o DFA / NFA. Ilustruje dwie ważne rzeczy w teorii automatów:

1. Jak przekształcić proces umysłowy w prosty proces mechaniczny
2. Co tak naprawdę oznacza abstrakcja. Dwa stany, jak powyższe stany C i Z, mogą być dowolne: tranzystory w komputerze, mechanizm hydrauliczny lub dwóch ludzkich graczy!

To czasem przynosi uczniom chwilę „Aha”.

Koncepcja DFA jest bardzo przydatna przy projektowaniu wydajnych rozwiązań wielu rodzajów problemów. Jednym z przykładów jest sieć. Każdy protokół można zaimplementować jako maszynę stanu. Wdrożenie rozwiązania w ten sposób sprawia, że ​​kod jest prostszy, a prostszy oznacza niższy wskaźnik defektów. Oznacza to również, że zmiany w kodzie są łatwiejsze i mają mniejszy wpływ, ponownie mając niższy wskaźnik wad.

Niektórym trudno jest postrzegać protokół sieciowy jako maszynę stanową, ale dla tych, którzy mogą sprawić, że skok będzie bardzo satysfakcjonujący pod względem zwrotu wysiłku.

Właściwie to moi uczniowie czasami dokładnie o to pytają - po spędzeniu dużej części semestru na automatach skończonych i wreszcie dotarciu do maszyn Turinga. Po co spędzać tyle czasu na słabszym formalizmie, skoro dostępny jest silniejszy? Dlatego wyjaśniam nieodłączny kompromis między mocą ekspresyjną a złożonością analityczną. Bogatsze modele są zazwyczaj trudniejsze do analizy. Dychotomia DFA vs. TM jest ekstremalna, ponieważ problem członkostwa jest dla jednej osoby trywialny, a dla drugiej nieobliczalny. Mniej ekstremalnym przykładem może być DFA vs. PDA. Problem członkostwa dla tych ostatnich okazuje się być skuteczny do rozwiązania, ale rozwiązanie wcale nie jest trywialne. Widzimy to w wielu gałęziach matematyki i nauk ścisłych: studiuj prosty model, aby uzyskać jak najdokładniejsze zrozumienie, co zwykle prowadzi również do wglądu w bardziej złożone modele.

Widzę kilka odpowiedzi nazywających FM mniejszymi niż maszyny Turinga.

W zajęciach podyplomowych skupiłem się głównie na ich równoważności, a nie na wyróżnieniach. Dla każdego badanego modelu FSM musieliśmy udowodnić ich równoważność z maszynami Turinga. Odbywa się to poprzez wdrożenie maszyny Turinga w FSM. IIRC, badaliśmy także niektóre inne modele obliczeniowe, które nie wdrażają TM, ale zapominam, jakie to były. Chodzi o to, że jeśli możesz zaimplementować TM, możesz uruchomić dowolny program TM na modelu, biorąc pod uwagę wystarczająco duży analog taśmy dla uruchomionego problemu.

Odpowiedź na pytanie brzmiała: TM jest podstawowym modelem obliczeniowym, ale niezbyt praktycznym, jeśli chodzi o budowę użytecznych maszyn. Stąd modele FSM.

Zostało mi to przyniesione do domu, gdy mniej więcej w tym samym czasie (1984) odkryłem język FORTH. Jego silnik wykonawczy jest oparty na czystej realizacji PDA z dwoma stosami. Idąc głębiej, lubię ten sam silnik w kompilatorach ekspresji

Chociaż dla mnie prawdziwym wpływem FSM było odkrycie książki „Teoria automatów skończonych” Trakhtenbrota i Korzyńskiego (?), Gdy miałem 18 lat, odkrycie, które zasadniczo dało mi karierę.