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

Niech łańcuch wejściowy będzie podany jako $w_1w_2...w_n$. Następnie, jeśli NFA jest obecnie w stanie$r$ (i przeczytał wejście do alfabetu $w_i$ ), 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 \xrightarrow{\epsilon} s$. Jeśli istnieje cykl tego typu$r \xrightarrow{\epsilon} s \xrightarrow{\epsilon} q_1....\xrightarrow{\epsilon} q_k \xrightarrow{\epsilon} r$, gdzie $q_i$ są niektóre stany NFA, wtedy nie ma sensu zapamiętywać innego stanu NFA $r$ do momentu odczytania danych wejściowych do alfabetu $w_i$.

Jeśli PDA (niedeterministyczny) jest w stanie$r$ (i dane wejściowe są odczytywane do $w_i$ ) i istnieje cykl $r \xrightarrow{\epsilon,\epsilon \to a} s \xrightarrow{\epsilon,\epsilon \to a} q_1....\xrightarrow{\epsilon,\epsilon \to a} q_k \xrightarrow{\epsilon,\epsilon \to a} r$ (gdzie przejście $\epsilon,\epsilon \to a$ oznacza, że ​​nic później $w_{i}$ 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 $w_{i+1}$ w stanach będzie nieskończony PDA $r,s,q_1,...q_k$ 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 $\epsilon$przejścia Zakładam więc, że niedeterministyczna maszyna Turinga również czerpie z niej niedeterminizm$\epsilon$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 symbolu$w_{i+1}$deterministyczna 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$\epsilon$ przejścia?

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

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. Gdyby$f$ nie jest zdefiniowany w dniu $x$ wtedy piszemy $f(x) = \bot$. (Więc$f$ 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) = \bot$.

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śli$M$ zatrzymuje się $x$ zatem w stanie akceptacji $M(x)=1$; jeśli zatrzyma się w stanie odrzucenia, to$M(x)=0$; jeśli to się nie zatrzyma, to$M(x)=\bot$. Gdyby$M$zawsze się zatrzymuje, wtedy mówimy, że akceptuje język$L = \{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) = \bot$ 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 $\epsilon$-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$\epsilon$-transitions (choć dowód może przechodzić przez gramatyki bezkontekstowe).

Możesz symulować $\epsilon$- 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.)