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

247

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ś?

Doktorat
źródło
10
To pytanie na poziomie badawczym w TCS?
Hendrik Jan
13
To nie tyle pytanie badawcze, co pytanie o szerszą perspektywę na dany temat. Mamy tutaj wiele takich pytań. Zamiast rozpoczynać debatę w komentarzach, zachęcam do zamieszczenia pytania na stronie meta, jeśli chcesz bardziej szczegółowo omówić zasadność takich pytań.
Suresh Venkat,
6
Doktor: Twoje pytanie dało kilka bardzo dobrych odpowiedzi, więc dziękuję za to. Byłaś szczera w swoich oświadczeniach i nie miałem zamiaru dyskwalifikować ciebie ani twojego pytania. W rzeczywistości jest na odwrót od tego, co sugeruje mój komentarz: widziałem kilka innych pytań, które zostały zbyt łatwo odrzucone przy użyciu tego cytatu z FAQ. Masz rację Suresh: to nie jest miejsce na rozpoczęcie debaty. Przepraszam.
Hendrik Jan
1
@HendrikJan - Oh nie martw się! Tekst ukrywa dźwięk. Nigdy tak nie miałem na myśli. Myślałem, że pytasz mnie, czy to pytanie badawcze z mojej strony.
Doktorat
16
Wyrazy uznania dla doktora i Hendrika za poziom uprzejmości, którego rzadko spotykam na forach publicznych.
Lucas,

Odpowiedzi:

342

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.

Vijay D.
źródło
27
Piękna lista. Chciałbym dodać, że automaty zapewniają interesującą perspektywę teorii kodowania, której pionierem był Schuetzenberger. Ponadto współczesna teoria współbieżności i teoria procesów są uogólnieniem teorii automatów, w której automaty można komponować równolegle i synchronizować ich działania.
Martin Berger,
6
Łał. (+ 0,5 za ostatnie zdanie. :-)
LarsH,
6
Właśnie dołączyłem do TCS.SE wyłącznie po to, aby dać +1.
Tynam
5
Pomimo znajomości prawie wszystkiego na tej liście, nadal czuję się oświecony, że ją przeczytałem. (Poza tym (i tak dalej.) * Zachichotałem.)
CA McCann,
2
Szczerze mówiąc, nigdy nie myślałem o większości tych rzeczy (i niektórych twierdzeniach, o których nigdy nie słyszałem), i zacząłem kurs teorii teorii. Czy trzeba mieć szczególnie dobrego nauczyciela lub program nauczania, aby wskazać te objawienia?
Ken Bloom
33

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.

Lew Reyzin
źródło
2
# 1 ma sens i myślę, że rozumiem powód. Ale jak wyjaśniłbyś powód „pójścia naprzód” od FA? Ci, którzy wiedzą coś o ToC, mogą cofnąć się wstecz i zastanowić nad tym. Jak najlepiej wyjaśnić „dlaczego” uczniom, którzy rozpoczynają naukę teorii automatów i znają tylko FA? Czy po prostu stwierdzamy, że zaczynamy od maszyn bitowych, ponieważ są one podstawowe - dlaczego? Jak najlepiej odpowiedzieć „dlaczego”, dlaczego? Byłbym wdzięczny za trochę światła, odpowiadając na to pytanie dotyczące całkowitej liczby noobów do ToC :)
PhD
2
Argument „do przodu” pochodzi z faktu (jak wspomniała Sariel), że maszyny stanowe są prawdopodobnie najbardziej podstawowymi urządzeniami komputerowymi. Jesteś w stanie: coś się dzieje, a następnie przechodzisz do nowego stanu. Zauważ, że łańcuchy markowa (które są bardzo ważne w uczeniu maszynowym) są po prostu probabilistycznymi FSM.
Suresh Venkat,
31

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ć.

Alex ten Brink
źródło
2
„... możesz robić rzeczy za pomocą automatów skończonych, w przeciwieństwie do maszyn Turinga”. rozumiem pt, jednak cytat, który brzmi ironicznie lub nie ma większego sensu, jest
wyrwany
27

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ć?

Sariel Har-Peled
źródło
21

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.

David Eppstein
źródło
18

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:

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.

Radu GRIGore
źródło
16

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ć.

Luke Mathieson
źródło
10

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”.

Tarik FDIL
źródło
9

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.

geohump
źródło
Brzmi bardzo pochłaniająco, ale czy możesz wyjaśnić coś więcej? to jest trudno wyobrazić sobie protokół sieciowy jako machiny państwowej. Dziękuję Ci.
hkoosha
3

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.

Aryeh
źródło
-4

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ę.

David
źródło
1
Zakładam jednak, że nie wykazałeś równoważności między niedeterministycznymi automatami skończonymi a maszynami Turinga. To jest ten konkretny obiekt, o który OP pytał, a reszta z nas nazywa „pomniejszymi”.
Vijay D
2
A FA to nie to samo co FSM.
Suresh Venkat