Niech łańcuch wejściowy będzie podany jako . Następnie, jeśli NFA jest obecnie w stanie (i przeczytał wejście do alfabetu ), a następnie przed odczytaniem następnego symbolu wejściowego NFA dzieli się na dwa NFA, z których jeden jest w stanie i inne istnienie w , jeśli istnieje przejście tego typu . Jeśli istnieje cykl tego typu, gdzie są niektóre stany NFA, wtedy nie ma sensu zapamiętywać innego stanu NFA do momentu odczytania danych wejściowych do alfabetu .
Jeśli PDA (niedeterministyczny) jest w stanie (i dane wejściowe są odczytywane do ) i istnieje cykl (gdzie przejście oznacza, że nic później jest odczytywany z wejścia, nic nie jest wyskakujące lub odczytywane ze stosu i alfabetu jest wypychany na stos), a następnie przed odczytaniem następnego alfabetu wejściowego w stanach będzie nieskończony PDA 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 niedeterminizmprzejś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 symboludeterministyczna 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.
Odpowiedzi:
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)=⊥ . GdybyM zawsze 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ę:
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.)
źródło