Różnica między maszyną Turinga a maszyną skończonego stanu?

27

Robię prezentację na temat maszyn Turinga i chciałem przedstawić trochę informacji na temat FSM przed wprowadzeniem maszyn Turinga. Problem w tym, że tak naprawdę nie wiem, co BARDZO różni się od siebie.

Oto, co wiem, że jest inaczej:

FSM ma sekwencyjne stany w zależności od spełnienia odpowiedniego warunku, podczas gdy maszyny Turinga działają na nieskończonej „taśmie” z głowicą, która czyta i pisze.

W FSM jest więcej miejsca na błędy, ponieważ łatwo możemy popaść w niekończący się stan, podczas gdy maszyny Turinga to nie tyle, ponieważ możemy cofać się i zmieniać rzeczy.

Ale poza tym nie znam o wiele więcej różnic, które czynią maszyny Turinga lepszymi niż FSM.

Możesz mi pomóc?

terminology turing-machines finite-automata machine-models Julio Garcia
źródło
2
Google nie jest trudny do wyszukania w „FSM vs. Turing Machine”! To zabawna część prowadzenia własnych badań. Główną różnicą jest to, że maszyna Turinga ma nieskończoną „pamięć”, ale FSM nie.
Dai
Ok, trochę oszukiwałem>.> ;;; Gotcha! Dzięki!
Julio Garcia
3
argument dotyczący „błędu” jest nieprawidłowy. Spróbuj wikipedii i podręczników. Zobacz, jakie są ich podstawowe różnice, cel wykorzystania każdego z nich (np. Kiedy nie możemy wybrać FSM zamiast TM?) I ich związek.
Parham
@MahmoudAlimohamadi, co mam na myśli to, że istnieje większa szansa, że ​​fsm wyląduje w niekończącym się stanie.
Julio Garcia
@Dai: Jest to bardziej poprawne powiedzieć, że maszyna Turinga może wykorzystywać takie dowolnie dużej ilości pamięci. Użyta ilość nigdy nie jest nieskończona.
reinierpost

Odpowiedzi:

24

Główną różnicą między działaniem DFA (Deterministic Finite Automaton) i baz TM jest sposób, w jaki wykorzystują pamięć.

Intuicyjnie DFA w ogóle nie mają pamięci „scratch”; konfiguracja DFA jest w pełni uwzględniana przez stan, w którym się obecnie znajduje, i jego bieżący postęp w czytaniu danych wejściowych.

Intuicyjnie bazy TM mają pamięć „scratch” w postaci taśmy; konfiguracja TM składa się zarówno z jej bieżącego stanu, jak i bieżącej zawartości taśmy, którą TM może zmieniać podczas wykonywania.

DFA można uważać za TM, która nie zmienia żadnych symboli taśmy ani nie przesuwa głowy w lewo. Ograniczenia te uniemożliwiają rozpoznanie niektórych języków, które mogą być akceptowane przez TM.

Zauważ, że używam terminu „DFA” zamiast „FSM”, ponieważ technicznie uważam TM za maszynę o stanie skończonym, ponieważ TM z definicji mają skończoną liczbę stanów. Różnica między DFA i TM polega na liczbie konfiguracji, która jest taka sama jak liczba stanów dla DFA, ale jest nieskończenie wielka dla TM.

Patrick87
źródło
Ach, rozumiem. Jedno pytanie dotyczące części „bez pamięci”: widziałem przykład automatu, który sumował wydane monety. Skąd wiedzą, ile pieniędzy, jeśli nie ma pamięci?
Julio Garcia
@JulioGarcia Trudno powiedzieć, nie wiedząc dokładnie, co widziałeś. Istnieją maszyny Moore i Mealy, które mogą wyświetlać symbole przy przejściach. Działanie automatu może być lepiej modelowane przez jeden z tych mechanizmów. Waniliowy DFA przyjmuje i odrzuca tylko sznurki ... automat powinien „akceptować” dowolny „sznur” monet. W zależności od tego, w jaki sposób modelujesz dodatkowe skutki uboczne dawania zmian, rodzaj potrzebnej pamięci scratch może być brak lub nieskończony losowy dostęp.
Patrick87
Nie widząc twojego przykładu, nie mogę być całkowicie pewien, ale mam dwa domysły. Jednym z nich jest to, że nie wie, ile jest pieniędzy: po prostu zakłada, że ​​wystarczy. Nie chciałbyś w ten sposób zbudować prawdziwego automatu, ale nadal jest to przydatny przykład tej koncepcji. Inną możliwością jest to, że tak naprawdę nie jest to „czysty” FSA: jest podłączony do czujnika, który może w jakiś sposób uzyskać te dane z „zewnątrz” maszyny. Maszyna nie wie ani nie obchodzi, skąd pochodzą dane, i nie może przechowywać niczego w czujniku (więc nie jest tak naprawdę „pamięcią”), ale nadal może działać na podstawie tego, co tam widzi.
Spooniest
16

Maszyny Turinga opisują znacznie większą klasę języków, klasę języków rekurencyjnie policzalnych. Maszyny stanów skończonych opisują klasę zwykłych języków.

Maszyny stanów skończonych nie mają „pamięci”, są ograniczone swoimi stanami.

Maszyna o skończonym stanie jest ograniczoną maszyną Turinga, w której głowa może wykonywać tylko operacje „odczytu” i zawsze porusza się od lewej do prawej.

Weź ten język jako przykład:

L={aibi| i>=0}

Ponieważ maszyny stanów skończonych są ograniczone w tym sensie, że nie mają pamięci, nie można zbudować FSM, który akceptuje L.

Podsumowując:

Maszyny stanów skończonych opisują małą klasę języków, w których nie jest potrzebna pamięć.

Maszyny Turinga to matematyczny opis komputera i akceptują znacznie większą klasę języków niż FSM.

Maszyny Turinga mają większą moc obliczeniową niż FSM. Są zadania, których nie może wykonać żaden FSM, ale które mogą wykonać Maszyny Turinga.

mrjasmin
źródło
3

Miałem te same wątpliwości i widziałem dwa bardzo pouczające filmy i jedno wyjaśnienie na temat Quory w następujący sposób:

Maszyna stanów skończonych jest tylko zbiorem stanów i przejść. Jedyną pamięcią, jaką ma, jest stan, w jakim się znajduje. Liczba stanów pamięci jest więc ... skończona.

Maszyna Turinga jest maszyną skończoną i pamięcią taśmową. Każdemu przejściu może towarzyszyć operacja na taśmie (ruch, odczyt, zapis).

Zrozumiałem z tego, że maszyna Turinga używa / ma maszynę skończoną jako część swojej procedury operacyjnej, a także dodaje do niej trochę edytowalnej pamięci.

Proszę również obejrzeć te dwa filmy, są pouczające!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

użytkownik5193682
źródło
2

O ile rozumiem różnice między (standardowym modelem) Turinga i (standardowym modelem) Mealy Machines:

  • Maszyny Turinga odczytują i zapisują na tej samej taśmie w porównaniu do maszyn Mealy odczytują na jednej taśmie wejściowej i zapisują na innej taśmie wyjściowej
  • Maszyny Turinga mogą zmieniać „kierunek taśmy” (postęp w lewo lub w prawo [lub zatrzymywać]) w porównaniu do maszyn Mealy mogą postępować tylko w prawo (dlatego nie ma ustawionego kierunku {L, R, H} w funkcji przejścia maszyny Mealy [jest to domyślnie {R}, co oznacza brak wyboru])
  • Maszyny Turinga mogą zatrzymać się na dowolnej komórce z taśmą w przeciwieństwie do Mealy Machines odczytać cały wpis, a następnie zatrzymać jego akceptację lub odrzucenie
Michael Klaube
źródło
-3

Maszyna Turinga może przechowywać, jako część taśmy, rzeczy, które chce zapamiętać.

Richard Mullins
źródło
5
Nie jest jasne, co rozumiesz przez „to”, ale zarówno maszyny Turinga, jak i FSM mogą to zrobić, więc nie jest to różnica.
David Richerby,
@DavidRicherby Ale FSM może przechowywać tylko z góry określoną ilość, podczas gdy maszyny Turinga mogą przechowywać tyle, ile chcą. To jest podstawowa różnica.
Gilles 'SO - przestań być zły'
1
@Gilles zgodził się, ale nie tak mówi odpowiedź.
David Richerby