Obliczalność i nierozstrzygalność

1. Udowodnić równoważność następujących warunków
   1. język \(L\) jest częściowo obliczalny,
   2. język \(L\) jest dziedziną pewnej funkcji częściowo obliczalnej,
   3. język \(L\) jest zbiorem wartości pewnej funkcji częściowo obliczalnej,
   4. język \(L\) jest zbiorem wartości pewnej funkcji obliczalnej.
2. Udowodnić, że język \(L\) jest obliczalny, wtedy i tylko wtedy, gdy jest skończony lub jest zbiorem wartości pewnej funkcji obliczalnej rosnącej.
3. Udowodnić następujące twierdzenie Turinga–Posta : jeśli zarówno język jak i jego uzupełnienie są częściowo obliczalne, to są również obliczalne.
4. Udowodnić, że istnieje zbiór częściowo obliczalny, którego uzupełnienie nie zawiera żadnego nieskończonego zbioru częściowo obliczalnego.
5. Udowodnić, że istnieje automat z dwoma (sic !) licznikami \(A\) taki, że nie jest rozstrzygalne, czy \(A\) zatrzymuje się dla danej wejściowej \(n\). Wskazówka : wykorzystać zadanie ??.
6. Udowodnić nierozstrzygalność następującego problemu Posta.

   Dane są dwie listy słów : \(u_{1},\ldots,u_{n}\in\Sigma^{*}\) i \(w_{1},\ldots,w_{n}\in\Sigma^{*}\). Pytanie, czy istnieje ciąg indeksów \(i_{1},\ldots,i_{m}\in\{ 1,\ldots,n\}\), taki, że \(u_{{i_{1}}}\ldots u_{{i_{n}}}=w_{{i_{1}}}\ldots w_{{i_{n}}}\) ? Jeśli taki ciąg istnieje, to słowo \(u_{{i_{1}}}\ldots u_{{i_{n}}}\) (\(=w_{{i_{1}}}\ldots w_{{i_{n}}}\)) nazywamy rozwiązaniem danej instancji problemu Posta.

   Wskazówka : Rozważyć zmodyfikowany problem Posta, w którym dodatkowo wymaga się, by pierwszymi słowami w rozwiązaniu 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ę \(P\) zmodyfikowanego problemu Posta w ten sposób, że \(P\) ma rozwiązanie wtedy i tylko wtedy, gdy \(M\) akceptuje \(w\). Rozwiązaniem \(P\) (o ile istnieje) będzie właśnie akceptujące obliczenie \(M\) na \(w\).

7. Dowieść, że następujące problemy są nierozstrzygalne :
   1. Dana gramatyka bezkontekstowa \(G\) nad alfabetem \(\Sigma\). Pytanie : czy \(L(G)=\Sigma^{*}\) ? (Tzw. problem uniwersalności.) Wskazówka : Dla maszyny Turinga \(M\), udane obliczenie jest ciągiem \(c_{0}\# c_{1}\#\ldots\# c_{f}\), gdzie \(c_{i}\) są konfiguracjami \(M\), \(c_{0}\) jest konfiguracją początkową, \(c_{f}\) akceptującą, oraz \(c_{i}\vdash _{M}c_{{i+1}}\). Należy przedstawić algorytm, który dla dowolnej maszyny \(M\) konstruuje gramatykę \(G_{M}\) generującą wszystkie ciągi, które nie są udanymi obliczeniami. A zatem, gdybyśmy potrafili rozstrzygać problem uniwersalności, moglibyśmy również rozstrzygać problem niepustości (\(L(M)\neq\emptyset\) ?) dla maszyn Turinga, co jest niemożliwe (na mocy twierdzenia Rice'a).
   2. Dane dwie gramatyki bezkontekstowe \(G_{1},G_{2}\). Pytanie : czy \(L(G_{1})\cap (G_{2})\neq\emptyset\) ? Wskazówka : Podobnie jak poprzednie zadanie, ale należy wykorzystać operację lustrzanego odbicia.
   3. 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.

8. Czy następuący problem \(X\) jest rozstrzygalny:
   Dana gramatyka bezkontekstowa \(G\), sprawdzić czy \(L(G)\) zawiera palindrom.

9. Załóżmy, że wiemy że jednotasmowa deterministyczna maszyna Turinga \(M\) wykonuje zawsze co najwyzej jeden ńawrót” (to znaczy glowica przesuwa sie w prawo a od pewnego momentu już tylko w lewo). Czy problem “\(w\in L(M)\)” jest rozstrzygalny, gdzie \(w\) jest słowem wejściowym a \(L(M)\) oznacza zbiór słów akceptowanych przez \(M\) stanem akceptującym.

10. Czy następujący problem jest rozstrzygalny. Dane są dwa słowa \(u,w\in\Sigma^{*}\) oraz liczba \(k\), sprawdzić czy

    \(\left(\exists\ x\in\Sigma^{*}\right)\ \left(\ |x|>k\ \&\ \mathit{Ile}(w,x)=\mathit{Ile}(u,x)\ \right)\)

    gdzie \(\mathit{Ile}(w,x)\) oznacza liczbę wystąpień słowa \(w\) jako podsłowo \(x\) (wystąpienia nie muszą być rozłączne).

11. Niech \(\mathit{bin}(n)\) oznacza zapis binarny liczby naturalnej \(n\). Mamy \(|\mathit{bin}(n)|=\lfloor\log _{2}n\rfloor+1\) z wyjątkiem liczby 0, dla której \(|\mathit{bin}(0)|=1\). Określić obliczalną różnowartościową funkcję pary \(\{ 0,1\}^{*}\times\{ 0,1\}^{*}\), tak by

    \(|(x,y)|=|x|+|y|+\min\{|\mathit{bin}(|x|)|,|\mathit{bin}(|y|)|\}+{\cal O}(1)\)

12. Ustalamy pewne kodowanie maszyn Turinga, które pozwala nam utożsamiać maszynę \(M\) z pewnym słowem nad \(\{ 0,1\}\). Rozważmy funkcję \(C\), która parze \(\left(M,v\right)\) przyporządkowuje minimalną długość słowa \(x\), takiego że

    \(M(x)=v\)

    lub specjalny symbol \(\infty\), gdy nie ma takiego \(x\).

    1. Dowieść, że funkcja \(C\) nie jest obliczalna.

       Wskazówka. W przeciwnym razie obliczalna byłaby również funkcja, która liczbie \(n\) danej w postaci binarnej przyporządkowuje pewne słowo \(w\in(0+1)^{n}\), takie że

       \(\min\{|(M,x)|:M(x)=w\}\geq n\)

       (długość pary w rozumieniu za zadania ??). Biorąc za \(M\) maszynę obliczajacą tę funkcję oraz \(\mathit{bin}(n)\) za \(x\), otrzymujemy sprzeczność.

    2. Dowieść, że funkcja \(C\) z punktu ?? moze być przybliżana w następującym sensie. Istnieje maszyna Turinga, która dla wejścia \(\left(M,v\right)\) produkuje nieskończony ciąg liczb, który od pewnego miejsca ustala się na wartości \(C\left(M,v\right)\).

       Uwaga. Nie ma sprzeczności pomiędzy punktami ?? i ?? , ponieważ odbiorca powyższego ciągu nigdy nie wie, czy jest on już ustalony.