Czy niedeterminizm w niedeterministycznej maszynie Turinga różni się od automatów skończonych i automatów wypychających?

9

Niech łańcuch wejściowy będzie podany jako w1w2...wn. Następnie, jeśli NFA jest obecnie w stanier (i przeczytał wejście do alfabetu wi ), a następnie przed odczytaniem następnego symbolu wejściowego NFA dzieli się na dwa NFA, z których jeden jest w stanie r i inne istnienie w s, jeśli istnieje przejście tego typu rϵs. Jeśli istnieje cykl tego typurϵsϵq1....ϵqkϵr, gdzie qi są niektóre stany NFA, wtedy nie ma sensu zapamiętywać innego stanu NFA r do momentu odczytania danych wejściowych do alfabetu wi.

Jeśli PDA (niedeterministyczny) jest w stanier (i dane wejściowe są odczytywane do wi ) i istnieje cykl rϵ,ϵasϵ,ϵaq1....ϵ,ϵaqkϵ,ϵar (gdzie przejście ϵ,ϵa oznacza, że ​​nic później wi jest odczytywany z wejścia, nic nie jest wyskakujące lub odczytywane ze stosu i alfabetu a jest wypychany na stos), a następnie przed odczytaniem następnego alfabetu wejściowego wi+1 w stanach będzie nieskończony PDA r,s,q1,...qk ponieważ w przeciwieństwie do NFA, chociaż stany są skończonymi stosami, zawartość może być inna (nieskończone możliwości), jeśli się nie mylę.

Podobnie jak w przypadku NFA i PDA, siła niedeterminizmu pochodzi ϵprzejścia Zakładam więc, że niedeterministyczna maszyna Turinga również czerpie z niej niedeterminizmϵprzejścia takie jak NFA i PDA (bardziej jak PDA). Wiem, że deterministyczna maszyna Turinga może symulować niedeterministyczną (znam dowód, który wykorzystuje wyszukiwanie w pierwszej kolejności). Ale teraz wątpię, jak to możliwe. Ponieważ jeśli cykl typu w powyższym PDA istnieje na schemacie stanu niedeterministycznej maszyny Turinga, to przed odczytaniem następnego symboluwi+1deterministyczna maszyna Turinga nawet podczas symulacji konfiguracji w jakiejś gałęzi niedeterministycznej maszyny Turinga (podczas gdy bfs) musiałaby śledzić nieskończoną maszynę Turinga (ponownie stany są skończone, ale symbole na taśmie mają nieskończone możliwości).
Jak dokładnie zdefiniowany jest brak determinizmu w przypadku maszyn Turinga? Czy nie rozumiem czegoś trywialnego? Czy używaj niedeterministycznych maszyn Turingaϵ przejścia?


Przepraszam za moje trywialne wątpliwości. Jeśli coś jest nie tak, mogę zaktualizować swoje pytanie.

sashas
źródło
2
w odniesieniu do pytania tytułowego nie ma dużej różnicy w definicjach formalnych. jeśli chodzi o powstającą moc, tak, ma ona wiele różnych implikacji dla każdego modelu maszyny. co do reszty pytania, trudno jest je przeanalizować. :(
vzn
1
Czy sprawdziłeś Wikipedię? en.wikipedia.org/wiki/Non-deterministic_Turing_machine
Yuval Filmus
@YuvalFilmus tak mam. Definicja funkcji przejścia obejmuje zestaw mocy, który rozumiem. Ale chodzi o toepsilonprzejścia w maszynach Turinga są dla mnie nadal niejasne.
sashas
@vzn Tak myślałem. Naprawdę przepraszam. Źle wyrażam swoje wątpliwości. Ale mogę poprawić, jeśli podasz sugestie.
sashas

Odpowiedzi:

8

Niedeterminizm jest tą samą koncepcją we wszystkich kontekstach - maszynie można wykonać kilka opcji w dowolnym punkcie. Jednak semantyka jest nieco inna, ponieważ DFA / NFA i PDA zawsze definiują funkcje całkowite , podczas gdy maszyny Turinga (deterministyczne lub niedeterministyczne) ogólnie definiują funkcje cząstkowe .

Funkcja częściowa to funkcja zdefiniowana tylko w części domeny. Gdybyf nie jest zdefiniowany w dniu x wtedy piszemy f(x)=. (Więcf jest naprawdę funkcją całkowitą, ale w zakresie znajduje się specjalny element oznaczający, że wynik jest niezdefiniowany.) Deterministyczna maszyna Turinga M definiuje funkcję częściową w następujący sposób: if M zatrzymuje się x następnie M(x) jest zawartością taśmy, kiedy M zatrzymuje się x; i w innym znaczeniu,M(x)=.

Deterministyczny decydent maszyny Turinga ma dwa rodzaje stanów zatrzymania: akceptujący i odrzucający oraz definiuje funkcję częściową w następujący sposób: jeśliM zatrzymuje się x zatem w stanie akceptacji M(x)=1; jeśli zatrzyma się w stanie odrzucenia, toM(x)=0; jeśli to się nie zatrzyma, toM(x)=. GdybyMzawsze się zatrzymuje, wtedy mówimy, że akceptuje językL={x:M(x)=1}.

Niedeterministyczna maszyna Turinga (która zawsze decyduje) może „rozgałęziać się” (mieć kilka możliwych opcji w danym momencie) i ma następującą semantykę:

  • M(x)=1 jeśli na wejściu x, maszyna M zatrzymuje się na wszystkich gałęziach, zatrzymując się w stanie akceptacji dla co najmniej jednej gałęzi.
  • M(x)=0 jeśli na wejściu x, maszyna M zatrzymuje się na wszystkich gałęziach, zawsze zatrzymując się w stanie odrzucającym.
  • M(x)= jeśli na wejściu x istnieje gałąź, na której M nie zatrzymuje się

Biorąc pod uwagę tę definicję, mam nadzieję, że jest jasne, jak symulować niedeterministyczną maszynę Turinga za pomocą deterministycznego decydenta maszyny Turinga: wypróbowujesz wszystkie gałęzie, sprawdzając, czy którakolwiek z nich prowadzi do akceptowalnego stanu zatrzymania. Po zatrzymaniu wszystkich gałęzi możesz zdecydować, czy przejść do stanu akceptacji czy odrzucenia. Jeśli niedeterministyczna maszyna Turinga nie zatrzymuje się na jakiejś gałęzi, to i tak deterministyczna.


Co powiesz na ϵ-move? Powodują problemy, ponieważ odpowiedni automat nigdy się nie zatrzyma. W przypadku automatów skończonych (NFA i PDA) po cichu ignorujemy obliczenia bez zatrzymywania. Naszym powodem jest to, że powstałe języki są zawsze obliczalne, nawet jeśli naiwny algorytm symulujący je deterministycznie (symulujący wszystkie ścieżki obliczeniowe) nie całkiem działa. Nie jest to takie trudne dla NFA, które można przekształcić w DFA. Jednak deterministyczne PDA są ściśle słabsze niż niedeterministyczne PDA. Niemniej jednak możesz pokazać, że każdy PDA jest równoważny z jednym bezϵ-transitions (choć dowód może przechodzić przez gramatyki bezkontekstowe).

Możesz symulować ϵ- porusza się w maszynach Turinga, ale musisz uważać, aby nie było żadnych pętli, które powodowałyby nieprzerwane obliczenia. W niektórych przypadkach możemy jednak zastosować tę samą sztuczkę, co powyżej. Załóżmy na przykład, że twoja maszyna Turinga jest ograniczona przestrzenią: znamy górną granicę przestrzeni, z której korzysta (w zależności od długości wejściowej). W takim przypadku każde niekończące się obliczenie musi się cyklicznie (ponieważ maszyna Turinga ma skończenie wiele stanów, w tym zawartość taśmy), a więc jeśli „zignorujemy” obliczenia nie zatrzymujące się jak wyżej, wynikowy model obliczeń jest nadal obliczalny. Mówiąc bardziej ogólnie, działa to tak długo, jak mamy gwarancję, że każde nieprzerwane obliczenia będą się powtarzać. (Dotyczy to NFA, ale nie PDA.)

Yuval Filmus
źródło
Dziękuję Ci. Miałem ostatnią wątpliwość. W PDA z przejściemrb,cas, jeśli PDA jest w stanie r to podzieli się tylko wtedy, gdy b ( b czy alfabet jest odczytywany z taśmy wejściowej, c jest alfabet wyskakujący ze stosu i a jest wypychany na stos) jest ϵ niezależnie od czego a i c są ( ϵlub zwykłe stosy alfabetów). Czy mam rację ?
sashas
@sasha Execution „dzieli”, ilekroć jest więcej niż jedna opcja, aby kontynuować.
Yuval Filmus
Jak mogę udowodnić, że jest to urządzenie PDA ϵprzejścia można przekształcić w jedno bez nich? Wiem, że zawsze mogę udowodnić, że język akceptowany przez dowolny PDA jest rozstrzygalny poprzez konwersję na jego CFG w normalnej formie Chomsky'ego. Ale nadal nie można przekonwertować na PDA bez przejść epsilon. Byłbym wdzięczny za każdą wskazówkę.
sashas
1
@sasha Możesz przekonwertować gramatykę bezkontekstową w normalnej formie Greibacha na PDA bez ϵprzejścia (przynajmniej według Wikipedii).
Yuval Filmus
1
@YuvalFilmus, niedeterministyczna konstrukcja GNF ma zasadniczo charakter rekurencyjny: do produkcji AaB1B2Bn, gdyby A znajduje się na górze stosu, na wejściu a zastąpić A przez B1Bnna stosie. Nieϵwgląd. Nadal nie deterministyczny (może być ich kilkaA-produkcje, które się rozpoczynają a).
vonbrand,