Informatyka MIMUW

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.

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

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.

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

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.

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

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

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.