Języki, automaty i obliczenia/Wykład 12: Języki kontekstowe i automat liniowo ograniczony. Maszyna Turinga

W tym wykładzie omówimy języki i gramatyki kontekstowe oraz ich własności. Wprowadzimy automat liniowo ograniczony i uzasadnimy równość rodziny języków kontekstowych i rodziny języków rozpoznawanych przez automaty liniowo ograniczone. Zdefiniujemy maszynę Turinga i pokażemy równoważność tego modelu z wybranymi innymi modelami obliczeń.

W tym wykładzie omówimy kolejną rodzinę języków hierarchii Chomsky'ego, a mianowicie języki kontekstowe. Przedstawimy kilka własnosci gramatyk kontekstowych, czyli typu (1) oraz wprowadzimy pojęcie automatu liniowo ograniczonego. Wprowadzimy też najogólniejszy model obliczeń, a mianowicie maszynę Turinga.

1. Języki kontekstowe

Języki kontekstowe to kolejna rodzina języków w hierarchii Chomsky'ego. Rozszerza ona istotnie rodzinę języków bezkontekstowych. Wykorzystanie tej rodziny języków formalnych jest dość ograniczone. Brak jest bowiem praktycznych metod konstrukcji parserów dla tych gramatyk.

Ta część wykładu prezentuje gramatyki równoważne gramatykom kontekstowym, posiadające pewne określone własności. Te własności wykorzystuje się przy uzasadnieniu faktu, że rodzina języków kontekstowych pokrywa się z rodziną języków rozpoznawanych przez automaty liniowo ograniczone. Biorąc pod uwagę to, że zastosowania tej rodziny języków formalnych nie są powszechne oraz to, że dowody dla przedstawionych poniżej twierdzeń są mocno techniczne, postanowiliśmy zrezygnować z rygorystycznej prezentacji tego materiału i pominąć dowody. Zainteresowany Student może je znaleźć w literaturze wskazanej do tego przedmiotu.

Definicja 1.1

Gramatykę $G=(V_N,V_T,v_0,P)$ nazywamy rozszerzającą, jeśli każde prawo jest postaci $x\to y$ , gdzie $x,y\in (V_N\cup V_T{)}^{*}$ i spełniona jest nierówność $\mid x\mid ⩽\mid y\mid$ lub jest to prawo $v_0\to 1$ i wtedy $v_0$ nie występuje po prawej stronie w żadnej produkcji z $P$ .

Wprost z definicji wynika, że gramatyka kontekstowa jest gramatyką rozszerzającą. Prawdziwe jest również następujące twierdzenie.

Twierdzenie 1.1

Dla dowolnej gramatyki $G=(V_N,V_T,v_0,P)$ rozszerzającej istnieje równoważna gramatyka kontekstowa.

Wprowadzimy teraz gramatyki z markerem końca.

Definicja 1.2

Gramatyką z markerem końca $\mathrm{♯}$ nazywamy gramatykę $G_{\mathrm{♯}}=(V_N\cup \{\mathrm{♯}\},V_T,v_0,P)$ taką, że $\mathrm{♯}\notin V_N\cup V_T$ oraz prawa są postaci: $u\to v$ , $\mathrm{♯}u\to \mathrm{♯}v$ lub $u\mathrm{♯}\to v\mathrm{♯}$ , gdzie $u,v\in (V_N\cup V_T{)}^{*}$ i w słowie $u$ występuje co najmniej jeden symbol nieterminalny z $V_N$ . Językiem generowanym przez tę gramatykę nazywamy zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(G_{\sharp })=\{w\in V_{T}^{*}:\: \sharp v_{0}\sharp \mapsto^{*}\sharp w\sharp \}. }

Gramatyka z markerem końca $G_{\mathrm{♯}}$ jest kontekstowa (typu $1$ ), jeśli jej prawa po wymazaniu markera $\mathrm{♯}$ spełniają warunki gramatyki rozszerzającej. Oczywiście dla dowolnej gramatyki kontekstowej istnieje równoważna gramatyka kontekstowa z markerem końca. Prawdziwe jest również następujące twierdzenie:

Twierdzenie 1.2

Dla dowolnej gramatyki kontekstowej z markerem końca istnieje równoważna gramatyka kontekstowa.

Dowód

Niech $G_{\mathrm{♯}}=(V_N\cup \{\mathrm{♯}\},V_T,v_0,P)$ będzie dowolną gramatyką kontekstową z markerem końca. Zakładamy, bez ograniczania ogólności rozważań, że w zbiorze $P$ nie występuje prawo $v_0\to 1$ (po wymazaniu markera $\mathrm{♯}$ ). Dla każdego symbolu $x$ ze zbioru $V=V_N\cup V_T$ określamy trzy symbole Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \, ^{\sharp }x,x^{\sharp },^{\: \sharp }x^{\sharp } } oraz oznaczamy odpowiednio przez ${}^{\mathrm{♯}}V,V^{\mathrm{♯}}{,}^{\mathrm{♯}}{V}^{\mathrm{♯}}$ zbiory tych symboli. Dla $u=u_1...u_k$ takiego, że $k⩾1$ i $u_i\in V$ dla $i=1,...,k$ wprowadzamy także następujące oznaczenia:

${}^{\mathrm{♯}}u={}^{\mathrm{♯}}{u}_1{u}_2...u_k$ , $u^{\mathrm{♯}}=u_1...u_{k-1}{u}_k^{\mathrm{♯}}$ oraz ${}^{\mathrm{♯}}{u}^{\mathrm{♯}}={}^{\mathrm{♯}}{u}_1{u}_2...u_{k-1}{u}_k^{\mathrm{♯}}$ gdy $k>1$ .

Przy takich oznaczeniach definiujemy gramatykę

$G_1=(V_N\cup {}^{\mathrm{♯}}V\cup V^{\mathrm{♯}}{\cup }^{\mathrm{♯}}{V}^{\mathrm{♯}},V_T,{}^{\mathrm{♯}}{v}_0^{\mathrm{♯}},P_1),$

w której zbiór praw $P_1$ składa się ze wszystkich praw uzyskanych zgodnie z poniższymi warunkami:

1. jeśli $u\to w\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u\rightarrow w,\: ^{\#}u\rightarrow \, ^{\#}w,\: u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1}, }
2. jeśli ${}^{\mathrm{\#}}u\to {}^{\mathrm{\#}}w\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \: u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1}, }
3. jeśli $u^{\mathrm{\#}}\to w^{\mathrm{\#}}\in P$ , to Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u^{\#}\rightarrow w^{\#},\: ^{\#}u^{\#}\rightarrow \, ^{\#}w^{\#}\in P_{1}, }
4. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \, ^{\#}x\rightarrow x,\: x^{\#}\rightarrow x,\: ^{\#}x^{\#}\rightarrow x\in P_{1} }

dla wszystkich $x\in V$ .

Określona w ten sposób gramatyka $G_1$ jest gramatyką rozszerzającą i równoważną wyjściowej. Dla gramatyki $G_1$ istnieje, zgodnie z poprzednim twierdzeniem, równoważna gramatyka kontekstowa, co kończy dowód twierdzenia.

Prawdziwe jest także następujące twierdzenie (porównaj z 1.1).

Twierdzenie 1.3

Dla dowolnej gramatyki kontekstowej (rozszerzającej) istnieje równoważna gramatyka kontekstowa (rozszerzająca) o tej własności, że każde prawo, w którym występuje symbol terminalny, jest postaci $v\to a$ , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in V_{N},\: a\in V_{T} } .

Mówimy, że gramatyka $G$ jest rzędu $n>0$ , jeśli dla każdego prawa $x\to y$ tej gramatyki spełniony jest warunek $\mid x\mid ⩽n$ i $\mid y\mid ⩽n$ . Kolejne twierdzenie stwierdza możliwość dalszego uproszczenia praw gramatyki rozszerzającej.

Twierdzenie 1.4

Dla każdej gramatyki rozszerzającej istnieje równoważna gramatyka rozszerzająca rzędu $2$ .

Na koniec wprowadzimy jeszcze jeden rodzaj gramatyk równoważnych gramatykom kontekstowym. Są to mianowicie gramatyki liniowo ograniczone.

Definicja 1.3

Gramatyka $G=(V_N,V_T,v_0,P)$ jest liniowo ograniczona, jeśli każde prawo jest jednej z następujących postaci:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v_{0}\rightarrow v_{0}v,\: v_{1}v_{2}\rightarrow z_{1}z_{2},\: v\rightarrow x, }

gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle x\in V_{N}\cup V_{T},\: v,v_{1},v_{2},z_{1},z_{2}\in V_{N} } oraz $v_0\notin \{x,z_1,z_2,v\}$ .

Twierdzenie 1.5

Dla dowolnej gramatyki kontekstowej $G$ istnieje gramatyka liniowo ograniczona $G_1$ , która jest równoważna $G$ lub też generuje język $L(G)\setminus \{1\}$ .

Dowód

W świetle poprzednich twierdzeń możemy przyjąć, że gramatyka kontekstowa $G=(V_N,V_T,v_0,P)$ ma prawa wyłącznie w następujących postaciach:

1. $v_0\to 1,$
2. $v\to x$ gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle v\in V_{N},\: x\in V_{N}\cup V_{T}, }
3. $v\to v_1{v}_2$ gdzie $v,v_1,v_2\in V_N,$
4. $v_1{v}_2\to v_3{v}_4$ gdzie $v_1,v_2,v_3,v_4\in V_N.$

Określamy gramatykę $G_1=(V_N\cup \{z_0,z_1\},V_T,z_0,P_1)$ , gdzie $z_1,z_2$ są nowymi symbolami nieterminalnymi, a więc nie należą do $V_N$ . Natomiast zbiór praw $P_1$ składa się ze wszystkich praw ze zbioru $P$ postaci 2 i 4 oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle z_{0}\rightarrow z_{0}z_{1},\: z_{0}\rightarrow v_{0},\: } praw Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle z_{1}v\rightarrow vz_{1},\: vz_{1}\rightarrow z_{1}v } dla $v\in V_N$ i praw $v_1{z}_1\to v_3{v}_4$ dla każdego prawa postaci 4 w gramatyce $G$ . Skonstruowana gramatyka jest liniowo ograniczona i spełnia tezę twierdzenia.

2. Automat liniowo ograniczony

Określimy teraz systemy, zwane automatami liniowo ograniczonymi, który rozpoznają języki kontekstowe.

Definicja 2.1

Automatem liniowo ograniczonym nazywamy system ${{𝒜}}_{LO}=({\mathrm{\Sigma }}_T,S,P,s_0,S_F)$ , w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem taśmy, a ${\mathrm{\Sigma }}_I$ - alfabetem wejściowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan początkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów końcowych. Natomiast relacja przejść $P\subset (S\times {\mathrm{\Sigma }}_T)\times (S\times {\mathrm{\Sigma }}_T\times \{-1,0,1\})$ spełnia następujące warunki:

1. jeśli $(s_1,\mathrm{\#})P(s_2,a,k)$ , to $a=\mathrm{\#},$
2. jeśli $(s_1,a)P(s_2,\mathrm{\#},k)$ , to $a=\mathrm{\#}.$

Fakt, że $(s_1,a)P(s_2,b,k)$ , zapisujemy zazwyczaj jako $(s_1,a)\to (s_2,b,k)$ . Do opisu działania automatu liniowo ograniczonego wygodnie jest wprowadzić pojęcie konfiguracji (podobnie jak dla automatów ze stosem).

Konfiguracją automatu liniowo ograniczonego jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ . Pomiędzy dwoma konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}:$

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $(s_1,a)P(s_2,b,0),$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $(s_1,a)P(s_2,b,1),$
3. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $(s_1,a)P(s_2,b,-1).$

Przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez automat liniowo ograniczony.

Język rozpoznawany przez automat liniowo ograniczony ${{𝒜}}_{LO}$ to zbiór słów nad alfabetem ${\mathrm{\Sigma }}_I$ , pod działaniem których automat wykonuje obliczenie prowadzące do stanu końcowego, czyli

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathcal{A}_{LO})=\left\{ w\in \Sigma _{I}^{*}\: :\: s_{0}\#w\#\mapsto^{*}vs,\; v\in \Sigma _{T}^{*},\, s\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez automat liniowo ograniczony, jeśli istnieje automat ${{𝒜}}_{LO}$ taki, że ${ℒ}({{𝒜}}_{LO})=L.$

<flash>file=Wyklad12_rysunek1.swf|width=200|height=200</flash> <div.thumbcaption>Rysunek 1

Opiszemy teraz możliwe ruchy automatu liniowo ograniczonego. Automat ten może czytać słowo wejściowe w dwóch kierunkach. Jego głowica może poruszać się w lewo lub w prawo. Automat może wymieniać czytaną literę na inną, ale nie rozszerza miejsca zajętego na taśmie przez czytane słowo. Działa niedeterministycznie. Czytając literę $a$, będąc w stanie $s$, automat ma kilka możliwości działania. Może mianowicie:

1. zamienić literę na inną literę i/lub zmienić stan na inny - zgodnie z warunkiem 1. Głowica czytająca automatu pozostaje w poprzedniej pozycji,
2. zamienić literę na inną literę i/lub zmienić stan na inny - zgodnie z warunkiem 2. Głowica czytająca automatu przesuwa się w prawo,
3. zamienić literę na inną literę i/lub zmienić stan na inny - zgodnie z warunkiem 3. Głowica czytająca automatu przesuwa się w lewo.

Związek pomiędzy rodziną języków kontekstowych a wprowadzoną rodziną automatów liniowo ograniczonych ustalają poniższe twierdzenia.

Twierdzenie 2.1

Dla dowolnego języka kontekstowego $L$ istnieje automat liniowo ograniczony ${{𝒜}}_{LO}$ taki, że ${ℒ}({{𝒜}}_{LO})=L$ .

Dowód

Można założyć, bez ograniczenia ogólności naszych rozważań, że gramatyka $G=(V_N,V_T,v_0,P)$ generująca język $L$ ma prawa wyłącznie następujących postaci:

1. (G) $v\to x$ , gdzie $v\in V_N,x\in V_N\cup V_T,x\ne v_0,$
2. (G) $v_0\to v_0{v}_1$ , gdzie $v_1\in V_N,v_1\ne v_0,$
3. (G) $v_1{v}_2\to v_3{v}_4$ , gdzie $v_1,...,v_4\in V_N,v_3,v_4\ne v_0,$
4. (G) $v_0\to 1,$ jeśli $1\in L$ .

Określamy automat liniowo ograniczony ${{𝒜}}_{LO}=({\mathrm{\Sigma }}_T,S,P,s_0,S_F)$ , przyjmując ${\mathrm{\Sigma }}_T=V_N\cup V_T\cup \{\mathrm{\#},\mathrm{♭}\}$ , $S=\{s_0,s_1,s_2,s_3,s_4\}\cup \{s_{v_1}:v_1{v}_2\to v_3{v}_4\in P\}$ , ${\mathrm{\Sigma }}_I=V_N\cup V_T$ , $S_F=\{s_3\}$ , $s_0$ - stan początkowy. Relacja przejść automatu ${{𝒜}}_{LO}$ zdefiniowana jest poniżej:

1. (A) $(s_0,\mathrm{\#})\to (s_0,\mathrm{\#},1),$
2. (A) $(s_0,\mathrm{\#})\to (s_4,\mathrm{\#},1)$ jeśli $1\in L,$
3. (A) $(s_0,x)\to (s_0,x,1)$ , $(s_0,x)\to (s_0,x,-1)$ dla każdego $x\in V_N\cup V_T,$
4. (A) $(s_0,x)\to (s_0,v,0)$ jeśli $v\to x\in P$ i $x\ne v_0,$
5. (A) $(s_0,v_3)\to (s_{v_1},v_1,1),(s_{v_1},v_4)\to (s_0,v_2,0)$ jeśli $v_1{v}_2\to v_3{v}_4\in P,$
6. (A) $(s_0,v_0)\to (s_1,v_0,-1),$
7. (A) $(s_1,\mathrm{\#})\to (s_2,\mathrm{\#},1),$
8. (A) $(s_1,\mathrm{♭})\to (s_2,\mathrm{♭},1),$
9. (A) $(s_2,v_0)\to (s_3,\mathrm{♭},1),$
10. (A) $(s_3,v_1)\to (s_0,v_0,0)$ , gdy $v_0\to v_0{v}_1\in P,$
11. (A) $(s_3,\mathrm{\#})\to s_3,\mathrm{\#},1),(s_4,\mathrm{\#})\to (s_3,\mathrm{\#},1).$

Określony automat ${{𝒜}}_{LO}$ rozpoznaje tylko te słowa, które są generowane przez gramatykę $G$ , symulując wstecz każde wyprowadzenie gramatyki $G$ .

Prawdziwe jest również następujące twierdzenie.

Twierdzenie 2.2

Dla dowolnego języka $L$ rozpoznawanego przez automat liniowo ograniczony ${{𝒜}}_{LO}$ istnieje gramatyka kontekstowa $G$ taka, że $L(G)=L$ .

W dowodzie konstruuje się odpowiednią gramatykę.Zasada tej konstrukcji jest następująca. Z symbolu startowego gramatyka generuje dowolne słowa, ustawiając zawsze na prawym końcu symbol nieterminalny związany z przejściem automatu do stanu końcowego. Następnie korzysta się z możliwości zamiany takiego symbolu nieterminalnego na inne. W ten sposób gramatyka symuluje wstecz działanie automatu, wprowadzając symbole nieterminalne odpowiadające stanom automatu. Dojście do stanu początkowego automatu w tej symulacji jest równoznaczne z usunięciem ostatniego symbolu nieterminalnego i wygenerowaniem słowa dokładnie tego samego, które rozpoznaje automat.

Udowownimy teraz zamkniętość rodziny języków kontekstowych ze względu na iloczyn mnogościowy.

Twierdzenie 2.3

Dla dowolnych języków kontekstowych $L_1,L_2\subset A^{*}$ iloczyn mnogościowy tych języków $L_1\cap L_2$ jest językiem kontekstowym.

Dowód

(szkic) Załóżmy, że języki $L_1,L_2$ są rozpoznawane przez automaty liniowo ograniczone, ${{𝒜}}_{LO}^1$ i ${{𝒜}}_{LO}^2$ . Opiszemy konstrukcję automatu liniowo ograniczonego ${{𝒜}}_{LO}$ , który rozpoznawać będzie wyłącznie słowa akceptowane równocześnie przez oba automaty. Działanie tego automatu jest następujące. Każde słowo będzie czytane trzy razy. Przy pierwszym czytaniu automat ${{𝒜}}_{LO}$ dubluje litery, to znaczy w miejsce litery $a$ wprowadza parę $(a,a)$ . Po zakończeniu tej procedury automat wraca do skrajnej lewej pozycji i rozpoczyna symulację automatu ${{𝒜}}_{LO}^1$ . Jeśli ta symulacja doprowadzi do zaakceptowania czytanego słowa przez automat ${{𝒜}}_{LO}^1$ , to automat ${{𝒜}}_{LO}$ rozpoczyna obliczenie od początku, symulując teraz pracę automatu ${{𝒜}}_{LO}^2$ . Jeśli i ta symulacja zakończy się zaakceptowaniem czytanego słowa, to automat przechodzi do ustalonego stanu końcowego, a to oznacza akceptację tego słowa. Działając w opisany sposób, automat ${{𝒜}}_{LO}$ rozpoznaje język $L_1\cap L_2$ , a to w świetle udowodnionego powyżej twierdzenia oznacza, że przecięcie języków kontekstowych $L_1\cap L_2$ jest językiem kontekstowym.

Ponieważ dalsze własności domkniętości rodziny języków kontekstowych pokrywają się z własnościami języków typu (0), więc omówimy te własności wspólnie, co będzie mieć miejsce w następnym wykładzie.

3. Maszyna Turinga

Alan Turing (1912-1954)
Zobacz biografię

Przejdziemy teraz do prezentacji ogólnego modelu

maszyny liczącej, który został wprowadzony w 1936 roku przez Alana M. Turinga. Na cześć swego autora został on nazwany (jednotaśmową) maszyną Turinga. Model ten jest podobny w swojej idei do rozważanych wcześniej automatów liniowo ograniczonych, przy czym jednym z podstawowych założeń (i różnic względem automatów) jest nieskończony dostęp do pamięci. Maszyna Turinga może wydawać się na początku pojęciem bardzo abstrakcyjnym. Jednak, jak później zobaczymy, stanowi ona jedną z podstawowych koncepcji współczesnej informatyki. Pozwala na formalne zdefiniowanie pojęcia algorytmu oraz jego złożoności obliczeniowej. Jako model obliczeń pozwala odpowiedzieć także na bardzo ważne pytanie: czy każdy problem można rozwiązać algorytmicznie?

Jednotaśmowa maszyna Turinga jest podobna w swej idei do automatu liniowo ograniczonego, pominięte jednak zostaje, jak wspomnieliśmy, ograniczenie dostępu do pamięci. Omawiana maszyna jest abstrakcyjnym tworem w skład którego wchodzą:

• dwustronnie nieskończona taśma zbudowana z komórek zawierających symbole z pewnego zadanego alfabetu,
• głowica, która może czytać i zapisywać symbole w komórkach taśmy oraz poruszać się w prawo lub lewo o jedną komórkę lub pozostawać na tej samej pozycji podczas jednego kroku czasowego,
• działający sekwencyjnie mechanizm odpowiedzialny za sterowanie maszyną; mechanizm ten na podstawie symbolu odczytanego z komórki pod głowicą oraz stanu, w którym aktualnie znajduje się maszyna, dokonuje zapisu symbolu w tejże komórce, przechodzi do kolejnego stanu i przesuwa głowicę w prawo, lewo lub też nie zmienia pozycji głowicy.

Podamy teraz formalną definicję maszyny Turinga. Aby zachować analogię do poprzednich wykładów, zdefiniujemy maszynę w języku konfiguracji.

Definicja 3.1

(Jednotaśmowa deterministyczna) maszyna Turinga jest to system $\mathbf{𝐌}\mathbf{𝐓}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ , w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem taśmy, a ${\mathrm{\Sigma }}_I$ - alfabetem wejściowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan początkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów końcowych. Natomiast funkcja przejść jest funkcją częściową Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma _{T})\rightarrow (S\times \Sigma _{T}\times \{-1,0,1\} } .

Konfiguracją maszyny Turinga jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ . Pomiędzy dwiema konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}$:

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $f(s_1,a)=(s_2,b,0),$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $f(s_1,a)=(s_2,b,1)$ i $w\ne 1,$
3. $d_1=v{s}_1\mathrm{\#}$ , $d_2=vb{s}_2\mathrm{\#}$ oraz $f(s_1,\mathrm{\#})=(s_2,b,1),$
4. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $f(s_1,a)=(s_2,b,-1),$
5. $d_1=s_1\mathrm{\#}w$ , $d_2=s_2\mathrm{\#}bw$ oraz $f(s_1,\mathrm{\#})=(s_2,b,-1).$

Przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez maszynę Turinga. Konfiguracja $d_1\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ jest końcowa, jeśli stąd, że $d_1\mapsto d_2$ , wynika $d_2=d_1.$ Mówimy, że maszyna Turinga zatrzymuje się w $d_1$ wtedy i tylko wtedy, gdy $d_1$ jest konfiguracją końcową.

Zauważmy, że wprowadzenie markera końca jest zabiegiem czysto formalnym. Pozwala on z jednej strony na oznaczenie słowa wejściowego, a z drugiej strony wskazuje na elementy taśmy, które były zmieniane (czy to przez wprowadzenie słowa wejściowego, czy też poprzez ruch głowicy).

Definicja 3.2

Język rozpoznawany przez maszynę Turinga $MT$ jest to zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathbf{MT})=\left\{ w\in \Sigma _{T}^{*}\: :\: \sharp s_{0}w\sharp \mapsto^{*}\sharp w_{1}s_{F}w_{2}\sharp ,\; dla\: pewnych\: w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez maszynę Turinga, jeśli istnieje $MT$ taka, że $L({ℳ}{𝒯})=L.$ Klasę języków rozpoznawanych przez maszynę Turinga oznaczamy ${ℒ}(MT)$ .

We wprowadzonym przez nas ujęciu formalnym, działanie maszyny Turinga należy wyobrażać sobie następująco. W pierwszym etapie na taśmę zostają zapisane symbole słowa wejściowego (z alfabetu ${\mathrm{\Sigma }}_I$), a następnie komórki przyległe zostają oznaczone symbolami $\mathrm{♯}$. Jednocześnie maszyna jest sprowadzana do stanu $s_0$, a głowica zostaje ustawiona nad pierwszym symbolem słowa wejściowego. W tym momencie rozpoczyna się sekwencyjne przetwarzanie zawartości taśmy przez maszynę. Jeśli maszyna "zatrzyma się", tzn. w dwóch kolejnych chwilach czasowych nie wykona ruchu i jednocześnie nie zmieni stanu i symbolu taśmy, sprawdzany jest jej aktualny stan. Jeśli stan był akceptujący (czyli należał do zbioru $S_F$), to maszyna zaakceptowała słowo, w przeciwnym razie - słowo odrzuciła (gdyż nie może już osiągnąć stanu ze zbioru $S_F$). Należy zwrócić uwagę na to, że dla niektórych konfiguracji początkowych maszyna może nigdy się nie zatrzymać, a mimo to słowo zostanie przez nią zaakceptowane. To samo tyczy się odrzucania słów, jednak w tej sytuacji dowód, że słowo nie zostanie zaakceptowane, może być problematyczny. Zaprezentowane podejście ma na celu uproszczenie i tak już dość technicznych dowodów twierdzeń pojawiających się w tym wykładzie. Związki pomiędzy akceptowaniem a zatrzymywaniem maszyny Turinga zostaną skomentowane później (zob. Wniosek 4.1). W pierwszej kolejności przedstawiamy dwa przykłady:

Przykład 3.1

Skonstruujemy maszynę Turinga $M{T}_1$, która rozpoznaje język postaci $L=\{0^{2^n}:n⩾0\}$. Zamierzone działanie maszyny $M{T}_1$ można opisać następująco:

1. Przejdź od lewego markera do prawego, zaznaczając symbolem $\mathrm{♢}$ co drugie $0$.
2. Jeśli było tylko jedno $0$, to akceptuj.
3. Jeśli w kroku 1. obszar pomiędzy markerami zawierał nieparzystą ilość $0$, to odrzuć.
4. Powróć do lewego markera.
5. Powtórz działanie od 1.

Zwróćmy uwagę, że o ile jasne jest, w jaki sposób maszyna ma akceptować słowa wejściowe, odrzucanie tych słów nie zostało zdefiniowane. Aby ominąć ten problem, wprowadzimy jeden dodatkowy stan (nie należący do stanów końcowych), po osiągnięciu którego maszyna się zatrzymuje (tzn. nie wykonuje ruchów i przepisuje na taśmie wciąż ten sam symbol).

Określamy kolejno elementy składowe maszyny $M{T}_1$:

${\mathrm{\Sigma }}_I=\left\{0\right\},{\mathrm{\Sigma }}_T=\{0,\mathrm{♢},\mathrm{♣},\mathrm{♯}\},$ $S=\{s_0,s_1,s_2,s_3,s_4,s_A,s_R\},S_F=\left\{s_A\right\}.$

Pozostaje jeszcze zdefiniować funkcję przejść:

$\begin{array}{cc}(s_0,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (s_1,\mathrm{♢})\mapsto (s1,\mathrm{♢},1)\\ (s_0,0)\mapsto (s_1,\mathrm{♣},1)& (s_1,0)\mapsto (s_2,\mathrm{♢},1)\\ & (s_1,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)\\ (s_2,\mathrm{♢})\mapsto (s_2,\mathrm{♢},1)& (s_3,0)\mapsto (s_2,\mathrm{♢},1)\\ (s_2,\mathrm{♯})\mapsto (s_4,\mathrm{♯},-1)& (s_3,\mathrm{♢})\mapsto (s_3,\mathrm{♢},1)\\ (s_2,0)\mapsto (s_3,0,1)& (s_3,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)\\ (s_4,0)\mapsto (s_4,0,-1)& \\ (s_4,\mathrm{♢})\mapsto (s_4,\mathrm{♢},-1)& \\ (s_4,\mathrm{♣})\mapsto (s_2,\mathrm{♣},1)& \\ (s_A,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& (s_R,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)\end{array}$

W miejsce tabeli wygodniej jest zobrazować funkcję przejść maszyny Turinga na etykietowanym grafie skierowanym. Zostało to zrobione na poniższym rysunku:

<flash>file=ja-lekcja12-w-rys1.swf|width=350|height=350</flash>

<div.thumbcaption>Rysunek 2

Łatwo zauważyć, że wprowadzona funkcja przejścia określa maszynę spełniającą postawione przez nas warunki. Symbol $\mathrm{♣}$ został wprowadzony dla odróżnienia wystąpienia pojedynczego zera od sytuacji, gdy liczba zer jest nieparzysta i większa od $1$.

Aby lepiej zrozumieć działanie maszyny $M{T}_1$, zasymulujemy jej działanie na dwóch słowach wejściowych, przy czym pierwsze z nich będzie należało do języka $L$, a drugie nie:

$\begin{array}{cccccccc}& \mathrm{♯}{s}_{0}0000\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_{1}000\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_{2}00\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}0s_{3}0\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}0\mathrm{♢}{s}_2\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}0s_4\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_{4}0\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_4\mathrm{♢}0\mathrm{♢}\mathrm{♯}\\ \mapsto & \mathrm{♯}{s}_4\mathrm{♣}\mathrm{♢}0\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_1\mathrm{♢}0\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_{1}0\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}{s}_2\mathrm{♢}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}\mathrm{♢}{s}_2\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}{s}_4\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_4\mathrm{♢}\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_4\mathrm{♢}\mathrm{♢}\mathrm{♢}\mathrm{♯}\\ \mapsto & \mathrm{♯}{s}_4\mathrm{♣}\mathrm{♢}\mathrm{♢}\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_1\mathrm{♢}\mathrm{♢}\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_1\mathrm{♢}\mathrm{♢}\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}{s}_1\mathrm{♢}\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}\mathrm{♢}{s}_1\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}\mathrm{♢}{s}_A\mathrm{♯}& \circlearrowleft \end{array}$

Wykazaliśmy więc, że $\mathrm{♯}{s}_{0}0000\mathrm{♯}{\mapsto }^{*}\mathrm{♯}\mathrm{♣}\mathrm{♢}\mathrm{♢}\mathrm{♢}{s}_A\mathrm{♯}$. Zatem $0^4\in L(M{T}_1)$.

<flashwrap>file=ja-lekcja12-w-anim1a.swf|size=small</flashwrap>

<div.thumbcaption>Animacja 1

Dla porównania:

$\begin{array}{cccccccc}& \mathrm{♯}{s}_{0}000\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}{s}_{1}00\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}{s}_{2}0\mathrm{♯}& \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}0s_3\mathrm{♯}\\ \mapsto & \mathrm{♯}\mathrm{♣}\mathrm{♢}0s_R\mathrm{♯}& \circlearrowleft \end{array}$

Czyli zgodnie z naszym założeniem $0^3\in ̸L(M{T}_1)$.

<flashwrap>file=ja-lekcja12-w-anim1b.swf|size=small</flashwrap>

<div.thumbcaption>Animacja 2

Przykład 3.2

Przedstawimy maszynę Turinga $M{T}_2$ akceptującą język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{w \overleftarrow{w} \: : \: w\in \left\{0,1\right\}^*\right\}, }

gdzie $\overleftarrow{w}$ oznacza lustrzane odbicie słowa $w$. Elementy języka $L$ nazywamy palindromami. Definiujemy alfabet maszyny:

${\mathrm{\Sigma }}_I=\{0,1\},{\mathrm{\Sigma }}_T=\{0,1,\mathrm{♯}\},$

oraz zbiory stanów

$S=\{s_0,r_0,{r_0}^{\prime },q_0,r_1,{r_1}^{\prime },q_1,l,s_A,s_R\},S_F=\left\{s_A\right\}.$

Funkcję przejść maszyny $M{T}_2$ określa tabela:

$\begin{array}{ccc}(s_0,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& (s_0,0)\mapsto (r_0,\mathrm{♯},1)& (s_0,1)\mapsto (r_1,\mathrm{♯},1)\\ (r_0,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (r_0,0)\mapsto ({r_0}^{\prime },0,1)& (r_0,1)\mapsto ({r_0}^{\prime },1,1)\\ ({r_0}^{\prime },\mathrm{♯})\mapsto (q_0,\mathrm{♯},-1)& ({r_0}^{\prime },0)\mapsto ({r_0}^{\prime },0,1)& ({r_0}^{\prime },1)\mapsto ({r_0}^{\prime },1,1)\\ & (q_0,0)\mapsto (l,\mathrm{♯},-1)& (q_0,1)\mapsto (s_R,\mathrm{♯},-1)\\ (r_1,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& (r_1,0)\mapsto ({r_1}^{\prime },0,1)& (r_1,1)\mapsto ({r_1}^{\prime },1,1)\\ ({r_1}^{\prime },\mathrm{♯})\mapsto (q_1,\mathrm{♯},-1)& ({r_1}^{\prime },0)\mapsto ({r_1}^{\prime },0,1)& ({r_1}^{\prime },1)\mapsto ({r_1}^{\prime },1,1)\\ & (q_1,0)\mapsto (s_R,\mathrm{♯},0)& (q_1,1)\mapsto (l,\mathrm{♯},-1)\\ (l,\mathrm{♯})\mapsto (s_0,\mathrm{♯},1)& (l,0)\mapsto (l,0,-1)& (l,1)\mapsto (l,1,-1)\\ (s_R,\mathrm{♯})\mapsto (s_R,\mathrm{♯},0)& & \\ (s_A,\mathrm{♯})\mapsto (s_A,\mathrm{♯},0)& & \end{array}$

co dla przejrzystości zobrazowano na Rysunku 3.

<flash>file=ja-lekcja12-w-rys3.swf|width=500|height=500</flash>

<div.thumbcaption>Rysunek 3

4. Inne możliwe definicje maszyn Turinga

Istnieje kilka możliwych definicji maszyny Turinga, które jak się okazuje są równoważne pod względem możliwości obliczeniowych (tzn. rozpoznają dokładnie tę samą klasę języków). Naszkicujemy kilka wybranych podejść.

4.1 Maszyna wielotaśmowa

W tym modelu zakłada się, że głowica ma do dyspozycji nie tylko jedną, ale wiele taśm, na których może zapisywać i odczytywać symbole. Zakłada się przy tym, że słowo wejściowe znajduje się na pierwszej taśmie. Aby symulować maszynę wielotaśmową na jednej taśmie, należy zamienić alfabet taśmy na alfabet $({\mathrm{\Sigma }}_T{)}^k$, gdzie $k$ oznacza ilość taśm. W tym momencie zapis na taśmie $i$-tej jest realizowany przez zmianę odpowiedniej współrzędnej litery z nowego alfabetu (zob. Rys. 4.a). Czyli w opisywanym przypadku funkcja przejść będzie operowała na następujących zbiorach:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma^k_{T} )\rightarrow (S \times \Sigma^k_{T} \times \{-1,0,1\} ). }

4.2 Taśma jednostronnie nieskończona

Model ten zakłada, że taśma jest ograniczona z jednej ze stron. Różnica w porównaniu z rozważaną przez nas maszyną Turinga polega na tym, że nie jest dozwolone przesuwanie lewego markera (tzn. funkcja przejść nie może zawierać przejść typu punkt 5 definicji 3.1. W tej sytuacji, aby symulować maszynę z taśmą obustronnie nieskończoną na maszynie z taśmą ograniczoną z jednej strony, wystarczy zasymulować taśmę obustronnie nieskończoną poprzez rozszerzenie alfabetu (zob. Rys. 4.b).

<flash>file=ja-lekcja12-w-rys4.swf|width=350|height=350</flash>

<div.thumbcaption>Rysunek 4

4.3 Wielogłowicowa maszyna wielotaśmowa

W tym podejściu zakłada się dodatkowo, że każda z taśm posiada swoją głowicę. Inaczej mówiąc, mamy do czynienia z iloczynem kartezjańskim $k$ niezależnych maszyn jednotaśmowych. Akceptowany język jest w tym momencie $k$-wymiarowy. Oczywiście, słowo postaci $(w,1,\dots ,1)\in ({\mathrm{\Sigma }}_T^{*}{)}^k$ można w naturalny sposób utożsamiać z $w\in {\mathrm{\Sigma }}_T$. Z drugiej strony maszynę wielogłowicową można symulować na jednotaśmowej w następujący sposób:

1. Jako zbiór stanów bierzemy $S^k$.
2. Słowa startowe $w_1,\dots ,w_k$ zapisujemy jako konfigurację początkową maszyny jednotaśmowej w postaci: $\mathrm{♯}(s_0{)}^k\mathrm{\$}\dot{1}{w}_1\mathrm{\$}\dot{2}{w}_2\mathrm{\$}\dots \mathrm{\$}\dot{k}{w}_k\mathrm{\$}.$ Symbole $\mathrm{\$}$ mają za zadanie wirtualnego rozdzielenia taśm. Symbole $\dot{i}$ wskazują na położenie $i$-tej głowicy na taśmie.
3. W trakcie symulacji przechodzimy pomiędzy markerami i wykonujemy przejścia dla kolejnych głowic.

Widać już, że formalne podanie funkcji przejść jest w omawianym przypadku bardzo techniczne. Musimy zapewnić możliwość poszerzania obszaru zapisu na poszczególnych taśmach, co jest realizowane poprzez dopisanie nowego symbolu i przepisywanie przyległych symboli, aż do markera włącznie. Następnie należy wrócić do poprzedniego miejsca zapisu i symulować działanie kolejnych głowic. Wymaga to wprowadzenia sporej liczby stanów pomocniczych. Nie będziemy zagłębiać się w te techniczne szczegóły. Mamy nadzieję że sama idea konstrukcji jest w tym momencie zrozumiała.

Najbardziej ogólna definicja maszyny tego typu dopuszcza dodatkowo, aby głowice mogły przeglądać pozostałe taśmy, dzięki czemu zapewnia się komunikację między głowicami. Symulacja takiej maszyny na jednej taśmie jest podobna w swej idei do metody przedstawionej wcześniej.

4.4 Maszyna niedeterministyczna

Ten typ maszyn ma ogromne znaczenie dla teorii złożoności. Z tego powodu przyglądniemy mu się dokładniej. Różnica pomiędzy niedeterministyczną maszyną Turinga a maszyną deterministyczną polega na tym, że funkcja przejść może pozwalać na kilka różnych przejść na skutek tego samego symbolu czytanego (gdyż funkcja przejść w tym przypadku będzie multi-funkcją).

Definicja 4.1

(Jednotaśmowa) niedeterministyczna maszyna Turinga jest to system $\mathbf{𝐍}\mathbf{𝐌}\mathbf{𝐓}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$, w którym ${\mathrm{\Sigma }}_T$ jest skończonym alfabetem, $S$ skończonym zbiorem stanów, $S\cap {\mathrm{\Sigma }}_T=\mathrm{\varnothing }$ oraz wyróżniony jest podzbiór ${\mathrm{\Sigma }}_I\subset {\mathrm{\Sigma }}_T$ . Podobnie jak poprzednio zbiór ${\mathrm{\Sigma }}_T$ zwany jest alfabetem taśmy, a ${\mathrm{\Sigma }}_I$ - alfabetem wejściowym. Wyróżnione są także: element $\mathrm{\#}\in {\mathrm{\Sigma }}_T\setminus {\mathrm{\Sigma }}_I$ zwany markerem końca, stan początkowy $s_0\in S$ oraz $S_F\subset S$ - zbiór stanów końcowych. Natomiast funkcja przejść jest funkcją częściową Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle f:\: (S\times \Sigma _{T})\rightarrow \mathcal{P}(S\times \Sigma _{T}\times \{-1,0,1\}) } gdzie ${𝒫}(A)$ oznacza zbiór podzbiorów zbioru $A$.

Konfiguracją maszyny Turinga jest słowo $vsw\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ , w którym $s\in S,v,w\in {\mathrm{\Sigma }}_T^{*}$ , przy czym pomiędzy dwiema konfiguracjami $d_1,d_2$ zachodzi relacja bezpośredniego następstwa $d_1\mapsto d_2$ wtedy i tylko wtedy, gdy spełniony jest jeden z niżej wypisanych warunków, gdzie $s_1,s_2\in S$ , $a,b,c\in {\mathrm{\Sigma }}_T$ oraz $v,w\in {\mathrm{\Sigma }}_T^{*}$:

1. $d_1=v{s}_{1}aw$ , $d_2=v{s}_{2}bw$ oraz $f(s_1,a)\ni (s_2,b,0),$
2. $d_1=v{s}_{1}aw$ , $d_2=vb{s}_{2}w$ oraz $f(s_1,a)\ni (s_2,b,1)$ i $w\ne 1,$
3. $d_1=v{s}_1\mathrm{\#}$ , $d_2=vb{s}_2\mathrm{\#}$ oraz $f(s_1,\mathrm{\#})\ni (s_2,b,1),$
4. $d_1=vc{s}_{1}aw$ , $d_2=v{s}_{2}cbw$ oraz $f(s_1,a)\ni (s_2,b,-1),$
5. $d_1=s_1\mathrm{\#}w$ , $d_2=s_2\mathrm{\#}bw$ oraz $f(s_1,\mathrm{\#})\ni (s_2,b,-1).$

Tak jak poprzednio, przechodnie domknięcie relacji $\mapsto$ oznaczać będziemy symbolem ${\mapsto }^{*}$ i określać mianem obliczenia wykonanego przez maszynę Turinga. Konfiguracja $d_1\in ({\mathrm{\Sigma }}_T\cup S{)}^{*}$ jest końcowa, jeśli stąd, że $d_1\mapsto d_2$ , wynika $d_2=d_1.$

Pomimo tego, że postawiona definicja maszyny niedeterministycznej jest bardzo podobna do maszyny deterministycznej, występuje tutaj jedna bardzo istotna różnica. Słowo wejściowe może prowadzić do wielu różnych obliczeń wykonanych, w szczególności jedno z obliczeń może doprowadzać do zatrzymania maszyny, a inne nie.

Przykład maszyny niedeterministycznej podamy później, przy okazji omawiania klas złożoności obliczeniowej.

Definicja 4.2

Język rozpoznawany przez niedeterministyczną maszynę Turinga $NMT$ jest to zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L(\mathbf{NMT})=\left\{ w\in \Sigma _{T}^{*}\: :\: \sharp s_{0}w\sharp \mapsto^{*}\sharp w_{1}s_{F}w_{2}\sharp ,\; dla\: pewnych\: w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\right\} .}

Język $L\subset {\mathrm{\Sigma }}_I^{*}$ jest rozpoznawany (akceptowany) przez niedeterministyczną maszynę Turinga, jeśli istnieje ${𝒩}{ℳ}{𝒯}$ taka, że $L({𝒩}{ℳ}{𝒯})=L.$

Podkreślamy fakt, że aby maszyna niedeterministyczna zaakceptowała słowo wejściowe, wystarczy, aby wśród wszystkich możliwych obliczeń znalazło się co najmniej jedno akceptujące.

Wprost z definicji wynika że każda maszyna deterministyczna jest także maszyną niedeterministyczną, co oznacza, że języki rozpoznawane przez maszyny deterministyczne są zawarte w klasie języków rozpoznawanych przez maszyny niedeterministyczne. Przeciwna inkluzja jest gwarantowana przez następujące twierdzenie.

Twierdzenie 4.1

Dla każdej niedeterministycznej maszyny Turinga ${𝒩}{ℳ}{𝒯}$ istnieje maszyna deterministyczna ${ℳ}{𝒯}$ taka, że

$L({𝒩}{ℳ}{𝒯})=L({ℳ}{𝒯}).$

Dowód

(Szkic). Aby sprawdzić, czy maszyna niedeterministyczna akceptuje dane słowo wejściowe, należy przejrzeć wszystkie możliwe obliczenia wykonywane, tworzące drzewo obliczeń. Poziomy drzewa tworzone są przez kroki czasowe, wierzchołki stanowią obliczenia wykonane w danym kroku czasowym, a gałęzie zadane są przez relację bezpośredniego następstwa. W celu sprawdzenia, czy maszyna akceptuje dane słowo, przeglądamy drzewo obliczeń poziomami (por. algorytm BFS) i akceptujemy, gdy przeglądana konfiguracja była akceptująca. Tą techniką przeglądamy wszystkie możliwe obliczenia wykonane w $1,2,3,\dots$ krokach.

Do dokonania symulacji najwygodniej jest użyć maszyny $3$-głowicowej z możliwością czytania na wszystkich taśmach. Wprowadzamy te taśmy kolejno do przechowywania słowa wejściowego, symulacji działania maszyny niedeterministycznej i adresowania wyboru przejść ze zbioru przejść danego przez funkcję przejść. Symulacja przebiega w czterech krokach:

1. Rozpocznij ze słowem wejściowym $w$ na taśmie $1$ oraz pustymi taśmami $2$ i $3$.
2. Przekopiuj taśmę $1$ na taśmę $2$.
3. Użyj taśmy $2$ do symulacji $w$, wykorzystując taśmę $3$ do wyboru przejść funkcji przejść $f$. Jeśli po wykonaniu skończonego zbioru instrukcji według adresowania z taśmy $3$ otrzymano konfigurację akceptującą, to akceptuj. W przeciwnym razie, przejdź do następnego punktu.
4. Zamień ciąg adresowy na następny w kolejności leksykograficznej. Jeśli zapisany ciąg jest ostatnim możliwym ciągiem adresowym o długości $N$, zapisz na taśmie $3$ pierwszy w kolejności leksykograficznej ciąg adresowy o długości $N+1$ oraz przejdź do $2$.

Wniosek 4.1

Dla każdej maszyny Turinga ${ℳ}{𝒯}$ istnieje maszyna Turinga ${{ℳ}{𝒯}}^{\prime }$ taka, że

$L({ℳ}{𝒯})=L({{ℳ}{𝒯}}^{\prime })$

oraz dla każdego $w\in L({{ℳ}{𝒯}}^{\prime })$ maszyna ${{ℳ}{𝒯}}^{\prime }$ zatrzymuje się na $w$.

Dowód

Wystarczy przerobić maszynę ${ℳ}{𝒯}$ na maszynę niedeterministyczną ${𝒩}{ℳ}{𝒯}$ posiadającą dodatkowy stan $s_A$ oraz taką, że dla każdego stanu ze zbioru $S_F$ pod wpływem dowolnego symbolu z ${\mathrm{\Sigma }}_T$ maszyna ${𝒩}{ℳ}{𝒯}$ posiada dodatkowe przejście do $s_A$, w którym już pozostaje i nic nie zmienia. Stąd widać, że $L({ℳ}{𝒯})=L({𝒩}{ℳ}{𝒯})$.

Twierdzenie 4.1 pozwala na otrzymanie maszyny ${{ℳ}{𝒯}}^{\prime }$ akceptującej ten sam język co ${𝒩}{ℳ}{𝒯}$ z dodatkowym założeniem, że gdy ${𝒩}{ℳ}{𝒯}$ osiąga stan $s_A$, maszyna ${{ℳ}{𝒯}}^{\prime }$ się zatrzymuje. Zauważmy, że stan $s_A$ można osiągnąć tylko dla słów akceptowanych prze ${𝒩}{ℳ}{𝒯}$, a z drugiej strony, każde słowo akceptowane przez ${𝒩}{ℳ}{𝒯}$ prowadzi do co najmniej jednego obliczenia kończącego się w $s_A$.