Języki, automaty i obliczenia/Wykład 13: Złożoność obliczeniowa.

Sformułujemy definicje podstawowych klas złożoności w języku maszyn Turinga oraz metodę ich porównywania. Przeanalizujemy związki między rodziną języków określonych przez maszyny Turinga a rodziną języków typu (0) z hierarchii Chomsky'ego. Podamy dalsze własności języków kontekstowych i typu (0). Wprowadzimy pojęcie języka rekurencyjnie przeliczalnego oraz przedstawimy tezę Churcha. Następnie omówimy teoretyczne podstawy teorii rozstrzygalności oraz przeanalizujemy kilka problemów nierozstrzygalnych w teorii języków.

Klasy złożoności obliczeniowej

Jednym z podstawowych celów wprowadzania maszyn Turinga jest dążenie do formalnej definicji złożoności obliczeniowej. Na podstawie wcześniejszych uwag możemy utożsamiać akceptację słowa przez maszynę Turinga z jej zatrzymaniem się. Intuicyjnie, można takie zachowanie maszyny Turinga utożsamić z wykonaniem programu, który zwraca odpowiedź "Tak" na postawione przez nas pytanie.

Definicja 1.1

Ustalmy funkcje $t,s:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$. Mówimy, że maszyna Turinga ${ℳ}{𝒯}$ (deterministyczna lub niedeterministyczna) akceptuje słowo $w\in {\mathrm{\Sigma }}_I^{*}$ w czasie $t(|w|)$, jeśli istnieje ciąg $k⩽t(|w|)$ konfiguracji $d_1,d_2,\dots ,d_k$ takich, że $d_1=\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_k=\mathrm{♯}{w}_1{s}_F{w}_2\mathrm{♯}$ dla pewnych $w_1,w_2\in {\mathrm{\Sigma }}_T^{*},s_F\in S_F$ oraz $d_i\mapsto d_{i+1}$ dla $i=1,\dots ,k-1$.

Jeśli istnieje ciąg konfiguracji $d_1\mapsto d_2\mapsto \dots \mapsto d_m$, gdzie $d_1=\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_m$ jest konfiguracją akceptującą (tzn. $d_m=\mathrm{♯}{w}_1{s}_F{w}_2\mathrm{♯}$ dla pewnych $w_1,w_2\in {\mathrm{\Sigma }}_T^{*},s_F\in S_F$) oraz dodatkowo $|d_i|⩽s(|w|)+2$, to mówimy, że maszyna ${ℳ}{𝒯}$ akceptuje słowo $w\in {\mathrm{\Sigma }}_I^{*}$ w pamięci $s(|w|)$.

Mówimy, że język $L$ jest akceptowany w czasie $t(n)$ (pamięci $s(n)$), jeśli istnieje maszyna Turinga ${ℳ}{𝒯}$, dla której $L({ℳ}{𝒯})=L$ oraz każde słowo $w\in L$ jest akceptowane w czasie $t(|w|)$ (pamięci $s(|w|)$ odpowiednio).

Uwaga 1.1

W niektórych podejściach wykorzystuje się, do definicji złożoności pamięciowej, tak zwanych maszyn Turinga off-line. Pomysł polega na tym, aby nie uwzględniać komórek taśmy, z których maszyna czytała informacje, a jedynie te, do których następował zapis. Dzięki temu zabiegowi można w sposób "rozsądny" mówić o akceptacji słowa w pamięci $\log n$ itp. W ujęciu prezentowanym w tym wykładzie zajmujemy się akceptacją w pamięci $n^k$, dla $k⩾1$, zatem nie ma potrzeby dodatkowego definiowania maszyn Turinga off-line.

Definicja 1.2

Oznaczmy przez $Dtime(t(n))$ oraz $Dspace(s(n))$ rodzinę języków akceptowanych w czasie $t(n)$ i odpowiednio pamięci $s(n)$ przez deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych wprowadzamy w identyczny sposób klasy $Ntime(t(n))$ oraz $Nspace(s(n))$.

Określamy następujące klasy złożoności (klasy języków):

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \textbd{P} \displaystyle =\bigcup_{k=0}^\infty Dtime(n^k), &\qquad\qquad& \textbd{NP} \displaystyle =\bigcup_{k=0}^\infty Ntime(n^k), \\ \textbd{PSPACE} \displaystyle =\bigcup_{k=0}^\infty Dspace(n^k), && \textbd{NSPACE} \displaystyle =\bigcup_{k=0}^\infty Nspace(n^k). \endaligned}

Wprost z definicji otrzymujemy zależności P $\subset$ NP oraz PSPACE $\subset$ NPSPACE . W dalszej części wykładu udowodnimy kilka mniej oczywistych zależności.

Przykład 1.1

Rozważmy język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}. }

Język $L\in$ P . Deterministyczna maszyna Turinga $M{T}_3$ akceptująca taki język może wyglądać następująco (zaczynamy od konfiguracji $\mathrm{♯}{s}_{0}w\mathrm{♯}$):

1. Jeśli symbol pod głowicą, to $1$ zamień go na $\mathrm{♯}$. Inaczej odrzuć.
2. Przejdź od lewego ogranicznika do prawego, sprawdzając, czy po $1$ występuje $1$ lub $2$, po $2$ tylko $2$ lub $3$, a po $3$ kolejny symbol $3$ lub ogranicznik. Jeśli ta zależność nie jest spełniona, odrzuć. Gdy osiągniesz ogranicznik wykonaj następny krok.
3. Gdy przed ogranicznikiem nie znajduje się symbol $3$, odrzuć. W przeciwnym razie zamień symbol $3$ na $\mathrm{♯}$, a następnie poruszaj się w lewo, aż dotrzesz do symbolu innego niż $3$ i $\mathrm{♢}$.
4. Jeśli symbol do którego dotarłeś to $2$, zamień go na $\mathrm{♢}$. Sprawdź symbol po lewej. Jeśli to $2$, poruszaj się w prawo aż do ogranicznika. Następnie przejdź do kroku 3.
5. Jeśli dotarłeś do symbolu $1$, poruszaj się w lewo aż do ogranicznika. Zamień symbol $1$ przy ograniczniku na $\mathrm{♯}$, a następnie idź w prawo, zamieniając wszystkie symbole $\mathrm{♢}$ na $2$. Gdy dojdziesz do ogranicznika, przejdź do kroku $3$.
6. Jeśli dotarłeś do ogranicznika, oznacza to, że skasowano już wszystkie symbole $1$. Przejdź w prawo aż do ogranicznika. Jeśli natrafisz na symbol $3$, odrzuć. W przeciwnym przypadku, akceptuj.

Nietrudno zaobserwować, że maszyna $M{T}_3$ przechodzi przez taśmę w prawo i w lewo tyle razy, ile symboli $3$ zawiera taśma oraz wykonuje jeden dodatkowy przebieg na starcie. Zatem słowa z $L$ są akceptowane w czasie ograniczonym wielomianowo.

Przykład 1.2

Rozważmy teraz język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{3^k\: : \: k=i\cdot j } dla pewnych $i,j>1\}.$

Najprostszą metodą uzasadnienia, że $L\in$ NP jest konstrukcja tak zwanej wyroczni. Polega ona na następującej dwuetapowej procedurze:

1. Skonstruuj niedeterministyczną maszynę Turinga (wyrocznia) generującą pewne słowo (certyfikat).
2. Zweryfikuj w sposób deterministyczny spełnienie założeń przez certyfikat.

W naszym przykładzie Etap 1 wygląda następująco:

1. Użyj dwóch taśm. Na pierwszej z nich znajduje się $3^k$.
2. Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając $3$, możesz wypisać $1$ na taśmie drugiej i przejść o jedną komórkę w prawo na taśmie pierwszej lub przejść do następnego kroku. Jeśli dotarłeś do prawego ogranicznika taśmy pierwszej, przejdź do kroku 3.
3. Powróć do początku pierwszej taśmy. Wykonaj sekwencję jak w kroku $2$, z tą różnicą, że teraz na drugiej taśmie wypisuj symbole $2$.
4. Jako ostatnią część tego etapu przekopiuj symbole $3$ z pierwszej taśmy na drugą (po symbolach $1$ i $2$).

W konstrukcji wykorzystaliśmy dwie taśmy, ale oczywiście w nawiązaniu do wcześniejszych uwag, całą konstrukcję można wykonać na jednej taśmie (z odpowiednio rozszerzonym alfabetem i bardziej skomplikowaną funkcją przejść).

Etap 2 polega na weryfikacji, czy na taśmie drugiej znajduje się słowo postaci $1^i{2}^j{3}^k$, gdzie $i,j>1$ oraz $k=i\cdot j$. Jeśli tak, to słowo wejściowe $3^k$ pochodziło z języka $L$ i akceptujemy. Można do tego wykorzystać deterministyczną maszynę Turinga, niemal identyczną z opisaną w przykładzie poprzednim.

Jeśli słowo wejściowe pochodzi z języka $L$, to jedno z obliczeń maszyny niedeterministycznej z Etapu 1. prowadzi do konstrukcji odpowiedniego słowa na drugiej taśmie. Nie wiemy, jaka dokładnie ścieżka obliczeń ma być wykorzystana, ale dla akceptacji języka $L$ nie ma to znaczenia.

Zastanów się, czy da się wykazać, że także $L\in$ P (Ćwiczenie 1.3, do tego wykładu).

Definicja 1.3

Funkcja $s(n)$ jest konstruowalna pamięciowo, jeśli istnieje maszyna Turinga ${ℳ}{𝒯}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$, dla której $d_1{\mapsto }^{*}{d}_2$, gdzie $d_1=\mathrm{♯}{s}_0{1}^n\mathrm{♯}$, $d_2=\mathrm{♯}{s}_1{1}^{s(n)}w\mathrm{♯}$ dla $s_1\in S_F$, $w\in ({\mathrm{\Sigma }}_T\setminus \left\{1\right\}{)}^{*}$ oraz dodatkowo $d_2$ jest konfiguracją końcową.

Inaczej mówiąc, funkcję $s(n)$ nazywamy konstruowalną pamięciowo, jeśli istnieje maszyna Turinga ${ℳ}{𝒯}$, otrzymując na wejściu słowo $w$ długości $|w|=n$, zaznacza na taśmie roboczej $s(n)$ klatek i zatrzymuje się (akceptując słowo $w$).

Przykład 1.3

Funkcja $s(n)=2n$ jest konstruowalna pamięciowo. Maszyna $M{T}_4$, która konstruuje $s(n)$ działa według schematu:

1. Przejdź do prawego markera. Jeśli napotkano symbol inny niż $1$, to odrzuć.
2. Idź w lewo aż do pierwszego symbolu $1$ lub markera $\mathrm{♯}$
3. Jeśli napotkałeś symbol $1$, zamień go na $\mathrm{♣}$ i przejdź do prawego markera. Dopisz do słowa symbol $\mathrm{♣}$ (zwiększając tym samym długość słowa na taśmie o $1$). Następnie powtórz cykl od $2$.
4. Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia $\mathrm{♣}$ na $1$. Następnie wracaj do lewego markera i zatrzymaj się, akceptując.

Twierdzenie 1.1 liniowa kompresja pamięci

Niech będzie dany język $L$ oraz maszyna Turinga ${𝒯}{ℳ}$ akceptująca $L$ w pamięci $s(n)$. Dla dowolnego $\epsilon >0$ istnieje maszyna Turinga ${{𝒯}{ℳ}}^{\prime }$ akceptująca $L$ w pamięci $\max \{n,\epsilon s(n)\}$.

Dowód

(Szkic) Ustalamy liczbę naturalną $k$, dla której $\epsilon k⩾2$. Maszynę ${{𝒯}{ℳ}}^{\prime }$ definiujemy następująco:

1. Przekoduj słowo wejściowe, łącząc po $r$ kolejnych symboli w jeden blok stanowiący nowy symbol na taśmie.
2. Symuluj maszynę ${ℳ}{𝒯}$ na skompresowanej taśmie. Położenie głowicy wewnątrz bloku zakoduj w stanach maszyny ${{ℳ}{𝒯}}^{\prime }$.

Zauważmy, że w kroku $1$. maszyna ${{ℳ}{𝒯}}^{\prime }$ wykorzystuje $n$ komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy zapewnia, że podczas symulowania maszyny ${ℳ}{𝒯}$ nie wykorzystamy więcej niż $\lceil \frac{s(n)}{k}\rceil ⩽\epsilon s(n)$ komórek. Jednocześnie można założyć, że ${{ℳ}{𝒯}}^{\prime }$ akceptuje słowa wejściowe z języka $L$ o długości mniejszej niż $k$ bez symulowania ${ℳ}{𝒯}$.

Twierdzenie 1.2 Savitch

Dla dowolnej funkcji $s(n)$ konstruowalnej pamięciowo spełniającej warunek $s(n)⩾{\log }_{2}n$ prawdziwa jest inkluzja $Nspace(s(n))\subset DSpace(s^2(n))$.

Dowód

Niech ${𝒩}{ℳ}{𝒯}$ będzie niedeterministyczną maszyną Turinga akceptującą język $L=L({𝒩}{ℳ}{𝒯})$ w pamięci $s(n)$. Niech $k(n)$ oznacza liczbę konfiguracji potrzebną do zaakceptowania słowa o długości $n$. Istnieje liczba $c>1$, dla której $k(n)⩽c^{s(n)}$, co z kolei oznacza, że każde słowo o długości $n$ jest akceptowane w $c^{s(n)}$ krokach czasowych.

Rozważmy algorytm:

Algorytm

---

  1  Wejście: słowo $w$ długości $|w|=n$
  2  oblicz $s(n)$
  3  for każda konfiguracja akceptująca $d_A$ dla której $|d_A|⩽s(n)$
  4    do if Test($\mathrm{♯}{s}_{0}w\mathrm{♯}$, $d_A$, $s(n){\log }_{2}c$) then akceptuj

gdzie procedura Test ma następującą postać:

Algorytm Procedure Test($d$,$d^{\prime }$,$i$)

---

  1  if $i=0$ and [ ($d=d^{\prime }$) or ($d\mapsto d^{\prime }$)] then return true
  2    else for każda konfiguracja $d^{″}$ dla której $|d^{″}|⩽s(n)$
  3      do if Test($d$,$d^{″}$,$i-1$) and Test $d^{″}$,$d^{\prime }$,$i-1$)
  4        then return true;
  5  return false

Przedstawiony algorytm można zrealizować za pomocą wielotaśmowej maszyny Turinga. Założenie dotyczące konstruowalności pamięciowej jest istotnie wykorzystywane w tej konstrukcji przy implementacji linii 3 algorytmu i linii 2 procedury Test. Musimy zaznaczyć $s(n)$ komórek taśmy, aby móc konstruować konfiguracje o długości ograniczonej przez $s(n)$ i móc następnie wykonywać na nich symulację maszyny ${𝒩}{ℳ}{𝒯}$.

Zauważmy, że ilość konfiguracji jest ograniczona przez $s(n)$, a głębokość rekursji przez $\log c^{s(n)}$. Oznacza to, że jesteśmy w stanie skonstruować maszynę Turinga, która wymaga $c^{\prime }{s}^2(n)$ pamięci, gdzie $c^{\prime }$ jest pewną stałą. Na mocy Twierdzenia 1.1 jesteśmy w stanie określić maszynę ${ℳ}{𝒯}$ działającą w pamięci $s^2(n)$.

Wniosek 1.1

PSPACE $=$ NPSPACE

Lemat 1.1

Jeśli $g(n)⩾n$, to $Dtime(g(n))\subset Dspace(g(n))$ oraz $Ntime(g(n))\subset Nspace(g(n))$.

Dowód

Niech będzie dana maszyna deterministyczna ${ℳ}{𝒯}$ akceptująca dany język $L$ w czasie $g(n)$. Do akceptacji słowa $w$ o długości $n$ maszyna wykorzystuje co najwyżej $g(n)$ kroków czasowych, czyli odwiedza co najwyżej $g(n)+1$ komórek taśmy.

Na podstawie Twierdzenia 1.1 istnieje maszyna Turinga ${{ℳ}{𝒯}}^{\prime }$ wykorzystująca

$\max \{n,\frac{1}{2}(g(n)+1)\}⩽g(n)$

komórek pamięci. Dla niedeterministycznych maszyn Turinga argumentacja jest identyczna.

Wniosek 1.2

P $\subset$ NP $\subset$ PSPACE $=$ NPSPACE

Uwaga 1.2

Nie jest znany przykład wykazujący silną inkluzję P $⊊$ NP ani dowód wykluczający istnienie takiego przykładu. Powszechnie uznawana hipoteza głosi:

P $\ne$ NP.

Rozstrzygnięcie jej prawdziwości lub fałszywości stanowi jeden z najważniejszych, a zarazem najtrudniejszych problemów współczesnej informatyki. Jak widzieliśmy w Przykładzie 1.2, nawet w przypadku konkretnego języka $L\in$ NP, problem uzasadnienia, że także $L\in$ P, jest nietrywialny, gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż ta do weryfikacji $L\in$ NP .

Redukcja i problemy zupełne

Definicja 2.1 transformacja wielomianowa

Niech $L_1,L_2$ będą dowolnymi językami nad pewnym alfabetem ${\mathrm{\Sigma }}_I$. Mówimy, że $L_1$ redukuje się do $L_2$ w czasie wielomianowym, co oznaczamy $L_1\propto L_2$, gdy istnieje deterministyczna maszyna Turinga ${ℳ}{𝒯}=({\mathrm{\Sigma }}_T,S,f,s_0,S_F)$ taka, że dla dowolnego $w\in {\mathrm{\Sigma }}_I^{*}$ istnieje $w^{\prime }\in {\mathrm{\Sigma }}_I^{*}$ i stan $s_1\in S_F$ o własności

$\mathrm{♯}{s}_{0}w\mathrm{♯}{\mapsto }^{*}\mathrm{♯}{s}_1{w}^{\prime }\mathrm{♯}$

oraz

$w\in L_1⟺w^{\prime }\in L_2.$

Lemat 2.1

Załóżmy, że $L_1\propto L_2$. Wtedy zachodzą implikacje:

1. $L_2\in$ P      $⟹L_1\in$ P,
2. $L_2\in$ NP      $⟹L_1\in$ NP,
3. $L_2\in$ PSPACE      $⟹L_1\in$ PSPACE.

Dowód

Dane słowo $w$ transformujemy do $w^{\prime }$ w czasie wielomianowym, co gwarantuje założenie $L_1\propto L_2$. Dzięki założeniu $L_2\in$ P możemy rozstrzygnąć, czy $w^{\prime }\in L_2$ (tzn. jeśli akceptujemy $w^{\prime }$, to robimy to w czasie wielomianowym). Tym sposobem (korzystając z definicji transformacji wielomianowej) akceptujemy $w$ w czasie wielomianowym, o ile tylko $w\in L_1$. Dowód dla pozostałych implikacji jest identyczny.

Definicja 2.2

Niech ${𝒞}$ oznacza pewną klasę języków. Język $L$ nazywamy ${𝒞}$-trudnym, jeśli spełniony jest warunek:

$\mathrm{\forall }{L}^{\prime }\in {𝒞}{L}^{\prime }\propto L.$

Jeżeli dodatkowo spełniony jest warunek $L\in {𝒞}$, to język $L$ nazywamy ${𝒞}$-zupełnym.

Intuicyjnie, fakt, że język jest ${𝒞}$-zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy ${𝒞}$, natomiast język ${𝒞}$-trudny jest bardziej skomplikowany niż każdy z klasy ${𝒞}$, choć sam nie musi do niej należeć.

Uwaga 2.1

Rozważając klasę P , NP i PSPACE, możemy mówić o językach (problemach) P -zupełnych, NP -zupełnych, czy też PSPACE -zupełnych. To samo odnosi się do języków trudnych (tzn. klasa języków P -trudnych, itd.).

Przykład 2.1

Rozważmy języki:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}\quad,\quad L_2=\left\{1^i 2^j 4^{2k}\: k=i\cdot j,\: i,j\geqslant 1\right\}. }

Języki: $L_1$ oraz $L_2$ wyglądają na bardzo podobne, zatem wydaje się, że $L_1\propto L_2$ oraz $L_2\propto L_1$. Uzasadnienie tego faktu jest prawie natychmiastowe.

Konstruujemy deterministyczną maszynę Turinga która działa w następujący sposób:

1. Jeśli słowo wejściowe jest puste, to stop.
2. Przejdź do prawego ogranicznika. Jeśli przy ograniczniku nie występuje symbol $4$, to wykonaj krok 1.
3. Jeśli w słowie wejściowym występuje symbol $4$, to sprawdź, czy słowo przetwarzane jest postaci $\mathrm{♯}w{4}^s\mathrm{♯}$, gdzie $s⩾1$ oraz $w\in ({\mathrm{\Sigma }}_I\setminus \left\{4\right\}{)}^{*}$ oraz czy dodatkowo $s$ jest liczbą parzystą. Jeśli nie, to wykonaj krok 1.
4. Zamień słowo $4^s$ na słowo $3^{\frac{s}{2}}{\mathrm{♯}}^{\frac{s}{2}}$ i wykonaj krok 1.
5. Przejdź nad pierwszy symbol po lewym ograniczniku i zatrzymaj się.

W ten sposób zawsze przeprowadzamy konfigurację $\mathrm{♯}{s}_{0}w\mathrm{♯}$ na konfigurację $\mathrm{♯}{s}_1{w}^{\prime }\mathrm{♯}$, przy czym $w^{\prime }=1^i{2}^j{3}^k$ tylko, gdy $w=1^i{2}^j{4}^{2k}$. Zatem $w\in L_2$ wtedy i tylko wtedy, gdy $w^{\prime }\in L_1$. Wykazaliśmy, że $L_2\propto L_1$.

Warunek $L_1\propto L_2$ otrzymujemy w sposób identyczny. Trzeba tylko wypisać odpowiednią ilość symboli $4$ (a wiemy już, jak konstruować liczbę $2n$, mając dane $n$).

4. Rodziny ${{ℒ}}_1$ i ${{ℒ}}_0$ - zamkniętość na działania

Dla kompletności tej części wykładu przedstawimy własności zamkniętości rodziny języków kontekstowych ${{ℒ}}_1$ i języków typu (0) ${{ℒ}}_0$ ze względu na najczęściej używane operacje. W niektórych przypadkach dowody dotyczące obu klas są takie same. W dowodach posłużymy się specjalną postacią gramatyk, a mianowicie taką, w której symbole terminalne występują tylko po prawej stronie. Prawdziwe bowiem jest twierdzenie

Twierdzenie 4.1

Dla każdej gramatyki istnieje równoważna gramatyka tego samego typu taka, że każda produkcja, w której występuje symbol terminalny $a$ , jest postaci $v⟶a$ .

Elementarny dowód tej własności pozostawiamy jako zadanie domowe.

Twierdzenie 4.2

Rodziny ${{ℒ}}_0$ i ${{ℒ}}_1$ są zamknięte ze względu na:

1. sumę mnogościową,
2. iloczyn mnogościowy,
3. katenację,
4. iterację $*$,
5. odbicie zwierciadlane.

Dowód

1. Niech dla $i=1,2G_i=(V_N^i,V_T,v_0^i,P_i)$ będą gramatykami typu $(1)$ (odpowiednio typu $(0)$ ) takimi, że $V_N^1\cap V_N^2=\mathrm{\varnothing }$ . I niech $L_i=L(G_i)$ . Określamy gramatykę $G$ typu $(1)$ (typu $(0)$ ) generującą język $L_1\cup L_2$ .

Jeśli $1\notin L_1\cup L_2$ , to przyjmujemy:

$G=(V_N^1\cup V_N^2\cup \left\{v_0\right\},V_T,v_0,P_1\cup P_2\cup \{v_0\to v_0^1,v_0\to v_0^2\}).$

Zauważmy, że wówczas w żadnej z gramatyk nie ma prawa wymazującego. Jeśli natomiast $1\in L_1\cup L_2$ , to konstruujemy gramatykę $G$ dla języków $L_1\setminus \left\{1\right\}$ i $L_2\setminus \left\{1\right\}$ , jak powyżej, a następnie dodajemy nowy symbol początkowy ${\bar{v}}_0$ i prawa ${\bar{v}}_0\to v_0,{\bar{v}}_0\to 1$ .

2. Przecięcie udowodnimy tylko dla języków typu $(0)$ . Dowód dla języków kontekstowych został przeprowadzony wcześniej.

Niech dla $i=1,2G_i=(V_N^i,V_T,v_0^i,P_i)$ będą gramatykami typu $(0)$ takimi, że $V_N^1\cap V_N^2=\mathrm{\varnothing }$ . Niech $L_i=L(G_i)$ . Określamy gramatykę $G$ typu $(0)$ generującą język $L_1\cap L_2$, przyjmując:

$G=(V_N^1\cup V_N^2\cup V_N,V_T,v_0,P_1\cup P_2\cup P),$

gdzie: $V_N=\{v_a:a\in V_T\}\cup \{v_0,{\bar{v}}_1,{\bar{v}}_2\}$ , a do zbioru $P$ należą prawa:
(1) $v_0\to {\bar{v}}_1{v}_0^1{\bar{v}}_2{v}_0^2{\bar{v}}_1,$
(2) ${\bar{v}}_{2}a\to v_a{\bar{v}}_2$ dla $\mathrm{\forall }a\in V_T,$
(3) $b{v}_a\to v_{a}b$ dla $\mathrm{\forall }a,b\in V_T,$
(4) ${\bar{v}}_1{v}_{a}a\to a{\bar{v}}_1$ dla $\mathrm{\forall }a\in V_T,$
(5) ${\bar{v}}_1{\bar{v}}_2{\bar{v}}_1\to 1.$
Przy pomocy prawa (1) i wszystkich praw ze zbioru $P_1\cup P_2$ można wygenerować zbiór słów:

$\{{\bar{v}}_1{w}_1{\bar{v}}_2{w}_2{\bar{v}}_1:w_1\in L_1,w_2\in L_2\}.$

Z dowolnego słowa należącego do tego zbioru, korzystając z praw (2)-(4), można wyprowadzić słowo $w_1{\bar{v}}_1{\bar{v}}_2{\bar{v}}_1$ wtedy i tylko wtedy, gdy $w_1=w_2$ . Korzystając z prawa (5), dostajemy słowo $w_1$ . A więc $L(\bar{G})=L_1\cap L_2$ .

3. Niech dla $i=1,2G_i=(V_N^i,V_T,v_0^i,P_i)$ będą tak jak poprzednio gramatykami typu $(1)$ ( $(0)$ ) takimi, że $V_N^1\cap V_N^2=\mathrm{\varnothing }$ oraz spełniającymi warunki powyższego twierdzenia. Niech $L_i=L(G_i)$ . Określamy gramatykę $G$ odpowiednio typu $(1)$ ( $(0)$ ) generującą język $L_1{L}_2$ .

Jeśli $1\notin L_1\cup L_2$ , to przyjmujemy:

$G=(V_N^1\cup V_N^2\cup \left\{v_0\right\},V_T,v_0,P_1\cup P_2\cup \{v_0\to v_0^1{v}_0^2\}).$

Jeśli $1\in L_1\cup L_2$ , to oznaczamy $L_{1^{\prime }}=L_1\setminus \left\{1\right\},L_{2^{\prime }}=L_2\setminus \left\{1\right\}$ . Wówczas:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle L_{1}L_{2}=\left\{ \begin{array} {lll} L_{1}'L_{2}'\cup L_{1}', & gdy & 1\in L_{2},\: 1\notin L_{1},\\ L_{1}'L_{2}'\cup L_{2}', & gdy & 1\in L_{1},\: 1\notin L_{2},\\ L_{1}'L_{2}'\cup L_{1}'\cup L_{2}'\cup \left\{ 1\right\}, & gdy & 1\in L_{1},\: 1\in L_{2}. \end{array} \right. }

Wykorzystując poprzednią konstrukcję i zamkniętość ze względu na sumę w każdym z tych przypadków, otrzymujemy gramatykę generującą katenację języków $L_1$ i $L_2$ .

4. Niech $G=(V_N,V_T,v_0,P)$ będzie gramatyką typu $(1)$ (typu $(0)$ ) taką, że symbole terminalne nie występują po lewej stronie żadnej produkcji z $P$ . Załóżmy też, że $1\notin L=L(G)$ . Gramatyka

$\bar{G}=(V_N\cup \{{\bar{v}}_0,{\bar{v}}_1\},V_T,{\bar{v}}_0,\bar{P}),$

gdzie

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle \displaystyle \overline{P}=P\cup \begin{array} [t]{l} \left\{ \overline{v}_{0}\rightarrow 1,\: \overline{v}_{0}\rightarrow v_{0},\: \overline{v}_{0}\rightarrow \overline{v}_{1}v_{0}\right\} \cup \\ \left\{ \overline{v}_{1}a\rightarrow \overline{v}_{1}v_{0}a\, :\, a\in V_{T}\right\} \cup \\ \left\{ \overline{v}_{1}a\rightarrow v_{0}a\, :\, a\in V_{T}\right\} \end{array} }

generuje język $L^{*}$ . Jeśli $1\in L$ , to usuwamy prawo wymazujące $v_0\to 1$ i dla języka $L\setminus \left\{1\right\}$ konstruujemy gramatykę $\bar{G}$ . Z faktu, że $(L\cup \left\{1\right\}{)}^{*}=L^{*}$ , wynika, że również $L(\bar{G})=L^{*}$ .

5. Jeśli $G=(V_N,V_T,v_0,P)$ jest gramatyką typu $(1)$ (typu $(0)$ ) taką, że $L(G)=L$ , to gramatyka $\overleftarrow{G}=(V_N,V_T,v_0,\overleftarrow{P})$ , gdzie $\overleftarrow{P}=\{\overleftarrow{x}\to \overleftarrow{y}:x\to y\in P\}$ generuje język $\overleftarrow{L}$ .

Zauważmy na koniec, że rodzina ${{ℒ}}_0$ nie jest zamknięta ze względu na uzupełnienie. Stwierdzenie to wynika z przyjęcia jako obowiązujacej tezy Churcha, która w tym wypadku implikuje równość rodziny języków ${{ℒ}}_0$ i rodziny języków rekurencyjnie przeliczalnych oraz z faktu, iż istnieje język rekurencyjnie przeliczalny, którego uzupełnienie nie jest rekurencyjnie przeliczalne. Ten ostatni fakt podajemy bez dowodu. Dodajmy, że własność zamkniętości ze względu na uzupełnienie dla rodziny ${{ℒ}}_1$ przez długi czas pozostawała problemem otwartym. Dopiero w roku 1987 udowodniono, iż własność ta jest spełniona dla języków kontekstowych. Podsumowanie własności zamkniętości ze względu na działania dla różnych klas języków hierarchii Chomsky'ego zawarte jest w poniższej tabeli:

	3	2	1	0
$\cup$	T	T	T	T
$\cdot$	T	T	T	T
$\star$	T	T	T	T
$\setminus$	T	N	T	N
$\cap$	T	N	T	T

Na koniec podamy twierdzenie o wzajemnych relacjach pomiędzy rodzinami języków z hierarchii Chomsky'ego. Dowód tego twierdzenia wynika w części z definicji typów gramatyk wprowadzonych na wykładzie 2, a w części z udowodnionych własności poszczególnych rodzin języków z hierarchii Chomsky'ego (zakładając obowiązywanie tezy Churcha).

Twierdzenie 4.3

Rodziny języków hierarchii Chomsky'ego spełniają następujące relacje:

${{ℒ}}_0\subseteq {}_{/}{{ℒ}}_1\subseteq {}_{/}{{ℒ}}_2\subseteq {}_{/}{{ℒ}}_3.$

5. Problemy rozstrzygalne

W poprzednim wykładzie uzasadniliśmy, że dla każdej deterministycznej maszyny Turinga jesteśmy w stanie wskazać taką, która akceptuje dany język i jednocześnie zatrzymuje się tylko na słowach akceptowanych. Wymagało to przejścia przez maszynę niedeterministyczną, a następnie jej symulację na maszynie deterministycznej. Z tego powodu ograniczamy się w dalszej części wykładu tylko do tego typu maszyn Turinga (akceptacja=stop). Jak to uzasadniono wcześniej, przy założeniu tezy Churcha, maszyna Turinga może być rozpatrywana jako matematycznie ścisła definicja algorytmu.

Pojęcie rozstrzygalnego problemu zostało wprowadzone wcześniej, na innym wykładzie, i jest ono znane. Przypomnijmy więc tylko, że rozstrzygalność, czy też nierozstrzygalność, odnosi się do pewnej klasy, którą tworzą określone przypadki ustalonego problemu. Jeśli istnieje algorytm, który rozwiązuje taki problem dla wszystkich przypadków w tej klasy, to mówimy, że problem jest rozstrzygalny (w tej klasie). Zatem taki algorytm jest uniwersalnym sposobem rozwiązywania problemu dla wszystkich danych wejściowych określających poszczególne przypadki w tej klasie. Jak łatwo zauważyć dla ustalenia rozstrzygalności problemu wystarczy się opierać na intuicyjnym pojęciu algorytmu. Są jednak takie problemy, dla których nie istnieje, w rozważanej klasie przypadków, uniwersalny sposób ich rozwiazywania. Takie problemy nazywamy nierozstrzygalnymi w danej klasie. Aby wykazać nierozstrzygalność jakiegoś problemu, nieodzownym jest sformalizowanie pojęcia algorytmu. Standardowo taką formalizacją jest, o czym wspomniano już wcześniej, maszyna Turinga.

Zwróćmy uwagę, że maszyna Turinga akceptuje języki, gdy tymczasem przyzwyczajeni jesteśmy, że algorytmy (programy) rozwiązują pewne, niekiedy bardzo skomplikowane, problemy (określone przy pomocy list, kolejek, grafów itp.). Zwracamy zatem uwagę na fakt, że w przypadku maszyny Turinga musimy wykonać wstępne umowne kodowanie naszego problemu. W tym przypadku rozważany język określa te spośród "sensownych" kodowań, które stanowią rozwiązanie postawionego problemu. Z drugiej strony maszyna, akceptując słowo $\mathrm{♯}{w}_1\mathrm{\$}{w}_2\mathrm{♯}$, może informować nas o tym, że wynikiem obliczeń numerycznych na danych zakodowanych w $w_1$ rzeczywiście jest liczba zakodowana w $w_2$ itp.

Dla ilustracji powyższych dywagacji rozważmy problem skończoności w klasie jezyków regularnych. Problem ten jest rozstrzygalny, bo w oparciu o lemat o pompowaniu można skonstruować algorytm, który dla dowolnego języka regularnego rozstrzygnie, czyli odpowie twierdząco lub przecząco na pytanie o jego skończoność. W tym przypadku można np. przyjąć, że jako słowo wejściowe podajemy zakodowany opis gramatyki generującej język.

Nierozstrzygalność algorytmiczna problemu w ustalonej klasie nie oznacza, podkreślmy, niemożliwości rozwiązania konkretnego zadania z tej klasy. Nierostrzygalność oznacza niemożliwość rozwiązania za pomocą tego samego algorytmu, tej samej metody, wszystkich przypadków tego problemu należących do danej klasy.

W zamieszczonej poniżej tabeli przedstawiamy najczęściej rozważane pod kątem rozstrzygalności problemy z dziedziny języków formalnych w ramach hierarchii Chomsky'ego. Litera R oznacza rozstrzygalność problemu, N nierostrzygalność, a znak - pojawiający się przy problemie jednoznaczności oznacza, że problemu tego nie formułuje się dla gramatyk kontekstowych i typu (0):

własność	(3)	(2)	(1)	(0)
należenie $w\in L$	R	R	R	N
inkluzja $L_1\subset L_2$	R	N	N	N
równoważność	R	N	N	N
pustość $L=\mathrm{\varnothing }$	R	R	N	N
nieskończoność $cardL={\mathrm{\aleph }}_0$	R	R	N	N
jednoznaczność gramatyki	R	N	-	-

Najczęściej używaną metodą dowodzenia nierozstrzygalności problemu $P$ jest redukcja tego problemu do innego, powiedzmy $P^{\prime }$ , dla którego nierozstrzygalność została ustalona wcześniej. Redukcja taka prowadzi do sformułowania implikacji:

jeśli $P$ byłby rozstrzygalny, to i $P^{\prime }$ byłby rozstrzygalny.

A ponieważ to ostatnie (następnik implikacji) nie jest prawdą, więc problem $P$ nie jest rozstrzygalny.

Należy w tym miejscu podkreślić fakt, że dowody nierozstrzygalności problemów uniwersalnych (takich jak problem Posta rozważany dalej) wiążą się z konstrukcją odpowiednich maszyn Turinga, kodowaniem problemu, a następnie dowodem uzasadniającym, że problem jest rzeczywiście nierozstrzygalny. Tematyka ta wykracza poza ramy wykładu. Z tego też powodu ograniczymy się tutaj do zaprezentowania jednego ze znanych problemów nierozstrzygalnych bez dowodu nierozstrzygalności.

Najczęściej występującym w literaturze problemem nierozstrzygalnym jest, bez wątpienia, problem Posta przedstawiony poniżej.

 

Problem Posta

Dla dowolnego alfabetu $A$ , o co najmniej dwóch elementach ( $\mathrm{♯}A⩾2$ ), załóżmy, iż dana jest, tak zwana, lista słów, a dokładniej: par słów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right), } gdzie $u_i,w_i\in A^{+}$ , $n\in \mathbb{\mathbb{N}}$ . Mówimy, że taka lista ma własność Posta (problem Posta ma rozwiązanie), jeśli istnieje ciąg indeksów $i_1,\dots ,i_k\in \{1,...,n\}$ taki, że

$u_{i_1}\dots u_{i_k}=w_{i_1}\dots w_{i_k}.$

Jest to w ogólnym przypadku problem nierozstrzygalny.

Problem ten można sformułować równoważnie następująco. Niech $A$ będzie alfabetem interpretowanym jako zbiór indeksów, a $B$ dowolnym alfabetem. Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle h:A^{*}\longrightarrow B^{*},\: g:A^{*}\longrightarrow B^{*} } będą dowolnymi homomorfizmami. Problem Posta, inaczej sformułowany, polega na odpowiedzi na pytanie, czy istnieje słowo $x\in A^{+}$ takie, że $h(x)=g(x)$ .

Dwa kolejne przykłady ilustrują technikę redukcji pewnych problemów do problemu Posta. W efekcie uzyskujemy nierozstrzygalność w sposób opisany powyżej.

Twierdzenie 5.1

W klasie gramatyk bezkontekstowych problem niejednoznaczności jest nierozstrzygalny.

Dowód

Udowodnimy, że problem jest nierozstrzygalny dla gramatyk bezkontekstowych generujących języki nad alfabetem dwuelementowym $A=\{a,b\}$ . Oznaczmy $B=\{d,e\}$ i określmy homomorfizm $h:B^{*}⟶A^{*}$ , przyjmując $h(d)=b{a}^2$ oraz $h(e)=b{a}^3$ . Niech $u$ będzie ciągiem $u_1,...,u_n\in B^{+}$ dowolnie wybranych i ustalonych słów. Dla dowolnej liczby naturalnej $i>0$ niech $\bar{i}=d{e}^i$ . Określony poniżej język

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_{u}=\{h(\overline{i_{1}}).....h(\overline{i_{k}})bah(u_{i_{k}}),...,h(u_{i_{1}})\in A^{*}\: :\: k\geqslant 1,\: 1\leqslant i_{j}\leqslant n\}}

jest językiem bezkontekstowym, jako generowany przez gramatykę $G_u=(V_N,V_T,v_0,P_u)$ , dla której

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle V_{N}=\{v_{u}\},\: V_{T}=\{a,b\},\: v_{0}=v_{u} } oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle P_{x}=\{v_{u}\rightarrow h(\overline{i})v_{u}h(u_{i}),\: v_{u}\rightarrow h(\overline{i})bah(u_{i})\} } .

Niech teraz $u$ i $w$ oznaczają ciągi dowolnie wybranych i ustalonych słów $u_1,...,u_n\in B^{+}$ i $w_1,...,w_n\in B^{+}$ . Tworzą one listę słów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right), } . Zatem zasadne jest postawienie pytania, czy lista ta ma własność Posta. Niech $G_u$ oraz $G_w$ będą gramatykami bezkontekstowymi określonymi tak jak powyżej. Gramatyka $G=(\{v_0,v_u,v_w\},\{a,b\},v_0,P)$ , gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle P=\{v_{0}\rightarrow v_{u},\: v_{0}\rightarrow v_{w}\}\cup P_{u}\cup P_{w} } jest bezkontekstowa. Gramatyka ta jest niejednoznaczna wtedy i tylko wtedy, gdy $L_u\cap L_y\ne \mathrm{\varnothing }$ . Ten ostatni warunek równoważny jest istnieniu liczb $i_1,...,i_k\in \mathbb{\mathbb{N}}$ takich, że $u_{i_1}.....u_{i_k}=w_{i_1}.....w_{i_k}$, czyli własności Posta listy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right) } .Ostatecznie więc rozstrzygalność problemu niejednoznaczności w klasie gramatyk bezkontekstowych prowadziłaby do rozstrzygalności własności Posta.

Dla drugiego przykładu przyjmijmy jako alfabety Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle A_{2}=\left\{ a,b\right\} ,\: A_{3}=\left\{ a,b,c\right\} } oraz określmy język

$L=\{v_{1}c{v}_{2}c{\overleftarrow{v}}_{2}c{\overleftarrow{v}}_1:v_1,v_2\in A_2^{*}\}.$

Ustalmy listę Posta Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left( u_{1},w_{1}\right) \: \left( u_{2},w_{2}\right) \: \ldots \left( u_{n},w_{n}\right) } nad alfabetem $A_2$ , gdzie $u_i,w_i\in A_2^{+}$ . Wprowadzamy teraz języki Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_{u},\: L_{w}\: L_{PP} } nad alfabetem $A_3$, przyjmując:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned L_{u} &= \left\{ ba^{i_{k}}b\ldots ba^{i_{1}}cu_{i_{1}}\ldots u_{i_{k}}\, :\, k\geqslant 1,1\leqslant i_{j}\leqslant n\right\} \\ L_{w} &= \left\{ ba^{i_{k}}b\ldots ba^{i_{1}}cw_{i_{1}}\ldots w_{i_{k}}\, :\, k\geqslant 1,1\leqslant i_{j}\leqslant n\right\} \endaligned}

oraz definiujemy język

$L_{PP}=L_{u}c{\overleftarrow{L}}_w.$

Określone powyżej języki nad alfabetem $A_3$ mają własności konieczne do zastosowania lematu, który przytoczymy bez dowodu.

Lemat 5.1

Języki Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L,\: L_{PP},\: A_{3}^{*}\setminus L,\: A_{3}^{*}\setminus L_{PP} } są bezkontekstowe.

Dla języków $L$ i $L_{PP}$ uzasadnienie ich bezkontekstowości jest proste poprzez konstrukcję odpowiednich gramatyk. Aby uzyskać bezkontekstowość ich uzupełnień, należy podzielić rozważane języki na rozłączne podzbiory i konstruować gramatyki bezkontekstowe dla tych wyróżnionych podzbiorów, a w końcu wykorzystać fakt, że suma języków bezkontekstowych jest językiem bezkontekstowym.

Zauważmy teraz, że istnienie rozwiązania problemu Posta nad alfabetem $A_3$ jest równoważne temu, że $L_{PP}\cap L\ne \mathrm{\varnothing }$ .

Jeśli bowiem $L_{PP}\cap L\ni b{a}^{i_k}\dots b{a}^{i_1}c{u}_{i_1}\dots u_{i_k}c\overleftarrow{w_{i_1}\dots w_{i_k}}c{a}^{i_1}b\dots a^{i_k}b$ , gdzie $k⩾1,1⩽i_j⩽n$ , to oczywiście $u_{i_1}\dots u_{i_k}=w_{i_1}\dots w_{i_k}$ . Jeśli ciąg $i_1,\dots ,i_k$ jest rozwiązaniem problemu Posta, to $(i_1,\dots ,i_k)(i_1,\dots ,i_k)$ też. Zatem jeśli $L_{PP}\cap L\ne \mathrm{\varnothing }$ , to język $L_{PP}\cap L$ jest nieskończony.

Wobec nierozstrzygalności problemu Posta wnioskujemy, że nierozstrzygalny jest problem pustości i problem nieskończoności przecięcia $L_1\cap L_2$ w klasie języków bezkontekstowych.