Maszyny Turinga

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 $\Sigma=\{ 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,\ldots,n-1$, reprezentujemy ciągiem zer i jedynek długości $n^{2}$, 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\cdot 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 $M_{1}$ i $M_{2}$ 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.)