Maszyny Turinga

  1. 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}}}\).
  2. Skonstruować maszynę Turinga obliczającą funkcję \(\lceil\log n\rceil\) reprezentowaną unarnie.
  3. 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.
  4. 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.
  5. 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}\)).
  6. Dla danej niedeterministycznej maszyny Turinga skonstruować równoważną maszynę deterministyczną.
  7. 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})^{{*}}\).
  8. 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\).
  9. 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.

  10. Dla dowolnej maszyny Turinga (nad dowolnym alfabetem), skonstruować równoważną maszyne o jednej taśmie i czterech stanach. (Wolno powiększyć alfabet roboczy.)
  11. 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).
  12. 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.
  13. 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.)