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.
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 \(\displaystyle t,s:\mathbb{N}\rightarrow \mathbb{N}\). Mówimy, że maszyna Turinga \(\displaystyle \mathcal{MT}\) (deterministyczna lub niedeterministyczna) akceptuje słowo \(\displaystyle w\in \Sigma_I^*\) w czasie \(\displaystyle t(|w|)\), jeśli istnieje ciąg \(\displaystyle k\leqslant t(|w|)\) konfiguracji \(\displaystyle d_1,d_2,\dots, d_k\) takich, że \(\displaystyle d_1=\sharp s_0 w \sharp\), \(\displaystyle d_k= \sharp w_{1}s_{F}w_{2}\sharp\) dla pewnych \(\displaystyle w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\) oraz \(\displaystyle d_i \mapsto d_{i+1}\) dla \(\displaystyle i=1,\dots,k-1\).
Jeśli istnieje ciąg konfiguracji \(\displaystyle d_1 \mapsto d_2 \mapsto \dots \mapsto d_m\), gdzie \(\displaystyle d_1=\sharp s_0 w \sharp\), \(\displaystyle d_m\) jest konfiguracją akceptującą (tzn. \(\displaystyle d_m= \sharp w_{1}s_{F}w_{2}\sharp\) dla pewnych \(\displaystyle w_{1},w_{2}\in \Sigma _{T}^{*},s_{F}\in S_{F}\)) oraz dodatkowo \(\displaystyle |d_i|\leqslant s(|w|)+2\), to mówimy, że maszyna \(\displaystyle \mathcal{MT}\) akceptuje słowo \(\displaystyle w\in \Sigma_I^*\) w pamięci \(\displaystyle s(|w|)\).
Mówimy, że język \(\displaystyle L\) jest akceptowany w czasie \(\displaystyle t(n)\) (pamięci \(\displaystyle s(n)\)), jeśli istnieje maszyna Turinga \(\displaystyle \mathcal{MT}\), dla której \(\displaystyle L(\mathcal{MT})=L\) oraz każde słowo \(\displaystyle w\in L\) jest akceptowane w czasie \(\displaystyle t(|w|)\) (pamięci \(\displaystyle 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 \(\displaystyle \log n\) itp. W ujęciu prezentowanym w tym wykładzie zajmujemy się akceptacją w pamięci \(\displaystyle n^k\), dla \(\displaystyle k\geqslant 1\), zatem nie ma potrzeby dodatkowego definiowania maszyn Turinga off-line.
Definicja 1.2
Oznaczmy przez \(\displaystyle Dtime(t(n))\) oraz \(\displaystyle Dspace(s(n))\) rodzinę języków akceptowanych w czasie \(\displaystyle t(n)\) i odpowiednio pamięci \(\displaystyle s(n)\) przez deterministyczną maszynę Turinga. Dla maszyn niedeterministycznych wprowadzamy w identyczny sposób klasy \(\displaystyle Ntime(t(n))\) oraz \(\displaystyle Nspace(s(n))\).
Określamy następujące klasy złożoności (klasy języków):
Wprost z definicji otrzymujemy zależności P \(\displaystyle \subset\) NP oraz PSPACE \(\displaystyle \subset\) NPSPACE . W dalszej części wykładu udowodnimy kilka mniej oczywistych zależności.
Przykład 1.1
Rozważmy język:
Język \(\displaystyle L\in\) P . Deterministyczna maszyna Turinga \(\displaystyle MT_3\) akceptująca taki język może wyglądać następująco (zaczynamy od konfiguracji \(\displaystyle \sharp s_0 w \sharp\)):
Nietrudno zaobserwować, że maszyna \(\displaystyle MT_3\) przechodzi przez taśmę w prawo i w lewo tyle razy, ile symboli \(\displaystyle 3\) zawiera taśma oraz wykonuje jeden dodatkowy przebieg na starcie. Zatem słowa z \(\displaystyle L\) są akceptowane w czasie ograniczonym wielomianowo.
Przykład 1.2
Rozważmy teraz język
Najprostszą metodą uzasadnienia, że \(\displaystyle L\in\) NP jest konstrukcja tak zwanej wyroczni. Polega ona na następującej dwuetapowej procedurze:
W naszym przykładzie Etap 1 wygląda następująco:
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 \(\displaystyle 1^i 2^j 3^k\), gdzie \(\displaystyle i,j>1\) oraz \(\displaystyle k=i\cdot j\). Jeśli tak, to słowo wejściowe \(\displaystyle 3^k\) pochodziło z języka \(\displaystyle 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 \(\displaystyle 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 \(\displaystyle L\) nie ma to znaczenia.
Zastanów się, czy da się wykazać, że także \(\displaystyle L\in\) P (Ćwiczenie 1.3, do tego wykładu).
Definicja 1.3
Funkcja \(\displaystyle s(n)\) jest konstruowalna pamięciowo, jeśli istnieje maszyna Turinga \(\displaystyle \mathcal{MT}=(\Sigma _{T},S,f,s_{0},S_{F})\), dla której \(\displaystyle d_1 \mapsto^* d_2\), gdzie \(\displaystyle d_1=\sharp s_0 1^n \sharp\), \(\displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp\) dla \(\displaystyle s_1\in S_F\), \(\displaystyle w\in (\Sigma_T\setminus \left\{1\right\})^*\) oraz dodatkowo \(\displaystyle d_2\) jest konfiguracją końcową.
Inaczej mówiąc, funkcję \(\displaystyle s(n)\) nazywamy konstruowalną pamięciowo, jeśli istnieje maszyna Turinga \(\displaystyle \mathcal{MT}\), otrzymując na wejściu słowo \(\displaystyle w\) długości \(\displaystyle |w|=n\), zaznacza na taśmie roboczej \(\displaystyle s(n)\) klatek i zatrzymuje się (akceptując słowo \(\displaystyle w\)).
Przykład 1.3
Funkcja \(\displaystyle s(n)=2n\) jest konstruowalna pamięciowo. Maszyna \(\displaystyle MT_4\), która konstruuje \(\displaystyle s(n)\) działa według schematu:
Twierdzenie 1.1 liniowa kompresja pamięci
Niech będzie dany język \(\displaystyle L\) oraz maszyna Turinga \(\displaystyle \mathcal{TM}\) akceptująca \(\displaystyle L\) w pamięci \(\displaystyle s(n)\). Dla dowolnego \(\displaystyle \varepsilon>0\) istnieje maszyna Turinga \(\displaystyle \mathcal{TM}'\) akceptująca \(\displaystyle L\) w pamięci \(\displaystyle \max\left\{n,\varepsilon s(n)\right\}\).
Dowód
(Szkic) Ustalamy liczbę naturalną \(\displaystyle k\), dla której \(\displaystyle \varepsilon k\geqslant 2\). Maszynę \(\displaystyle \mathcal{TM}'\) definiujemy następująco:
Zauważmy, że w kroku \(\displaystyle 1\). maszyna \(\displaystyle \mathcal{MT}'\) wykorzystuje \(\displaystyle n\) komórek pamięci do odczytania słowa wejściowego. Kompresja taśmy zapewnia, że podczas symulowania maszyny \(\displaystyle \mathcal{MT}\) nie wykorzystamy więcej niż \(\displaystyle \lceil \frac{s(n)}{k}\rceil \leqslant \varepsilon s(n)\) komórek. Jednocześnie można założyć, że \(\displaystyle \mathcal{MT}'\) akceptuje słowa wejściowe z języka \(\displaystyle L\) o długości mniejszej niż \(\displaystyle k\) bez symulowania \(\displaystyle \mathcal{MT}\).
Twierdzenie 1.2 Savitch
Dla dowolnej funkcji \(\displaystyle s(n)\) konstruowalnej pamięciowo spełniającej warunek \(\displaystyle s(n)\geqslant \log_2 n\) prawdziwa jest inkluzja \(\displaystyle Nspace(s(n))\subset DSpace(s^2(n))\).
Dowód
Niech \(\displaystyle \mathcal{NMT}\) będzie niedeterministyczną maszyną Turinga akceptującą język \(\displaystyle L=L(\mathcal{NMT})\) w pamięci \(\displaystyle s(n)\). Niech \(\displaystyle k(n)\) oznacza liczbę konfiguracji potrzebną do zaakceptowania słowa o długości \(\displaystyle n\). Istnieje liczba \(\displaystyle c>1\), dla której \(\displaystyle k(n)\leqslant c^{s(n)}\), co z kolei oznacza, że każde słowo o długości \(\displaystyle n\) jest akceptowane w \(\displaystyle c^{s(n)}\) krokach czasowych.
Rozważmy algorytm:
Algorytm
1 Wejście: słowo \(\displaystyle w\) długości \(\displaystyle |w|=n\) 2 oblicz \(\displaystyle s(n)\) 3 for każda konfiguracja akceptująca \(\displaystyle d_A\) dla której \(\displaystyle |d_A|\leqslant s(n)\) 4 do if Test(\(\displaystyle \sharp s_0 w \sharp\), \(\displaystyle d_A\), \(\displaystyle s(n) \log_2 c\)) then akceptuj
gdzie procedura Test ma następującą postać:
Algorytm Procedure Test(\(\displaystyle d\),\(\displaystyle d'\),\(\displaystyle i\))
1 if \(\displaystyle i=0\) and [ (\(\displaystyle d=d'\)) or (\(\displaystyle d\mapsto d'\))] then return true 2 else for każda konfiguracja \(\displaystyle d''\) dla której \(\displaystyle |d''|\leqslant s(n)\) 3 do if Test(\(\displaystyle d\),\(\displaystyle d''\),\(\displaystyle i-1\)) and Test \(\displaystyle d''\),\(\displaystyle d'\),\(\displaystyle 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ć \(\displaystyle s(n)\) komórek taśmy, aby móc konstruować konfiguracje o długości ograniczonej przez \(\displaystyle s(n)\) i móc następnie wykonywać na nich symulację maszyny \(\displaystyle \mathcal{NMT}\).
Zauważmy, że ilość konfiguracji jest ograniczona przez \(\displaystyle s(n)\), a głębokość rekursji przez \(\displaystyle \log c^{s(n)}\). Oznacza to, że jesteśmy w stanie skonstruować maszynę Turinga, która wymaga \(\displaystyle c' s^2(n)\) pamięci, gdzie \(\displaystyle c'\) jest pewną stałą. Na mocy Twierdzenia 1.1 jesteśmy w stanie określić maszynę \(\displaystyle \mathcal{MT}\) działającą w pamięci \(\displaystyle s^2(n)\).
Wniosek 1.1
Lemat 1.1
Jeśli \(\displaystyle g(n)\geqslant n\), to \(\displaystyle Dtime(g(n))\subset Dspace(g(n))\) oraz \(\displaystyle Ntime(g(n))\subset Nspace(g(n))\).
Dowód
Niech będzie dana maszyna deterministyczna \(\displaystyle \mathcal{MT}\) akceptująca dany język \(\displaystyle L\) w czasie \(\displaystyle g(n)\). Do akceptacji słowa \(\displaystyle w\) o długości \(\displaystyle n\) maszyna wykorzystuje co najwyżej \(\displaystyle g(n)\) kroków czasowych, czyli odwiedza co najwyżej \(\displaystyle g(n)+1\) komórek taśmy.
Na podstawie Twierdzenia 1.1 istnieje maszyna Turinga \(\displaystyle \mathcal{MT}'\) wykorzystująca
komórek pamięci. Dla niedeterministycznych maszyn Turinga argumentacja jest identyczna.
Wniosek 1.2
Uwaga 1.2
Nie jest znany przykład wykazujący silną inkluzję P \(\displaystyle \varsubsetneq\) NP ani dowód wykluczający istnienie takiego przykładu. Powszechnie uznawana hipoteza głosi:
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 \(\displaystyle L\in\) NP, problem uzasadnienia, że także \(\displaystyle L\in\) P, jest nietrywialny, gdyż wymaga zazwyczaj konstrukcji całkiem nowej maszyny Turinga niż ta do weryfikacji \(\displaystyle L\in\) NP .
Definicja 2.1 transformacja wielomianowa
Niech \(\displaystyle L_1,L_2\) będą dowolnymi językami nad pewnym alfabetem \(\displaystyle \Sigma_I\). Mówimy, że \(\displaystyle L_1\) redukuje się do \(\displaystyle L_2\) w czasie wielomianowym, co oznaczamy \(\displaystyle L_1 \propto L_2\), gdy istnieje deterministyczna maszyna Turinga \(\displaystyle \mathcal{MT}=(\Sigma _{T},S,f,s_{0},S_{F})\) taka, że dla dowolnego \(\displaystyle w\in \Sigma_I^*\) istnieje \(\displaystyle w'\in \Sigma_I^*\) i stan \(\displaystyle s_1\in S_F\) o własności
oraz
Lemat 2.1
Załóżmy, że \(\displaystyle L_1 \propto L_2\). Wtedy zachodzą implikacje:
Dowód
Dane słowo \(\displaystyle w\) transformujemy do \(\displaystyle w'\) w czasie wielomianowym, co gwarantuje założenie \(\displaystyle L_1 \propto L_2\). Dzięki założeniu \(\displaystyle L_2 \in\) P możemy rozstrzygnąć, czy \(\displaystyle w'\in L_2\) (tzn. jeśli akceptujemy \(\displaystyle w'\), to robimy to w czasie wielomianowym). Tym sposobem (korzystając z definicji transformacji wielomianowej) akceptujemy \(\displaystyle w\) w czasie wielomianowym, o ile tylko \(\displaystyle w\in L_1\). Dowód dla pozostałych implikacji jest identyczny.
Definicja 2.2
Niech \(\displaystyle \mathcal{C}\) oznacza pewną klasę języków. Język \(\displaystyle L\) nazywamy \(\displaystyle \mathcal{C}\)-trudnym, jeśli spełniony jest warunek:
Jeżeli dodatkowo spełniony jest warunek \(\displaystyle L\in \mathcal{C}\), to język \(\displaystyle L\) nazywamy \(\displaystyle \mathcal{C}\)-zupełnym.
Intuicyjnie, fakt, że język jest \(\displaystyle \mathcal{C}\)-zupełny, oznacza, że jest on najbardziej skomplikowany (pod względem obliczeniowym) wśród języków z klasy \(\displaystyle \mathcal{C}\), natomiast język \(\displaystyle \mathcal{C}\)-trudny jest bardziej skomplikowany niż każdy z klasy \(\displaystyle \mathcal{C}\), 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:
Języki: \(\displaystyle L_1\) oraz \(\displaystyle L_2\) wyglądają na bardzo podobne, zatem wydaje się, że \(\displaystyle L_1 \propto L_2\) oraz \(\displaystyle 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:
W ten sposób zawsze przeprowadzamy konfigurację \(\displaystyle \sharp s_0 w \sharp\) na konfigurację \(\displaystyle \sharp s_1 w' \sharp\), przy czym \(\displaystyle w'=1^i 2^j 3^k\) tylko, gdy \(\displaystyle w=1^i 2^j 4^{2k}\). Zatem \(\displaystyle w\in L_2\) wtedy i tylko wtedy, gdy \(\displaystyle w'\in L_1\). Wykazaliśmy, że \(\displaystyle L_2 \propto L_1\).
Warunek \(\displaystyle L_1 \propto L_2\) otrzymujemy w sposób identyczny. Trzeba tylko wypisać odpowiednią ilość symboli \(\displaystyle 4\) (a wiemy już, jak konstruować liczbę \(\displaystyle 2n\), mając dane \(\displaystyle n\)).