Złożoność obliczeniowa. | Informatyka MIMUW

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 $\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):

$\displaystyle \begin{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). \end{aligned}$

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:

$\displaystyle L=\left\{1^i 2^j 3^k\: k=i\cdot j,\: i,j\geqslant 1\right\}.$

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$ ):

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

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

$\displaystyle L=\left\{3^k\: : \: k=i\cdot j$ dla pewnych

$\displaystyle i,j> 1\rbrace.$

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

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

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

Użyj dwóch taśm. Na pierwszej z nich znajduje się $\displaystyle 3^k$ .
Idź po pierwszej taśmie, wykorzystując niedeterministyczną funkcję przejść. Napotykając $\displaystyle 3$ , możesz wypisać $\displaystyle 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.
Powróć do początku pierwszej taśmy. Wykonaj sekwencję jak w kroku $\displaystyle 2$ , z tą różnicą, że teraz na drugiej taśmie wypisuj symbole $\displaystyle 2$ .
Jako ostatnią część tego etapu przekopiuj symbole $\displaystyle 3$ z pierwszej taśmy na drugą (po symbolach $\displaystyle 1$ i $\displaystyle 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 $\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:

Przejdź do prawego markera. Jeśli napotkano symbol inny niż $\displaystyle 1$ , to odrzuć.
Idź w lewo aż do pierwszego symbolu $\displaystyle 1$ lub markera $\displaystyle \sharp$
Jeśli napotkałeś symbol $\displaystyle 1$ , zamień go na $\displaystyle \clubsuit$ i przejdź do prawego markera. Dopisz do słowa symbol $\displaystyle \clubsuit$ (zwiększając tym samym długość słowa na taśmie o $\displaystyle 1$ ). Następnie powtórz cykl od $\displaystyle 2$ .
Jeśli napotkałeś marker, idź w prawo, zamieniając wszystkie wystąpienia $\displaystyle \clubsuit$ na $\displaystyle 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 $\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:

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

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

PSPACE

$\displaystyle =$ NPSPACE

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

$\displaystyle \max \left\{n, \frac{1}{2}(g(n)+1)\right\}\leqslant g(n)$

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

Wniosek 1.2

$\displaystyle \subset$ NP

$\displaystyle \subset$ PSPACE

$\displaystyle =$ NPSPACE

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:

$\displaystyle \neq$ 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 $\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 .

Redukcja i problemy zupełne

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

$\displaystyle \sharp s_0 w \sharp \mapsto^* \sharp s_1 w' \sharp$

oraz

$\displaystyle w\in L_1 \quad \Longleftrightarrow \quad w' \in L_2.$

Lemat 2.1

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

$\displaystyle L_2 \in$ P $\displaystyle \quad \Longrightarrow \quad L_1 \in$ P,
$\displaystyle L_2 \in$ NP $\displaystyle \quad \Longrightarrow \quad L_1 \in$ NP,
$\displaystyle L_2 \in$ PSPACE $\displaystyle \quad \Longrightarrow \quad L_1 \in$ PSPACE.

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:

$\displaystyle \forall\; L' \in \mathcal{C} \quad L'\propto L.$

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:

$\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: $\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:

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

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$ ).