Maszyny Turinga | Informatyka MIMUW

Skonstruować maszynę Turinga obliczającą funkcję $2^{n}$ reprezentowaną unarnie. Bardziej dokładnie, zakładamy, że alfabet wejściowy składa się z jednego symbolu, powiedzmy $\{ 1\}$ . Jeśli na wejściu dany jest ciąg $n$ jedynek, (tzn. konfiguracja wejściowa jest $q_{0}1^{n}$ ), to po wykonaniu obliczenia konfiguracja powinna być $q_{f}1^{{2^{n}}}$ .
Skonstruować maszynę Turinga obliczającą funkcję $\lceil\log n\rceil$ reprezentowaną unarnie.
Przyjmijmy Σ={0,1}. Skonstruować maszyny Turinga rozpoznające następujące języki:
1. zbiór palindromów
2. $\{ w\$ w\,:\, w\in\Sigma^{*}\}$
3. $\{ ww\,:\, w\in\Sigma^{*}\}$
4. zbiór ciągów reprezentujących binarnie liczby pierwsze.
Graf zorientowany o n wierzchołkach ponumerowanych 0,1,…,n−1, reprezentujemy ciągiem zer i jedynek długości n2, takim, że k-ty bit jest 1 o ile istnieje krawędź z wierzchołka o numerze i do wierzchołka o numerze j, gdzie k=i⋅n+j+1.
1. Skonstruować niedeterministyczną maszynę Turinga rozpoznającą zbiór słów zero-jedynkowych, które w powyższy sposób reprezentują te grafy, w których istnieje ścieżka z wierzchołka o numerze $0$ do wierzchołka o numerze $n-1$ .
2. Skonstruować maszynę deterministyczną realizującą to samo zadanie.
Przypomnijmy, że dwie maszyny Turinga o tym samym alfabecie wejściowym uważamy za równoważne o ile akceptują ten sam język. Udowodnić, że dla każdej maszyny Turinga istnieje równoważna jej maszyna posiadająca dokładnie jeden stan akceptujący i taka, że w konfiguracji akceptującej głowica znajduje się nad pierwszą komórką taśmy (tzn. konfiguracja akceptująca jest postaci $q_{f}\mbox{ co"s}$ ).
Dla danej niedeterministycznej maszyny Turinga skonstruować równoważną maszynę deterministyczną.
Dla danych deterministycznych maszyn Turinga M1 i M2 skonstruować deterministyczne maszyny rozpoznające języki
1. $L(M_{1})\cup L(M_{2})$
2. $L(M_{1})\cap L(M_{2})$
3. $L(M_{1})L(M_{2})$
4. $L(M_{1})^{{*}}$ .
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$ .
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ąpiony żadnym innym symbolem (w szczególności nie może być “zmazany” tj. zastąpiony przez “blank”). Dla dowolnej maszyny Turinga z jedną taśmą, skonstruować maszynę write-once z dwiema taśmami, która akceptuje ten sam język.

(*) Dowieść, że maszyny typu write-once z jedną taśmą akceptują jedynie języki regularne.
Dla dowolnej maszyny Turinga (nad dowolnym alfabetem), skonstruować równoważną maszyne o jednej taśmie i czterech stanach. (Wolno powiększyć alfabet roboczy.)
Pojęcie automatu ze stosem można rozszerzyć do automatu z $k$ stosami, $k\geq 2$ . Dowieść, że dla każdej maszyny Turinga istnieje równoważny jej deterministyczny automat z dwoma stosami. Wywnioskować stąd, że automat z $k$ stosami, $k>2$ może być symulowany przez automat z 2 stosami (symulację tę można również opisać bezpośrednio).
Udowodnić, że jeśli automat skończony wyposażyć dodatkowo w kolejkę, to otrzymany model ma siłe obliczeniową maszyny Turinga, tzn. dla dowolnej maszyny istnieje automat z kolejką, który rozpoznaje ten sam język.
Automat z $k$ licznikami $c_{1},\ldots,c_{k}$ , określamy podobnie jak automat z $k$ stosami, z tym, że liczniki zawierają liczby naturalne, a dostępne operacje na licznikach są postaci $c_{i}:=c_{i}+1$ , $c_{i}:=c_{i}\dot{-}1$ (gdzie $0\dot{-}1=0$ ), oraz test $c_{i}\stackrel{?}{=}0$ . Tzn. przejścia takiego automatu są postaci $q\rightarrow p$ , $q,c_{i}\stackrel{?}{=}0\rightarrow p$ , $q,c_{i}\stackrel{?}{\neq}0\rightarrow p$ , $q\rightarrow p,c_{i}:=c_{i}+1$ , $q\rightarrow p,c_{i}:=c_{i}\dot{-}1$ . Nie ma taśmy, lecz zakładamy, że w chwili początkowej dana wejściowa jest wartością licznika $c_{1}$ , a pozostałe liczniki mają wartość 0. Dowieść najpierw, że dla każdej maszyny Turinga nad alfabetem $\{ 1\}$ istnieje równoważny jej automat z 4 licznikami. Następnie 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.)