Problemy trudne obliczeniowo — Zadania

Czȩść pierwsza

Damian Niwiński

Marzec 2001

Zadania punktowane

1. Funkcja Ackermana (2 pt). Klas_{}e funkcji pierwotnie rekurencyjnych określamy jako najmniejszy zbiór PR funkcji N^{k} → N zawieraj _{}acy funkcje λx.x + 1, λx_{1} … x_{n}.0, λx_{1} … x_{n}.x_{i} (dla każdych 1 ≤ i ≤ n) oraz zamkni_{}ety na operacje

— złożenia: jeśli f : N^{k} → N oraz g_{i} : N^{m} → N, dla i = 1, …, k, należ _{}a do PR, to funkcja f(g_{1}, …, g_{k}) należy do PR^{1},

— rekursji pierwotnej: jeśli g i h s _{}a funkcjami o arnościach k i k + 2 odpowiednio, to funkcja f : N^{k+1} → N określona równaniami

f(0, x_{1}, …, x_{k}) = g(x_{1}, …, x_{k})
f(n + 1, x_{1}, …, x_{k}) = h(n, f(n, x_{1}, …, x_{k}), x_{1}, …, x_{k})

należy do PR.

Funkcja Ackermana A : N^{3} → N, określona jest równaniami rekurencyjnymi

A(0, 0, x) = 0
A(0, y + 1, x) = A(0, y, x) + 1
A(1, 0, x) = 0
A(z + 2, 0, x) = 1
A(z + 1, y + 1, x) = A(z, A(z + 1, y, x), x)

Nie trudno jest sprawdzić, że A(0, y, x) = x + y, A(1, y, x) = x · y, A(2, y, x) = x^{y}, oraz, że, dla każdego n, funkcja λxy.A(n, y, x) jest pierwotnie rekurencyjna. Dowieść, że funkcja A nie jest pierwotnie rekurencyjna.

Wskazówka. Dowieść, że dla każdej funkcji pierwotnie rekurencyjnej f : N → N, istnieje m, takie że f(n) ≤ A(m, n, n), dla prawie wszystkich n.

2. (1 pt, zamkni_{}ete) Dowieść, że problem, czy dana gramatyka bezkontekstowa generuje j_{}ezyk regularny jest algorytmicznie nierozstrzygalny.

1Dokładniej, mamy na myśli funkcj_{}e λx_{1} … x_{m}.f(g_{1}(x_{1} … x_{m}), …, g_{k}(x_{1} … x_{m})).

3. (3 pt) Powiemy, że rodzina zbiorów A ⊆ P (Σ^{∗}) (Σ = {0, 1}) jest rekurencyjnie prezentowalna, jeśli istnieje funkcja rekurencyjna f : Σ^{∗} → Σ^{∗}, taka że L ∈ A wtedy i tylko wtedy, gdy istnieje x ∈ Σ^{∗} takie, że L(M_{f(x)}) = L. Czy istnieje rekurencyjna prezentacja f rodziny wszystkich rekurencyjnie przeliczalnych podzbiorów Σ^{∗}, w której każdy zbiór jest prezentowany dokładnie raz (tzn. dla każdego x istnieje dokładnie jedno z, takie że W_{x} = L(M_{f(z)}))?

Powyższe pytanie można sformułować w sposób przypominaj _{}acy pewnik wyboru:

Dla x ∈ Σ^{∗}, niech A_{x} = {z : W_{z} = W_{x}}. Zauważmy, że rodzina {A_{x} : x ∈ Σ^{∗}} tworzy podział zbioru Σ^{∗}. Czy istnieje rekurencyjnie przeliczalny zbiór B maj _{}acy dokładnie jeden element wspólny z każdym A_{x}?

4. (1pt) Rozważamy maszyn_{}e Turinga z jedn _{}a taśm _{}a nieskończon _{}a w prawo. Dodatkowo nakładamy ograniczenie (ang. write-once), że maszyna 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”). Czy maszyna taka może rozpoznać j_{}ezyk nieregularny?

Uwaga. Jeśli przy ograniczeniu write-once pozwolimy używać dwóch taśm, to dowolny j_{}ezyk rekurencyjnie przeliczalny może być akceptowany w ten sposób.

5. (2 pt) Dowieść, że jeśli M jest deterministyczn _{}a maszyn _{}a Turinga i L(M) nie jest j_{}ezykiem regularnym, to istnieje stała c taka, że dla nieskończenie wielu słów w, maszyna M wykorzystuje co najmniej c · log log |w| komórek pami_{}eci.

(Wnika st _{}ad, że na przykład klasa DSPACE (log log log n) zawiera jedynie j_{}ezyki regularne.)

Zadania przygotowawcze

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, reprezentu-

jemy 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. 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.

6. (*) Udowodnić, że dla każdej maszyny Turinga (nad dowolnym alfabetem) istnieje równoważna jej maszyna o trzech stanach (oczywiście, maszyna ta ma na ogół wi_{}ekszy alfabet symboli roboczych).

7. 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 _{}a można również opisać bezpośrednio).

8. (*) Automat z k licznikami c_{1}, …, c_{k} jest zadany przez skończony ci _{}ag instrukcji postaci m : c_{i} := c_{i} + 1, m : c_{i} ˙−1, m : if c_{i} = 0 then m_{1} else m_{2}, STOP, gdzie m, m_{1}, m_{2} s _{}a etykietami instrukcji, x ˙−1 = x − 1, gdy x > 0 i 0 ˙−1 = 0. Zakładamy, że w chwili pocz _{}atkowej licznik c_{1} zawiera dan _{}a wejściow _{}a, 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 dwóch. (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.)

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. Dowieść, że nast_{}epuj _{}ace problemy s _{}a nierozstrzygalne :

• Dane dwie gramatyki bezkontekstowe G_{1}, G_{2}. Pytanie : czy L(G_{1}) ∩ L(G_{2}) ≠ 0 ?

• Dana gramatyka bezkontekstowa G nad alfabetem Σ. Pytanie : czy L(G) = Σ^{∗} ? Wskazówka : rozważać j_{}ezyk słów w$v^{R}, gdzie w i v s _{}a konfiguracjami maszyny Turinga M i w ⊢_{M} v.

6. Czy istnieje funkcja rekurencyjna f : N → N, taka że, dla każdego n, jeżeli zbiór L(M_{n}) jest rekurencyjny, to L(M_{f(n)}) = L(M_{n}), przy czym maszyna M_{f(n)} zatrzymuje si_{}e dla każdych danych? (Intuicyjnie, taka funkcja poprawiałaby, “tam gdzie si_{}e da”, maszyny Turinga do maszyn, które zawsze si_{}e zatrzymuj _{}a.)

7. Drugie twierdzenie Rice’a. Dowieść, że dla każdej nietrywialnej własności rekurencyjnie przeliczalnych podzbiorów N, tj. dla każdej rodziny zbiorów ∅ ⊂ S ⊂ {W_{n} : n ∈ N}, zbiór

L_{S} = {n : W_{n} ∈ S}

jest rekurencyjnie przeliczalny wtedy i tylko wtedy, gdy spełnione s _{}a nast_{}epuj _{}ace warunki:

• jeśli L ∈ S i L ⊆ L′, to L′ ∈ S,

• jeśli L ∈ S, to pewien skończony podzbiór L też należy do S,

• rodzina zbiorów skończonych należ _{}acych do S jest rekurencyjnie prezentowalna.

Wywnioskować st _{}ad, że nast_{}epuj _{}ace własności zbiorów rekurencyjnie przeliczalnych nie s _{}a rekurencyjnie przeliczalne:

• L = ∅

• L = N

• L jest skończony

• L jest rekurencyjny

• L nie jest rekurencyjny

• L jest semiliniowy

• L ∩ K̄ ≠ ∅

Natomiast nast_{}epuj _{}ace własności zbiorów rekurencyjnie przeliczalnych s _{}a rekurencyjnie przeliczalne:

• L ≠ ∅

• L zawiera co najmniej 10 elementów

• 1994 ∈ L

• L ∩ K ≠ ∅

8. Zbiory proste w sensie Posta. Dowieść, że istnieje rekurencyjnie przeliczalny zbiór liczb naturalnych, taki że jego uzupełnienie nie zawiera żadnego nieskończonego zbioru rekurencyjnie przeliczalnego.

9. Powiemy, że zbiór A ⊆ N jest m–sprowadzalny do zbioru B ⊆ N (notacja: A ≤_{m} B), jeśli istnieje funkcja rekurencyjna f : N → N, taka że

(∀n) n ∈ A ⇔ f(n) ∈ B

Zbiory A i B s _{}a m–równoważne (notacja: A ≡_{m} B), jeśli A ≤_{m} B i B ≤_{m} A. Dowieść, że nast_{}epuj _{}ace zbiory (por. def. poniżej) wyznaczaj _{}a rózne klasy abstrakcji:

K, K̄, K × K̄, K ⊕ K̄

Jakie relacje ≤_{m} zachodz _{}a pomi_{}edzy tymi zbiorami?

Uwaga. Dla A, B ⊆ N, definiujemy

A ⊕ B = {2x : x ∈ A} ∪ {2x + 1 : x ∈ B}

Natomiast

A × B = {⟨x, y⟩ : x ∈ A, y ∈ B}

gdzie ⟨ , ⟩ jest dowoln _{}a rekurencyjn _{}a funkcj _{}a pary.

10. Liczb_{}e rzeczywist _{}a nazywamy rekurencyjn _{}a, jeśli jej ci _{}ag cyfr w zapisie dziesi_{}etnym jest rekurencyjny. Innymi słowy, liczba r ∈ R jest rekurencyjna, o ile istnieje liczba całkowita a i funkcja rekurencyjna f : N → N, o wartościach w {0, 1, …, 9}, taka że

r = a + ∑_{n=1}^{∞} \frac{f(n)}{10^{n}}

Oczywiście, własność “być liczb _{}a rekurencyjn _{}a” nie zależy od wyboru podstawy systemu pozycyjnego.

(a) Dowieść, że liczby rekurencyjne tworz _{}a ciało rzeczywiście domkni_{}ete (tzn. każdy wielomian stopnia nieparzystego ma pierwiastek).

(b) Podać przykład funkcji rekurencyjnych f i g, takich że ci _{}ag f(n)/g(n) jest zbieżny do pewnej liczby rzeczywistej, ale liczba ta nie jest rekurencyjna.

11. Uwaga. W tym i w nast_{}epnych zadaniach należy zastosować twierdzenie o rekursji:

Dla dowolnej funkcji rekurencyjnej f, istnieje x takie, że W_{x} = W_{f(x)}.

Wykazać, że istnieje x ∈ Σ^{∗}, takie że W_{x} = {x}.

12. Wykazać, że istnieje x ∈ Σ^{∗}, takie że φ_{x} (tj. funkcja cz_{}eściowa obliczana przez maszyn_{}e o kodzie x) jest wsz_{}edzie określon _{}a funkcj _{}a stał _{}a, stale równ _{}a x.

13. Napisać program komputerowy P (np. w j_{}ezyku Pascal) nie przyjmuj _{}acy danych wejściowych ani nie komunikuj _{}acy si_{}e z otoczeniem, taki że w wyniku wykonania programu P na ekranie komputera wyświetla si_{}e tekst t, przy czym jest to właśnie dokładnie tekst programu P.