Jȩzyki, Automaty i Obliczenia

Zadania

Czȩść trzecia

Damian Niwiński i Wojciech Rytter

Styczeń 2002

1 Teoria obliczeń

1.1 Maszyny Turinga

1. Skonstruować maszyn_{}e Turinga obliczaj _{}ac _{}a funkcj_{}e 2^{n} reprezentowan _{}a unarnie. Bardziej dokładnie, zakładamy, że alfabet wejściowy składa si_{}e z jednego symbolu, powiedzmy {1}. Jeśli na wejściu dany jest ci _{}ag n jedynek, (tzn. konfiguracja wejściowa jest q_{0}1^{n}), to po wykonaniu obliczenia konfiguracja powinna być q_{f}1^{2^{n}}.

2. Skonstruować maszyn_{}e Turinga obliczaj _{}ac _{}a funkcj_{}e ⌈log n⌉ reprezentowan _{}a unarnie.

3. Przyjmijmy Σ = {0, 1}. Skonstruować maszyny Turinga rozpoznaj _{}ace nast_{}epuj _{}ace j_{}ezyki:

(a) zbiór palindromów

(b) {w$w : w ∈ Σ^{∗}}

(c) {ww : w ∈ Σ^{∗}}

(d) zbiór ci _{}agów reprezentuj _{}acych binarnie liczby pierwsze.

4. Graf zorientowany o n wierzchołkach ponumerowanych 0, 1, …, n − 1, reprezentujemy ci _{}agiem zer i jedynek długości n^{2}, takim, że k-ty bit jest 1 o ile istnieje kraw_{}edź z wierzchołka o numerze i do wierzchołka o numerze j, gdzie k = i · n + j + 1.

(a) Skonstruować niedeterministyczn _{}a maszyn_{}e Turinga rozpoznaj _{}ac _{}a zbiór słów zero-jedynkowych, które w powyższy sposób reprezentuj _{}a te grafy, w których istnieje ścieżka z wierzchołka o numerze 0 do wierzchołka o numerze n − 1.

(b) Skonstruować maszyn_{}e deterministyczn _{}a realizuj _{}ac _{}a to samo zadanie.

5. Przypomnijmy, że dwie maszyny Turinga o tym samym alfabecie wejściowym uważamy za równoważne o ile akceptuj _{}a ten sam j_{}ezyk. Udowodnić, że dla każdej maszyny Turinga istnieje równoważna jej maszyna posiadaj _{}aca dokładnie jeden stan akceptuj _{}acy i taka, że w konfiguracji akceptuj _{}acej głowica znajduje si_{}e nad pierwsz _{}a komórk _{}a taśmy (tzn. konfiguracja akceptuj _{}aca jest postaci q_{f} coś).

6. Dla danej niedeterministycznej maszyny Turinga skonstruować równoważn _{}a maszyn_{}e deterministyczn _{}a.

7. Dla danych deterministycznych maszyn Turinga M_{1} i M_{2} skonstruować deterministyczne maszyny rozpoznaj _{}ace j_{}ezyki

• L(M_{1}) ∪ L(M_{2})

• L(M_{1}) ∩ L(M_{2})

• L(M_{1})L(M_{2})

• L(M_{1})^{∗}.

8. Udowodnić, że dla każdej maszyny Turinga nad alfabetem wejściowym {0, 1}, istnieje równoważna jej maszyna, której alfabet wszystkich symboli roboczych obejmuje jedynie symbole 0,1,B.

9. Powiemy, że maszyna Turinga jest write-once jeśli może pisać tylko w pustych komórkach taśmy, a symbol raz napisany nie może być zast _{}apiony żadnym innym symbolem (w szczególności nie może być “zmazany” tj. zast _{}apiony przez “blank”). Dla dowolnej maszyny Turinga z jedn _{}a taśm _{}a, skonstruować maszyn_{}e write-once z dwiema taśmami, która akceptuje ten sam j_{}ezyk.

(*) Dowieść, że maszyny typu write-once z jedn _{}a taśm _{}a akceptuj _{}a jedynie j_{}ezyki regularne.

10. Dla dowolnej maszyny Turinga (nad dowolnym alfabetem), skonstruować równoważn _{}a maszyne o jednej taśmie i czterech stanach. (Wolno powi_{}ekszyć alfabet roboczy.)

11. Poj_{}ecie automatu ze stosem można rozszerzyć do automatu z k stosami, k ≥ 2. Dowieść, że dla każdej maszyny Turinga istnieje równoważny jej deterministyczny automat z dwoma stosami. Wywnioskować st _{}ad, że automat z k stosami, k > 2 może być symulowany przez automat z 2 stosami (symulacj_{}e t_{}e można również opisać bezpośrednio).

12. Udowodnić, że jeśli automat skończony wyposażyć dodatkowo w kolejk_{}e, to otrzymany model ma siłe obliczeniow _{}a maszyny Turinga, tzn. dla dowolnej maszyny istnieje automat z kolejk _{}a, który rozpoznaje ten sam j_{}ezyk.

13. Automat z k licznikami c_{1}, …, c_{k}, określamy podobnie jak automat z k stosami, z tym, że liczniki zawieraj _{}a liczby naturalne, a dost_{}epne operacje na licznikach s _{}a postaci c_{i} := c_{i} + 1, c_{i} := c_{i} ˙−1 (gdzie 0 ˙−1 = 0), oraz test c_{i} =^{?} 0. Tzn. przejścia

takiego automatu s _{}a postaci q → p, q, c_{i} =^{?} 0 → p, q, c_{i} ≠^{?} 0 → p, q → p, c_{i} := c_{i} + 1, q → p, c_{i} := c_{i} ˙−1. Nie ma taśmy, lecz zakładamy, że w chwili pocz _{}atkowej dana wejściowa jest wartości _{}a licznika c_{1}, a pozostałe liczniki maj _{}a wartość 0. Dowieść najpierw, że dla każdej maszyny Turinga nad alfabetem {1} istnieje równoważny jej automat z 4 licznikami. Nast_{}epnie wykazać, że liczba liczników może być dalej zredukowana do trzech. (Ograniczenie alfabetu maszyny Turinga nie jest istotne, bo słowa nad alfabetem n–literowym można również łatwo “przerobić” na liczby naturalne w systemie unarnym.)

1.2 Obliczalność i nierozstrzygalność

1. Udowodnić równoważność nast_{}epuj _{}acych warunków

• j_{}ezyk L jest cz_{}eściowo obliczalny,

• j_{}ezyk L jest dziedzin _{}a pewnej funkcji cz_{}eściowo obliczalnej,

• j_{}ezyk L jest zbiorem wartości pewnej funkcji cz_{}eściowo obliczalnej,

• j_{}ezyk L jest zbiorem wartości pewnej funkcji obliczalnej.

2. Udowodnić, że j_{}ezyk L jest obliczalny, wtedy i tylko wtedy, gdy jest skończony lub jest zbiorem wartości pewnej funkcji obliczalnej rosn _{}acej.

3. Udowodnić nast_{}epuj _{}ace twierdzenie Turinga–Posta : jeśli zarówno j_{}ezyk jak i jego uzupełnienie s _{}a cz_{}eściowo obliczalne, to s _{}a również obliczalne.

4. Udowodnić, że istnieje zbiór cz_{}eściowo obliczalny, którego uzupełnienie nie zawiera żadnego nieskończonego zbioru cz_{}eściowo obliczalnego.

5. Udowodnić, że istnieje automat z dwoma (sic !) licznikami A taki, że nie jest rozstrzygalne, czy A zatrzymuje si_{}e dla danej wejściowej n. Wskazówka : wykorzystać zadanie 13.

6. Udowodnić nierozstrzygalność nast_{}epuj _{}acego problemu Posta.

Dane s _{}a dwie listy słów : u_{1}, …, u_{n} ∈ Σ^{∗} i w_{1}, …, w_{n} ∈ Σ^{∗}. Pytanie, czy istnieje ci _{}ag indeksów i_{1}, …, i_{m} ∈ {1, …, n}, taki, że u_{i_{1}} … u_{i_{n}} = w_{i_{1}} … w_{i_{n}} ? Jeśli taki ci _{}ag istnieje, to słowo u_{i_{1}} … u_{i_{n}} (= w_{i_{1}} … w_{i_{n}}) nazywamy rozwi _{}azaniem danej instancji problemu Posta.

Wskazówka : Rozważyć zmodyfikowany problem Posta, w którym dodatkowo wymaga si_{}e, by pierwszymi słowami w rozwi _{}azaniu były u_{1} i w_{1} (tzn. i_{1} = 1). Redukcja zmodyfikowanego problemu do oryginalnego problemu Posta nie jest trudna. Z kolei przedstawić algoerytm, który dla dowolnej maszyny Turinga M i jej wejścia w konstruuje instancj_{}e P zmodyfikowanego problemu Posta w ten sposób, że P ma rozwi _{}azanie wtedy i tylko wtedy, gdy M akceptuje w. Rozwi _{}azaniem P (o ile istnieje) b_{}edzie właśnie akceptuj _{}ace obliczenie M na w.

7. Dowieść, że nast_{}epuj _{}ace problemy s _{}a nierozstrzygalne :

• Dana gramatyka bezkontekstowa G nad alfabetem Σ. Pytanie : czy L(G) = Σ^{∗} ? (Tzw. problem uniwersalności.) Wskazówka : Dla maszyny Turinga M, udane obliczenie jest ci _{}agiem c_{0}#c_{1}# … #c_{f}, gdzie c_{i} s _{}a konfiguracjami M, c_{0} jest konfiguracj _{}a pocz _{}atkow _{}a, c_{f} akceptuj _{}ac _{}a, oraz c_{i} ⊢_{M} c_{i+1}. Należy przedstawić algorytm, który dla dowolnej maszyny M konstruuje gramatyk_{}e G_{M} generuj _{}ac _{}a wszystkie ci _{}agi, które nie s _{}a udanymi obliczeniami. A zatem, gdybyśmy potrafili rozstrzygać problem uniwersalności, moglibyśmy również rozstrzygać problem niepustości (L(M) ≠ ∅ ?) dla maszyn Turinga, co jest niemożliwe (na mocy twierdzenia Rice’a).

• Dane dwie gramatyki bezkontekstowe G_{1}, G_{2}. Pytanie : czy L(G_{1}) ∩ L(G_{2}) ≠ ∅ ? Wskazówka : Podobnie jak poprzednie zadanie, ale należy wykorzystać operacj_{}e lustrzanego odbicia.

• Dana gramatyka bezkontekstowa G. Pytanie : czy G jest jednoznaczna (tzn. dla każedego słowa w L(G) istnieje dokładnie jedno drzewo wyprowadzenia). Wskazówka : wykorzystać problem Posta.

1.3 Złożoność obliczeniowa

1. Dowieść, że klasy P, NP i PSPACE s _{}a zamkni_{}ete na operacj_{}e *.

2. Problem domina. Instancja problemu domina obejmuje liczb_{}e naturaln _{}a M dan _{}a unarnie oraz skończony zbiór wzorców kostek domina, tzn. wektorów postaci (up, down, left, right ), gdzie up, down, left i right s _{}a binarnie zadanymi liczbami, które w tym kontekście nazywamy kolorami. (Liczba kolorów nie jest ograniczona, a wi_{}ec zależy od danej instancji problemu.) Pytanie brzmi: czy kwadrat M × M można pokryć kostkami domina w ten sposób, że s _{}asiednie kostki stykaj _{}a si_{}e bokami o tym samym kolorze, a na bokach kwadratu jest kolor 0 (“biały”). Zakładamy przy tym, że każdy wzorzec można wykorzystać dowolnie wiele razy, ale nie można go “obracać” (tzn. up jest zawsze górn _{}a kraw_{}edzi _{}a itd.).

Należy udowodnić, że problem domina jest NP-zupełny. Wskazówka : zastosować redukcj_{}e generyczn _{}a, tzn. wychodz _{}ac od dowolnej niedeterministycznej maszyny Turinga działaj _{}acej w czasie wielomianowym.

3. Udowodnić, że nast_{}epuj _{}acy problem dokładnego pokrycia (ang. exact cover) jest NPzupełny. Dana rodzina podzbiorów {1, 2, …, n} (liczby dane binarnie). Pytanie: czy istnieje podrodzina podzbiorów rozł _{}acznych, które w sumie daj _{}a {1, 2, …, n}.

Wskazówka : wykorzystać zadanie 2.

4. Udowodnić, że nast_{}epuj _{}acy problem plecakowy (ang. knapsack problem) jest NPzupełny. Dane: liczby n, m_{1}, …, m_{k} (binarnie). Pytanie: czy istnieje podzbiór zbioru {m_{1}, …, m_{k}} taki, że m_{1} + … + m_{k} = n.

Wskazówka : wykorzystać zadanie 3.