Czy maszyna Turinga zdecydować języka

Niech Czy istnieje maszyna Turinga R, która decyduje (nie mam na myśli rozpoznać) język L ∅ ?

Wydaje się, że ta sama technika użyta do pokazania, że tutaj powinno działać.$\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$

Oznaczając, prawdopodobnie masz na myśli analizę osiągalności - szukanie ścieżki ze stanu początkowego do stanu akceptacji. Rzeczywiście, język DFA jest pusty, jeśli nie ma takiej ścieżki.

Zacznijmy od przykładu, dlaczego nie udaje się to w bazach TM. Rozważmy TM, że , ignoruje go za wejście, ale pisze na jego taśma przesuwa prawo głowy i przechodzi do stanu q 1 , następnie w q 1 ponownie ignoruje wejście, pisze przesuwa głowę w lewo i przechodzi do q 2 . W q 2 , jeśli czyta a , to pisze a , przesuwa głowę w prawo i wraca do q 1 .$q_0$$a$$q_1$$q_1$$a$$q_2$$q_2$$a$$a$$q_1$

Oznacza to, że maszyna po prostu pisze i zastępców między dwoma stanami ( q 1 i q 2 ) i zawsze ma dwa przyległe A „s na taśmie.$a$$q_1$$q_2$$a$

Teraz dodajemy przejście z które podczas czytania b przechodzi do stanu akceptacji i zatrzymuje się.$q_2$$b$

Język tego komputera jest pusty. Rzeczywiście, bieg zawsze utknie w pętli i nigdy nie przejdzie do stanu akceptacji. Istnieje jednak ścieżka stanu do stanu akceptującego. Co poszło nie tak?$q_1-q_2$

Cóż, intuicyjnie `` stan '' bazy TM nie jest wystarczająco pouczający, aby opisać kontynuację cyklu. Aby uzyskać wszystkie informacje, potrzebujesz konfiguracji bazy TM, która obejmuje stan, pozycję głowy i zawartość taśmy. Jeśli znajdziesz ścieżkę konfiguracji (która jest nazywana uruchomieniem ) do konfiguracji akceptującej, to rzeczywiście język nie jest pusty i jest to warunek iff.

Problem z użyciem analizy osiągalności na wykresie konfiguracji polega na tym, że może być nieskończona. Dlatego decydowanie o pustce językowej jest nierozstrzygalne.

Dlatego też rozpoznawalna jest pustka językowa - możesz wykonać BFS na nieskończonym grafie konfiguracyjnym. Jeśli istnieje ścieżka do stanu akceptacji, w końcu ją znajdziesz. Jeśli jednak tego nie ma, możesz utknąć w nieskończonym poszukiwaniu.

jest nierozstrzygalne z powodutwierdzenia Rice'a, które stwierdza, że ​​nietrywialne właściwości funkcji cząstkowych nie są rozstrzygalne.$A$

1. Istnieje baza TM, która nie przyjmuje żadnego łańcucha. (Który bezpośrednio przechodzi w stan odrzucenia).
2. Istnieje TM, która akceptuje każdy ciąg. (Który bezpośrednio przechodzi w stan akceptacji).

Oznacza to, że funkcje obliczone przez elementy mają nietrywialną właściwość. Stąd A nie podlega rozstrzygnięciu.$A$$A$

jest rozstrzygalne tylko przy założeniu, że DFA są kodowane w specjalny sposób, taki jak tabela przejścia stanu itp. (Nie możemy zdecydować, czy TM akceptuje tylko zwykłe języki, z powodu twierdzenia Rice'a!). W tym przypadku Rice'a twierdzenie nie znajduje zastosowania, ponieważ szczególności kodowanie elementu jest wymagane do podjęcia decyzji o E . Więc nie decydujemy tylko o funkcjach częściowych.$E$$E$

(To znaczy, jeśli problem polegałby na tym, czy dana TM jest DFA - czy DFA obliczalna - a język przez nią akceptowany jest pusty, byłoby nierozstrzygalne na podstawie twierdzenia Rice'a. Zauważ, że w tym przypadku A = E .)$E$$A = E$

Kolejna wskazówka: spróbuj zredukować problem zatrzymania do .$L_\emptyset$

(Oryginalną wskazówką jest użycie twierdzenia Rice'a, ale w tym przypadku bezpośredni dowód jest również dość prosty.)

Lemat 1 : Jeśli L jest nierozstrzygalny, to także uzupełnienie L.

$H_{TM}$$H_{TM}^c$

$H_{TM}$$\{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \}$

$H_{TM}^c$$\{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \}$

$E_{TM}$$\{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \}$

Załóżmy, że $E_{TM}$ jest rozstrzygalne. Zmniejszymy $H_{TM}^c$ do $E_{TM}$$M_{H_{TM}^c}$$H_{TM}^c$$M_{E_{TM}}$$E_{TM}$$H_{TM}^c$$M_{H_{TM}^c}$$H_{TM}^c$

$M_{H_{TM}^c}$$\langle M,x \rangle$

$\qquad$$M_1$

$\qquad$ $\quad$ $M_1$$w$

$\qquad$ $\quad$$M$$x$

$\qquad$ $\quad$$M$

$\qquad$$M_{E_{TM}}$$\langle M_1 \rangle$

$\qquad$$M_{E_{TM}}$

$M_1$$M_1$

$M_1$$w$$M$$x$$M$$x$

$\quad$$M_1$$w$$M$$x$$M_{E_{TM}}$$M_1$$L(M_1) \neq \emptyset$

$\quad$$M$$x$$M_1$$w$$M_{E_{TM}}$$\quad$$M_1$$L(M_1) = \emptyset$

$Correctness$ : od$M_{E_{TM}}$ zawsze postojów (o założeniem)$M_{H_{TM}^c}$ K E T M odrzuca to$M_{H_{TM}^c}$$M_{E_{TM}}$$L(M_1) = \emptyset$$M$$x$
$M_{H_{TM}^c}$$M_{E_{TM}}$$L(M_1) \neq \emptyset$$M$$x$$M_{H_{TM}^c}$$H_{TM}^c$$H_{TM}^c$

$Nb:$

$H_{TM}^c$$E_{TM}$

Redukcja daje:

$\langle M, x \rangle \in H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E_{TM}$

$\qquad$ $R(\langle M,x \rangle)$

$\langle M, x \rangle \notin H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E_{TM}$

$\qquad$ $R(\langle M,x \rangle)$

$A_{TM}= \{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\}$

$R_{TM}$$L_\emptyset$

$R_{TM}$$S_{TM}$$A_{TM}$

$S_{TM}=^{definition}$$\langle M,w\rangle$$M$$w$

1. $M$$w$$M$$M_1$$w$$w$$w$$M_{1}$$M$$w$$M$

2. $R_{TM}$$\langle M_1,w\rangle$

3. $R_{TM}$

$L_\emptyset$$A_{TM}$

E = {| M jest TM, a L (M) = Φ}. Czy można rozpoznać E Turinga?

E jest językiem, aby zaakceptować język E budujemy Maszynę Turinga. Załóżmy, że tworzymy Turing EM dla języka E.

EM zostanie dostarczone jako kodowanie wejściowe innych maszyn Turinga. Jeśli wprowadzona maszyna M zaakceptuje pusty język, będzie to członek języka E, w przeciwnym razie nie będzie on członkiem języka.

Załóżmy, że mamy maszynę Turinga M, musimy sprawdzić, czy akceptuje pusty język. Maszyna Turinga EM ma M i ciągi eps, a, b, aa, bb, ..... EM sprawdzi, czy M może osiągnąć stan końcowy co najmniej na jednym wejściu, a jeśli zaakceptuje co najmniej jedno wejście, to zostaną odrzucone i nie zostaną uwzględnione w języku E. Teraz zobacz możliwość, że TM M dostanie się do pętli, więc M będzie działać dalej i nie mogliśmy zdecydować, czy może zaakceptować, czy nie. Dlatego ten dany język E NIE jest RE.

PS: Myślę, że uzupełnieniem tego podanego języka E będzie RE.