Złożoność obliczeniowa/Wykład 1: Obliczenia w modelu maszyny Turinga

Wprowadzenie

Zadaniem tego modułu jest wprowadzić podstawowe narzędzie, jakim dla teorii złożoności jest maszyna Turinga. Jest to pewien abstrakcyjny model maszyny liczącej, który ma trzy podstawowe własności:

• jest prosty koncepcyjnie.
• potrafi przeprowadzić dowolne obliczenie możliwe na innych znanych nam maszynach.
• zużycie zasobów podczas obliczenia dobrze modeluje rzeczywiste komputery.

Pierwsza własność jest bardzo istotna, gdyż pozwala formułować i dowodzić twierdzenia dotyczące maszyn używając tylko najprostszych pojęć matematycznych.

Druga własność jest związana ze słynną tezą Churcha mówiącą, że każdą funkcję, którą da się efektywnie obliczać, da się obliczać używając maszyny Turinga. Jest to stwierdzenie natury filozoficznej i nie może być matematycznie udowodnione, ale rzeczywicie żaden ze znanych sposobów reprezentowania obliczeń nie potrafi przedstawić nic więcej niż maszyna Turinga.

Trzecia własność jest najważniejszą dla teorii złożoności. W dalszej części kursu wykażemy, że zarówno czas, jak i pamięć zużyta podczas obliczenia maszyny Turinga nie różnią się bardzo od zasobów zużywanych podczas wykonania algorytmów na rzeczywistych komputerach. Sprawia to, że wyniki teorii złożoności mówiące o obliczeniach na maszynach Turinga pozostają w ścisłym związku z rzeczywistymi problemami informatyki i praktycznymi implementacjami algorytmów.

Notacje i pojęcia wprowadzone w tym module będą szeroko wykorzystywane w następnych. Dlatego nawet osoby dobrze znające pojęcia związane z maszynami Turinga powinny sprawdzić, czy znane im definicje są tymi samymi, które będą używane w dalszej części kursu.

Model obliczeń

Zacznijmy od odpowiedzi na pytanie, po co model obliczeń jest nam w ogóle potrzebny? Celem tego przedmiotu jest zbadanie jak złożone są różne problemy. Ale złożone dla kogo? Dla komputera oczywiście, bo to właśnie problemy rozwiązywane przez komputery nas interesują. Odpowiedź ta jest jak najbardziej poprawna, ale bardzo mało precyzyjna, bo dla jakiego komputera? Na świecie są miliony, jeżeli nie miliardy, komputerów i różnią się one od siebie możliwościami. Zadania, które wykonuje się łatwo na jednym z nich mogą być trudne, lub wręcz niemożliwe, do wykonania na innym.

Moglibyśmy wybrać jakiś konkretny komputer, albo nawet model komputera - powiedzmy „ZX Spectrum” (zakładając, że wszystkie jego egzemplarze pracują tak samo), ale niewiele by nas to posunęło do przodu - dopiero po zbadaniu i dokładnym opisaniu możliwości naszego komputera moglibyśmy zacząć budować teorię obliczeń na nim. Taki matematyczny opis działania komputera to właśnie model obliczeń.

W przypadku „ZX Spectrum” opis działania komputera musiałby uwzględniać organizację pamięci operacyjnej, strukturę procesora i jego operacje, oraz funkcje wejścia/wyjścia. To nie jest coś co można opisać łatwo, nawet w wypadku prostego komputera. Opis współczesnego komputera opartego o najnowocześniejsze rozwiązania technologiczne byłby jeszcze trudniejszy.

Pokazuje to, ze wybór „ZX Spectrum” na model obliczeń nie jest najszczęśliwszy. To dlatego, że nie jest on koncepcyjnie prosty. Dlatego musimy poszukiwać jakiegoś łatwiejszego.

Maszyna Turinga

Alan Turing (1912-1954)
Zobacz biografię

Maszyna Turinga została zaproponowana jako model „dowolnego możliwego obliczenia” przez Alana Turinga w 1936 roku. Czyli na całe dekady przed pojawieniem się pierwszego urządzenia, które moglibyśmy współcześnie nazwać komputerem. Powstała ona jako notacja do wyrażania algorytmów i służyła (głównie logikom) do określenia, jakie problemy są możliwe do algorytmicznego rozwiązania.

Maszyna Turinga jest bardzo prostym modelem komputera, który składa się z:

• nieograniczonej taśmy podzielonej na komórki, w których są zapisane zrozumiałe dla maszyny symbole.
• głowicy, która może się przesuwać po taśmie oraz odczytywać i zapisywać na niej symbole.
• mechanizmu sterującego, który może być w różnych stanach (ale skończenie wielu), który decyduje o działaniu maszyny. Na podstawie bieżącego stanu i symbolu znajdującego się pod głowicą podejmuje decyzje o:
  • zmianie zawartości komórki taśmy znajdującej się pod głowicą.
  • przesunięciu głowicy w lewo lub w prawo. Ponieważ taśma jest nieograniczona (czyli potencjalnie nieskończona), zawsze można wykonać przesunięcie.
  • zmianie stanu mechanizmu sterującego.

Zaskakująco prosty opis maszyny liczącej w porównaniu do tego, który musielibyśmy napisać, żeby opisać działanie „ZX Spectrum”.

Definicja formalna

Aby móc stworzyć formalną teorię obliczeń na maszynach Turinga potrzebujemy matematycznego opisu. Jest wiele różnych definicji formalnych i każda z nich mogłaby konkurować o miano najlepszej. Musimy jednak wybrać którąś z nich. W związku z tym proponujemy następującą:

Definicja 1

Maszyna Turinga $M$, to siódemka: M = $(Q,\Sigma ,\Gamma ,\#,\delta ,q_{0},F)$, gdzie:

$Q$ to skończony zbiór stanów maszyny.

$\Sigma$ to skończony zbiór symboli wejściowych, które służą do reprezentacji wejścia maszyny i są zapisane na taśmie przed rozpoczęciem obliczenia.

$\Gamma$ to skończony zbiór symboli taśmowych - są to wszystkie symbole jakie mogą się znajdować na taśmie. Oczywiście $\Sigma \subseteq \Gamma$.

$\#$ to symbol pusty - specjalny symbol taśmowy nie należący do symboli wejściowych. Symbol pusty będzie zawsze wypełniał prawie całą taśmę.

$\delta$ to funkcja przejścia. Jest to funkcja częściowa prowadząca z $Q\times \Gamma$ w $Q\times \Gamma \times \{\leftarrow ,\rightarrow \}$. Wartość $\delta (A,x)=(B,y,K)$ oznacza, że maszyna będąca w stanie $A$ i czytając symbol $x$ z taśmy przejdzie do stanu $B$, zapisze symbol $y$ na taśmie i przesunie głowicę o jedną komórkę w lewo ($K=\leftarrow$) lub w prawo ($K=\rightarrow$).

$q_{0}$ to stan początkowy w jakim znajduje się maszyna przed rozpoczęciem obliczenia.

$F$ to zbiór stanów akceptujących będący podzbiorem $Q$. Obliczenie maszyny kończy się kiedy osiągnięty zostanie któryś ze stanów $F$.

Działanie

Jak zatem uruchomić formalnie zdefiniowaną maszynę Turinga? Najpierw trzeba odpowiednio przygotować taśmę - można rozważać różne reprezentacje wejścia, ale w dalszych rozważaniach będziemy zakładać, że taśma jest wypełniona symbolami pustymi $\#$ oprócz skończonego spójnego fragmentu, na którym znajduje się słowo wejściowe składające się z symboli wejściowych.

Następnie należy ustawić głowicę nad którąś z komórek taśmy - tu znowu można zastosować różne podejścia, ale dla wygody będziemy ustawiać głowicę nad pierwszą komórką słowa wejściowego. Pozostaje już tylko ustawić mechanizm sterujący na stan $q_{0}$ i uruchomić maszynę.

Maszyna będzie działać zgodnie z algorytmem zapisanym w funkcji $\delta$ - będzie zmieniać swój stan, przesuwać głowicę i zmieniać zawartość taśmy. Tak będzie sią działo dopóki nie nastąpi jeden z dwóch warunków:

• Maszyna znajdzie się w stanie akceptującym. Mówimy wtedy, że obliczenie zakończyło się akceptująco.
• Maszyna znajdując się w stanie $A$ przeczyta z taśmy symbol $x$, a wartość funkcji częściowej $\delta (A,x)$ nie będzie zdefiniowana. Mówimy wtedy, że obliczenie zakończyło się błędem.

Może się również zdarzyć, że nigdy żaden z tych dwóch warunków nie nastąpi. W takim wypadku maszyna nie zakończy obliczenia.

Reprezentacja

Zanim przyjrzymy się przykładom konkretnych maszyn Turinga realizujących konkretne zadania przedstawimy dwa sposoby reprezentacji maszyn.

Pierwszy polega na przedstawieniu tabelki funkcji $\delta$. Możemy po prostu zapisywać w kolejnych wierszach ciągi $A,x:B,y,K$ oznaczające $\delta (A,x)=(B,y,K)$. Zazwyczaj nie jest wtedy potrzebne dokładne definiowanie pozostałych części maszyny. Symbolami taśmowymi są po prostu symbole występujące w tabelce, a dla symbolu pustego używa się standardowej notacji $\#$. To, które symbole są symbolami wejściowymi też zazwyczaj wynika z kontekstu i nie budzi wątpliwości. Dla oznaczenia stanów akceptujących można użyć pogrubienia. Jedynie określenie stanu początkowego wymaga dodatkowego komentarza do tabelki.

Można też przedstawić maszynę w wygodny sposób na diagramie. Każdy ze stanów maszyny reprezentujemy rysując prostokąt z nazwą stanu zapisaną wewnątrz prostokąta. Dla przejrzystości oznaczamy stany końcowe przez pogrubienie nazwy stanu.

Następnie łączymy prostokąty strzałkami etykietowanymi trzema symbolami - dwoma symbolami taśmowymi i symbolem $\leftarrow$ lub $\rightarrow$. Strzałka etykietowana $x,y,K$ prowadząca od stanu $A$ do stanu $B$ oznacza $\delta (A,x)=(B,y,K)$.

Przykład 2 [Maszyna dodająca dwie liczby w systemie unarnym]

Diagram maszyny dodającej dwie liczby

Możemy teraz przedstawić pierwszą maszynę Turinga. Będzie ona dodawać dwie liczby zapisane w systemie unarnym. Liczba naturalna $n$ jest reprezentowana w systemie unarnym przez $n+1$ jedynek zapisanych na taśmie obok siebie.

Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne $n$ i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle m} zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n+m} . W związku z tym, językiem wejściowym maszyny będzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Sigma = \{0,1\}} . Maszyna będzie miała 4 stany Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle Q = \{A,B,C,D\}} , stanem początkowym będzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A} , a jedynym stanem akceptującym będzie Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle D} .

Język maszyny. Języki rekurencyjne i rekurencyjnie przeliczalne

Maszyna z przykładu wykonywała bardzo pożyteczne zadanie. Dla określonego wejścia po zakończeniu działania pozostawiała na taśmie wynik dodawania. Można się domyślać, że inne działania arytmetyczne również można zakodować w algorytmie maszyny Turinga. Zachęcamy do zaprojektowania takiego kalkulatora. Czasem jednak jest całkiem nieistotne co maszyna pozostawia na taśmie, a interesuje nas tylko czy i w jaki sposób kończy swoje działanie.

Definicja 3

Językiem maszyny Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle M} nazwiemy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle L(M) \subseteq {\Sigma^\ast}} zbiór tych słów wejściowych, dla których obliczenie maszyny Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle M} kończy się w stanie akceptującym. Będziemy mówić, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle M} rozpoznaje język $L(M)$.

Definicja 4

Język $L\subseteq {\Sigma ^{\ast }}$ nazywamy rekurencyjnie przeliczalnym, albo częściowo rozstrzygalnym, jeżeli istnieje taka maszyna $M$, że $L=L(M)$.

Dlaczego język $L$ jest tylko częściowo rozstrzygalny? Ponieważ jeżeli słowo $w\in L$, to da się to sprawdzić - należy uruchomić maszynę $M$ na słowie $w$ i zostanie ono zaakceptowane. Natomiast jeżeli $w\notin L$, to niekoniecznie da się to sprawdzić. Możemy oczywiście uruchomić $M$ na $w$, ale jeżeli to obliczenie nigdy się nie kończy, to nigdy nie dowiemy się czy $M$ akceptuje $w$.

Żeby uchwycić własność pełnej rozstrzygalności definiujemy własność stopu dla maszyny Turinga.

Definicja 5

Mówimy, że $M$ ma własność stopu, jeżeli dla dowolnego słowa $w\in {\Sigma ^{\ast }}$ obliczenie $M$ na $w$ się kończy. Język $L\subseteq {\Sigma ^{\ast }}$ nazywamy rekurencyjnym, lub rozstrzygalnym, jeżeli istnieje maszyna Turinga $M$ z własnością stopu taka, że $L=L(M)$.

Własności i różnice pomiędzy językami rozstrzygalnymi i częściowo rozstrzygalnymi są bardzo ciekawe, ale świadomie nie będziemy się nimi tu zajmować. Prawie wszystkie języki z którymi się spotkamy w czasie tego kursu będą rozstrzygalne.

Przykład 6 [Maszyna rozpoznająca język $ww^{\leftarrow }$]

Diagram maszyny rozpoznającej język $ww^{\leftarrow }$

Przedstawimy teraz drugą maszynę Turinga, której zadaniem jest rozpoznanie konkretnego języka:

                        $\{ww^{\leftarrow }:w\in \{0,1\}\ast \}$

gdzie $w^{\leftarrow }$ oznacza słowo $w$ z odwróconą kolejnością liter.

Specyfikacja problemu narzuca język wejściowy  $\Sigma =\{0,1\}$. Maszyna, którą zaprezentujemy będzie miała 7 stanów $Q=\{A,B,C,D,E,F,G\}$. Stan $A$ będzie stanem początkowym, a jedynym stanem akceptującym będzie stan $G$.

Ćwiczenia

Ćwiczenie 7 [Język maszyny przykładowej

Udowodnij, że maszyna z przykładu rzeczywiście rozpoznaje język $ww^{\leftarrow }$.

Podpowiedź

Przeprowadź dowód indukcyjny ze względu na długość słowa wejściowego.

Rozwiązanie

Zauważmy, że jedynym stanem akceptującym jest stan $G$, a jedyne przejście do stanu $G$ pochodzi ze stanu $A$ przy symbolu $\#$. Ponieważ stan $A$ jest stanem początkowym, oznacza to, że aby maszyna zaakceptowała niepuste słowo $x$ musi ona powrócić jeszcze choć raz do stanu $A$. Przyglądając się ścieżkom, które umożliwiają powrót do stanu $A$ dochodzimy do wniosku, że maszyna $A$ akceptuje słowa postaci:

• $x$ jest słowem pustym.

• $x=0y0$ lub $x=1y1$, gdzie $A$ akceptuje słowo $y$.

Przeprowadzimy teraz dowód indukcyjny ze względu na długość słowa $x$, że $x$ należy do języka maszyny wtedy i tylko wtedy, gdy $x=ww^{\leftarrow }$ dla pewnego $w$.

Dla długości równej $0$ teza jest trywialna. Krok indukcyjny dowodzimy dla $x$ o długości większej od zera. Słowo $x$ należące do języka maszyny nie jest zatem słowem pustym i jest postaci $0y0$ lub $1y1$, a $y$ jest postaci $vv^{\leftarrow }$. To z kolei jest równoważne $x=(0v)(0v)^{\leftarrow }$ lub $x=(1v)(1v)^{\leftarrow }$.

Ćwiczenie 8 [Mnożenie liczb unarnych]

Skonstruuj maszynę analogiczną do maszyny dodającej, która wykona mnożenie dwóch liczb zapisanych unarnie.

Podpowiedź

Skonstruuj maszynę odejmującą jeden od liczby zapisanej unarnie, a następnie połącz ją z maszyną dodającą.

Rozwiązanie

Przedstawimy maszynę, która po kolei zrealizuje etapy obliczenia:

1. skróci zapis pierwszej liczby o jedną jedynkę i przejdzie na koniec wejścia:

${\begin{aligned}A,1&:B,\#,\rightarrow \\B,1&:B,1,\rightarrow \\B,0&:B,0,\rightarrow \\\end{aligned}}$

2. dopisze reprezentację liczby $0$, czyli jedną jedynkę za wejściem i przejdzie z powrotem na początek wejścia:

${\begin{aligned}B,\#&:C,0,\rightarrow \\C,\#&:D,1,\leftarrow \\D,0&:D,0,\leftarrow \\D,1&:D,1,\leftarrow \\D,\#&:E,\#,\rightarrow \\\end{aligned}}$

3. dopóki pierwsza liczba wejścia nie zostanie całkiem zamazana będzie zamazywać jedną komórkę i przechodzić do drugiej liczby:

${\begin{aligned}E,1&:F,\#,\rightarrow \\F,1&:F,1,\rightarrow \\F,0&:G,0,\rightarrow \\\end{aligned}}$

4. i dopisywać ją do wyniku:

${\begin{aligned}G,1&:H,*,\rightarrow \\H,1&:I,*,\rightarrow \\I,1&:I,1,\rightarrow \\I,0&:I,0,\rightarrow \\I,\#&:J,1,\leftarrow \\J,1&:J,1,\leftarrow \\J,0&:K,0,\leftarrow \\K,1&:L,1,\leftarrow \\L,*&:H,*,\rightarrow \\K,*&:M,1,\leftarrow \\M,*&:M,1,\leftarrow \\M,0&:M,0,\leftarrow \\M,1&:M,1,\leftarrow \\M,\#&:E,\#,\rightarrow \\\end{aligned}}$

5. a jeżeli liczba jest już zamazana, to usunie też drugą liczbę i pozostawi sam wynik:

${\begin{aligned}E,0&:N,\#,\rightarrow \\N,1&:N,\#,\rightarrow \\N,0&:\mathbf {Z} ,\#,\rightarrow \end{aligned}}$

Ćwiczenie 9 [Źle ustawiona głowica]

Załóżmy, że głowica nie byłaby ustawiana na początku słowa wejściowego, tylko w dowolnym miejscu na taśmie. Pokaż, że można napisać program maszyny Turinga, który „znajdzie” początek słowa wejściowego i ustawi tam głowicę.

Załóż, że maszyna pracuje nad alfabetem $\Sigma =\{0,1\}$ oraz, że słowo wejściowe jest niepuste.

Podpowiedź

Gdyby było wiadomo, że słowo znajduje się „na lewo”, lub „na prawo” od pozycji początkowej głowicy, to wystarczyłoby skierować głowicę w odpowiednim kierunku. Ponieważ nie masz takiej informacji, to musisz przeglądać taśmę w obu kierunkach jednocześnie.

Podpowiedź

Dodaj dodatkowy symbol do alfabetu $\Gamma$, którego użyjesz jako znacznika miejsc odwiedzonych w poszukiwaniu słowa wejściowego. Nie zapomnij na końcu usunąć znaczników z taśmy!

Rozwiązanie

Przedstawimy maszynę, która używa dodatkowego symbolu $*\in \Gamma$ na oznaczenie komórek już odwiedzonych przez głowicę. Maszyna rozpoczyna w stanie $A$ i poszerza odwiedzony obszar z lewej i z prawej strony aż znajdzie słowo wejściowe. Kiedy w końcu trafi na komórkę zawierającą $0$ lub $1$, to usuwa wszystkie $*$ z taśmy i ustawia się na początku słowa wejściowego w stanie $Z$.

${\begin{aligned}A,\#&:B,*,\rightarrow \\B,*&:B,*,\rightarrow \\B,\#&:C,*,\leftarrow \\C,*&:C,*,\leftarrow \\C,\#&:B,*,\rightarrow \\A,0&:D,0,\leftarrow \\A,1&:D,1,\leftarrow \\D,0&:D,0,\leftarrow \\D,1&:D,1,\leftarrow \\D,*&:D,\#,\leftarrow \\D,\#&:\mathbf {Z} ,\#,\rightarrow \\E,*&:E,\#,\rightarrow \\E,0&:D,0,\leftarrow \\E,1&:D,1,\leftarrow \\B,0&:F,0,\leftarrow \\B,1&:F,0,\leftarrow \\F,*&:F,*,\leftarrow \\F,\#&:E,\#,\rightarrow \\A,0&:G,0,\rightarrow \\A,1&:G,1,\rightarrow \\G,*&:G,*,\rightarrow \\G,\#&:D,\#,\leftarrow \end{aligned}}$

Ćwiczenie 10 [Obliczenie z „czystą” taśmą]

Pokaż, że jeżeli maszyna $M$ rozpoznaje język $L$, to można ją zmodyfikować tak, żeby nowa maszyna $M'$ również rozpoznawała język $L$, ale po zakończeniu jej działania taśma była w całości wypełniona symbolem pustym.

Podpowiedź

Zmodyfikuj alfabet $\Gamma$ tak, żeby dało się stwierdzić które komórki mogły być odwiedzone podczas obliczenia.

Rozwiązanie

Zauważmy, że po zakończeniu obliczenia $M$ musimy zamienić wszystkie wystąpienia symboli innych niż $\#$. Kłopot może sprawić to, że ciągi takich symboli mogą być oddzielone od siebie znakami pustymi i nie wiadomo, czy na lewo (lub na prawo) od danej pozycji są jeszcze symbole inne niż $\#$.

Zmodyfikujemy teraz działanie maszyny $M$ dodając nowy symbol taśmowy $*$, który będzie miał znaczenie „to jest symbol pusty zapisany na taśmie przez maszynę $M$”. Musimy zmienić funkcję $\delta$ tak, żeby czytając znak $*$ zachowywała się dokładnie tak samo, jak gdyby przeczytała $\#$. Jednocześnie za każdym razem kiedy funkcja $\delta$ wskazywała, że należy zapisać na taśmie symbol $\#$, teraz należy zapisać symbol $*$.

Ta modyfikacja nie zmienia języka rozpoznawanego przez $M$, gdyż możemy patrzeć na wystąpienia symbolu $*$ jak na wystąpienia $\#$ i wtedy całe obliczenie wygląda tak samo.

Musimy teraz „wykryć” zakończenie obliczenia maszyny i przejść do specjalnego stanu „czyszczącego-akceptującego” lub „czyszczącego-błędnego”. Wszystkie przejścia do stanów akceptujących modyfikujemy tak, żeby przechodziły do „czyszczącego-akceptującego”. Z kolei wszystkie niezdefiniowane przejścia ustawiamy tak, żeby prowadziły do stanu „czyszczącego-błędnego”.

Zauważmy, że dla nowej maszyny ciąg symboli różnych od $\#$ jest spójny - są to wszystkie komórki taśmy, nad którymi znajdowała się maszyna podczas obliczenia. Możemy w związku z tym odnaleźć jego początek (korzystając na przykład z maszyny zdefiniowanej w poprzednim ćwiczeniu, choć w tym wypadku zadanie jest łatwiejsze) i zamazać wszystkie symbole aż do końca.

Kiedy taśma jest już pusta możemy przejść do stanu akceptującego lub umyślnie wykonać błąd w zależności od tego, czy dokonaliśmy czyszczenia „akceptującego”, czy „błędnego”.

Ćwiczenie 11 [Suma i przecięcie języków rozstrzygalnych]

Pokaż, że jeżeli języki $L_{1}\in {\Sigma ^{\ast }}$ i $L_{2}\in {\Sigma ^{\ast }}$ są rozstrzygalne, to języki $L_{1}\cap L_{2}$ i $L_{1}\cup L_{2}$ są rozstrzygalne.

Podpowiedź

Użyj maszyn $M_{1}$ i $M_{2}$ z własnością stopu rozpoznających języki $L_{1}$ i $L_{2}$. Stwórz alfabet nowej maszyny $\Gamma =\Sigma \cup \Gamma _{1}\times \Gamma _{2}$ z alfabetów obu maszyn. Zamień symbol wejściowy $a$ na symbol $(a,a)$. Możesz teraz tak uruchomić odpowiednio zmodyfikowane maszyny $M_{1}$ i $M_{2}$, aby ich obliczenia nawzajem na siebie nie „zachodziły”.

Rozwiązanie

Postępujemy zgodnie z podpowiedzią i używając maszyn z własnością stopu $M_{1}$ i $M_{2}$ rozpoznających odpowiednio $L_{1}$ i $L_{2}$ definiujemy nową maszynę $M$, która ma zasymulować uruchomienie obu maszyn na tym samym wejściu.

Alfabetem symboli taśmowych będzie $\Gamma =\Sigma \cup \Gamma _{1}\times \Gamma _{2}$. Symbolem pustym jest teraz $(\#_{1},\#_{2})$.

Dokonujemy modyfikacji maszyn $M_{1}$ i $M_{2}$, tak żeby po zakończeniu ich działania taśma była pusta oprócz jednej komórki zawierającej symbol 1 jeżeli słowo zostało zaakceptowane, lub 0 jeżeli zostało odrzucone (jest to prosta modyfikacja pomysłu wykorzystanego w poprzednim ćwiczeniu).

Następnie wprowadzamy dalsze modyfikacje tak, żeby maszyna $M_{1}$ w swoim obliczeniu korzystała tylko z pierwszej współrzędnej alfabetu taśmowego. Po prostu produkcję $\delta _{1}(A,x)=(B,y,K)$ zamieniamy na zbiór produkcji postaci $\delta (A,(x,g))=(B,(y,g),K)$ po wszystkich $g\in \Gamma _{2}$. Podobną modyfikację wykonujemy dla drugiej maszyny.

Wiemy, że maszyny $M_{1}$ i $M_{2}$ miały własność stopu. Ich modyfikacje nie zmieniły tego faktu. Możemy w związku z tym skonstruować maszynę $M$ z własnością stopu, która po kolei:

• przepisuje litery słowa wejściowego $a\in \Sigma$ na pary $(a,a)$.

• wraca na początek słowa i uruchamia zmodyfikowaną wersję maszyny $M_{1}$.

• odszukuje początek słowa na drugich współrzędnych i uruchamia zmodyfikowaną wersję maszyny $M_{2}$.

• po zakończeniu obliczenia obu maszyn co najwyżej dwie komórki na taśmie są niepuste. Maszyna może osobno odczytać wynik na pierwszej współrzędnej i osobno na drugiej. W zależności od tego, czy $M$ miało rozpoznawać sumę, czy przecięcie języków, maszyna przechodzi do stanu akceptującego gdy jeden, lub oba obliczenia pozostawiły po sobie 1 zapisaną na taśmie.

Zauważmy, że tej samej metody nie można zastosować do skonstruowania maszyny rozpoznającej sumę języków częściowo rozstrzygalnych. W takim przypadku obliczenie zmodyfikowanej maszyny $M_{1}$ może się nigdy nie zakończyć dla słów należących do $M_{2}$. Aby rozwiązać takie zadanie będziemy musieli użyć innych technik.

Zapis programu i stanu maszyny

Bardzo ciekawą i istotną własnością jest to, że opis dowolnej maszyny Turinga można zapisać na taśmie. Takiego kodowania maszyny na taśmie można dokonać na wiele różnych sposobów. Przyjrzymy się jednemu z nich.

Zauważmy, że dla działania maszyny nie są istotne „nazwy” elementów ze zbioru $\Gamma$ i $Q$. Możemy zatem założyć, że są to kolejne liczby naturalne. Wtedy do opisu maszyny wystarczy zapisać:

1. $q$ - liczbę elementów w zbiorze $Q$. Dalej zakładamy, że $Q=\{0,1,\ldots ,q-1\}$.

2. $s$ - liczbę elementów w zbiorze $\Sigma$.

3. $g$ - liczbę elementów w zbiorze $\Gamma$. Wygodnie jest założyć, że numeracja w $\Sigma \subseteq \Gamma$ pokrywa się z tą w $\Gamma$. Dzięki temu nie trzeba rozróżniać tych dwóch numeracji.

4. $s\leq b<g$ - numer symbolu pustego.

5. $d$ - liczbę zdefiniowanych wartości funkcji $\delta$.

6. Następnie $d$ piątek liczb naturalnych $A<q$, $X<g$, $B<q$, $Y<g$, $K\in \{0,1\}$ oznaczających, że
     $\delta (A,X)=(B,Y,\leftarrow )$, gdy $K=0$.
     $\delta (A,X)=(B,Y,\rightarrow )$, gdy $K=1$.

Możemy zatem zapisać te liczby w systemie unarnym oddzielając je pojedynczymi zerami i potraktować wynikowy napis jako słowo wejściowe nad alfabetem wejściowym $\{0,1\}$. Bardzo istotne jest, że słowo to ma skończoną długość - będziemy z tej skończonej reprezentacji nieraz korzystać.

Ćwiczenia

Ćwiczenie 12 [Konfiguracja maszyny]

Podobnie jak zapisaliśmy maszynę jako słowo wejściowe nad alfabetem $\{0,1\}$, możemy w podobny sposób zakodować opis sytuacji w jakiej znajduje się obliczenie maszyny w dowolnej chwili.

Przedstaw takie kodowanie tego opisu.

Podpowiedź

Dla zakodowania całego opisu obliczenia maszyny trzeba zapisać stan maszyny, zawartość taśmy i pozycję głowicy.

Rozwiązanie

Zauważmy, że zawartość taśmy, mimo że jest potencjalnie nieskończona, to w każdym momencie obliczenia wymagane jest opisanie tylko skończonej liczby komórek - wiemy, że pozostałe są wypełnione symbolem pustym. Możemy zatem zapisać ciąg liczb w systemie unarnym pooddzielanych zerami:

• $q$ - numer stanu w którym znajduje się maszyna

• $t$ - liczba komórek taśmy, które wymagają opisu

• Następnie ciąg $T$ składający się z $t$ liczb, gdzie liczba $T_{i}$ oznacza numer symbolu z $\Gamma$, który jest zapisany w $i$-tej komórce.

• $h$ - numer komórki w ciągu $T$ nad którą znajduje się głowica.

Zasoby potrzebne do obliczenia maszyny

Przy projektowaniu algorytmów komputerowych bardzo istotna jest ilość czasu i pamięci potrzebnych do ich wykonania. Dla maszyn Turinga można bardzo łatwo badać zużycie czasu i pamięci.

Definicja 13

Czas obliczenia maszyny $M$ na konkretnym słowie wejściowym $w$ - $T(M,w)$ to liczba kroków wykonanych zanim maszyna się zatrzymała. Jeżeli $M$ nigdy się nie zatrzyma, to mówimy, że czas obliczenia jest nieskończony i zapisujemy $T(M,w)=\infty$.

Możemy też zdefiniować czas działania samej maszyny.

Definicja 14

Funkcja $f:\mathbb {N} \rightarrow \mathbb {N}$ jest złożonością czasową dla maszyny $M$, jeżeli

$\forall _{n\in \mathbb {N} }:f(n)=max\{T(M,w):w\in \Sigma ^{n}\}$

Odpowiada to intuicji, że $f(n)$ jest równe czasowi wystarczającemu do obliczenia na dowolnym $n$-literowym słowie wejściowym. Zauważmy, że dla maszyny bez własności stopu nie można podać złożoności czasowej.

Wprowadzamy również podobne definicje dla pamięci wymaganej dla obliczenia związane z liczbą komórek taśmy użytych podczas obliczenia.

Definicja 15

Pamięć potrzebną do obliczenia maszyny $M$ na słowie $w$ - $S(M,w)$ definiujemy jako liczbę komórek taśmy, które zostały odwiedzone przez głowicę zanim maszyna się zatrzymała. Jeżeli $M$ nie zatrzymuje się na $w$, to wartość $S(M,w)$ jest nieokreślona.

Definicja 16

Mówimy, że funkcja $f:\mathbb {N} \rightarrow \mathbb {N}$ jest złożonością pamięciową maszyny $M$ z własnością stopu, jeżeli

$\forall _{n\in \mathbb {N} }:f(n)=max\{S(M,w):w\in \Sigma ^{n}\}$

Dzięki założeniu o własności stopu dla maszyny $M$ wszystkie wartości są dobrze określone, a $f(n)$ jest równe pamięci wystarczającej do wykonania obliczenia $M$ na dowolnym $n$-literowym słowie wejściowym.

Ćwiczenia

Ćwiczenie 17 [Czas i pamięć potrzebna przykładowym maszynom]

Spróbuj określić złożoność czasową i pamięciową dla przykładowych maszyn - dodającej i rozpoznającej język $ww^{\leftarrow }$.

Podpowiedź

	Złożoność czasowa	Złożoność pamięciowa
Maszyna dodająca	$f(0)=1$ $f(1)=3$ $f(n)=n+3;n\geq 2$	$f(0)=2$ $f(1)=3$ $f(n)=n+1;n\geq 2$
Maszyna rozpoznająca $ww^{\leftarrow }$	$f(n)=6+8+\ldots +(n+3)+2;n=2k+1$ $f(n)=5+7+\ldots +(n+3)+1;n=2k$	$f(n)=n+1$

Rozwiązanie

Żeby określić złożoność czasową i pamięciową maszyny dodającej wystarczy zauważyć, że maszyna czytając dowolny ciąg $n$ zer i jedynek przesunie się $n$ razy w prawo (dochodząc do $n+1$ pozycji na której jest zero), a potem cofnie się co najwyżej trzy razy (o ile są dwie jedynki na końcu). Ponieważ dla słów krótszych niż $2$-znakowe niemożliwe są dwie jedynki na końcu, a możliwe jest wycofanie głowicy przed słowo wejściowe - należy te przypadki rozważyć osobno. Otrzymuje się wyniki podane w podpowiedzi.

Analiza maszyny rozpoznającej język $ww^{\leftarrow }$ jest prostsza (mimo, że maszyna jest bardziej skomplikowana), ponieważ nie występują przypadki brzegowe. Złożoność pamięciowa wynosi $n+1$, gdyż maszyna używa zawsze dokładnie $n+1$ pierwszych komórek.

Złożoność czasowa wynika w rekurencyjnego wzoru $f(n)=n+3+f(n-2)$ z bazą $f(0)=1$ i $f(1)=2$. Rozwiązaniem rekursji dla $n\geq 2$ jest:

${\begin{aligned}f(n)={\frac {n-1}{2}}(6+{\frac {n+3}{2}});n=2k+1\\f(n)={\frac {n}{2}}(5+{\frac {n+3}{2}});n=2k\end{aligned}}$

Jak widać, nawet dla prostych maszyn oszacowanie dokładnych wartości złożoności czasowej i pamięciowej przysparza sporych kłopotów. Dlatego prawie nigdy nie będziemy rozważać dokładnych wartości tych funkcji i będziemy szeroko korzystać z notacji ${\mathcal {O}}$.

Wielotaśmowa maszyna Turinga

Wielotaśmowa maszyna Turinga

Interesującym rozszerzeniem modelu maszyny Turinga jest dodanie do jej mechanizmu dodatkowych taśm. $k$-taśmowa maszyna Turinga różni się od zwykłej maszyny Turinga tym, że ma $k$ niezależnych głowic, które poruszają się po różnych taśmach - każda z nich jest nieograniczona. W nowym modelu, mechanizm sterujący podejmuje decyzje na podstawie aktualnego stanu i odczytów ze wszystkich głowic. Dokonuje zapisów i przesunięć na każdej z taśm niezależnie. Co więcej, o ile w przypadku zwykłych maszyn Turinga wymagaliśmy przesunięcia głowicy, to teraz pozwalamy, żeby głowice pozostawały na swoich miejscach.

Żeby sformalizować sposób podawania wejścia do maszyny wielotaśmowej zakładamy, że słowo wejściowe jest zapisane na pierwszej taśmie, a pozostałe taśmy są w całości wypełnione symbolami pustymi. Natomiast definicje akceptacji i zakończenia obliczenia z błędem pozostają takie same jak w przypadku zwykłej maszyny Turinga.

Maszyna off-line

Maszyna off-line jest z kolei zawężeniem modelu maszyny wielotaśmowej. Modyfikacja polega na tym, że maszynie off-line nie wolno dokonywać zmian taśmy wejściowej. Rozważa się też maszyny off-line z taśmą wyjściową - wtedy dodatkowym ograniczeniem jest to, że głowica na ostaniej taśmie może tylko zapisywać symbole i przesuwać się tylko w prawo. Taki model odpowiada sytuacji w której program ma wejście i wyjście na osobnych taśmach, a pozostałe taśmy pełnią funkcję pamięci roboczej.

Złożoność

O ile definicje związane ze złożonością czasową zwykłej maszyny Turinga można bez zastrzeżeń stosować do maszyn wielotaśmowych, to definicje użytej pamięci wymagają pewnego komentarza. W przypadku zwykłej maszyny wielotaśmowej licząc liczbę komórek używanych podczas obliczenia sumujemy liczby użytych komórek na każdej z taśm.

W przypadku maszyn off-line do komórek używanych zaliczamy tylko komórki z taśm roboczych - nie uwzględniamy przy sumowaniu komórek taśmy wejściowej i wyjściowej (jeżeli taka istnieje). Takie podejście pozwala badać bardzo ciekawe obliczenia z pamięcią mniejszą niż rozmiar danych wejściowych.

Ćwiczenia

Ćwiczenie 18 [Definicje funkcji przejścia]

Sformalizuj definicję funkcji przejścia dla $k$-taśmowej maszyny Turinga w wersji normalnej i off-line.

Podpowiedź

Przyjrzyj się definicji zwykłej maszyny Turinga i zmodyfikuj jej argumenty i wynik tak, żeby można było wyrazić dostęp do $k$ taśm. Który element jest niepotrzebny w wypadku maszyny off-line?

Rozwiązanie

Formalna definicja funkcji przejścia dla $k$-taśmowej maszyny Turinga musi zależeć od stanu i odczytu ze wszystkich $k$ taśm i decydować o zmianie stanu i wszystkich $k$ głowic. W związku z tym ma postać:

$\delta :Q\times \Gamma ^{k}\rightarrow Q\times (\Gamma \times \{\leftarrow ,\bullet ,\rightarrow \})^{k}$

Wersja off-line nie może dokonywać zapisu na pierwszej taśmie, stąd funkcja przyjmuje postać:

$\delta :Q\times \Gamma ^{k}\rightarrow Q\times \{\leftarrow ,\bullet ,\rightarrow \}\times (\Gamma \times \{\leftarrow ,\bullet ,\rightarrow \})^{k-1}$

Wersja off-line z taśmą wyjściową dodatkowo nie może dokonywać odczytów z ostatniej taśmy. W związku z tym funkcja przyjmuje postać:

$\delta :Q\times \Gamma ^{k-1}\rightarrow Q\times \{\leftarrow ,\bullet ,\rightarrow \}\times (\Gamma \times \{\leftarrow ,\bullet ,\rightarrow \})^{k-2}\times \Gamma \times \{\bullet ,\rightarrow \}$

Ćwiczenie 19 [Symulacja maszyny $k$-taśmowej]

Pokaż, że dla języka rozpoznawanego przez $k$-taśmową maszynę Turinga $M_{(k)}$ o złożoności czasowej ${\mathcal {O}}(f(n))$ da się skonstruować zwykłą maszynę Turinga $M$ o złożoności czasowej ${\mathcal {O}}(f(n)^{2})$.

Podpowiedź

Wykorzystaj pomysł z ćwiczenia o sumie i przecięciu języków rekurencyjnych, aby zakodować zawartość $k$-taśm na jednej taśmie. Użyj kopii alfabetu taśmowego do zaznaczenia pozycji głowicy na każdej z taśm.

Rozwiązanie

Zakładamy, że maszyna $M_{(k)}$ została zmodyfikowana tak jak w ćwiczeniu o „czystym” obliczeniu i używa symbolu $*$ do oznaczenia komórek z symbolem pustym zapisanym podczas obliczenia. Pozwoli to określić które fragmenty taśmy zawierają „istotne” informacje.

Maszyna $M$ będzie pracować przy alfabecie wejściowym $\Sigma =\Sigma _{(k)}$ i taśmowym $\Gamma =\Sigma _{k}\cup {(\Gamma _{(k)}\cup {\underline {\Gamma _{(k)}}})}^{k}$. Gdzie ${\underline {\Gamma _{(k)}}}=\{{\underline {A}}:A\in \Gamma _{(k)}\}$ jest kopią alfabetu taśmowego, a symbol ${\underline {A}}$ oznacza, że na taśmie jest symbol $A$ i głowica znajduje się nad tą właśnie komórką.

Stany Maszyny $M$ to $Q=Q_{(k)}\cup Q_{(k)}\times {(\Gamma _{(k)}\cup \{\sqcup \})}^{k}$. Stany z $Q_{(k)}$ będą odpowiadać stanom maszyny $M_{(k)}$, a stany $(q,A_{1},A_{2},\ldots ,A_{k})$ sytuacji w której maszyna $M_{(k)}$ jest stanie $q$, a na taśmie $k$ pod głowicą jest $A_{k}$. Symbolu $\sqcup$ na $i$-tej pozycji używamy, kiedy jeszcze nie wiemy co jest pod głowicą na $i$-tej taśmie.

Maszyna $M$ będzie działać w następujący sposób:

• przepisze wejście z wartości $a$ na $({\underline {a}},{\underline {\#}},\ldots ,{\underline {\#}})$ w wypadku pierwszego symbolu i $(a,\#,\#,\ldots ,\#)$ w wypadku pozostałych.

• będąc w stanie odpowiadającym stanowi $q$ maszyny $M_{(k)}$ i na lewym końcu taśmy (do znalezienia lewego końca taśmy używamy symboli $*$ i metody z ćwiczenia o ,,czystym obliczeniu)

• przejdzie do stanu $(q,\sqcup ,\sqcup ,\ldots ,\sqcup )$ i przeglądnie zawartość taśmy aż do prawego końca uzupełniając informację w stanie. Tzn. kiedy napotkana zostanie komórka z symbolem $(x_{1},\ldots ,{\underline {x_{i}}},\ldots ,x_{k})$, to w stanie $(q,A_{1},\ldots ,A_{i},\ldots ,A_{k})$ wartość na $i$-tej współrzędnej stanu zmienia się z $\sqcup$ na $x_{i}$.

• Posiadając już pełną informację o odczytach ze wszystkich taśm dokona jeszcze jednego przeglądnięcia taśmy w którym zostaną zmienione symbole taśmowe (na każdej ze współrzędnych osobno zgodnie z programem maszyny $M_{(k)}$.

Jeżeli maszyna $M_{(k)}$ działa dla wejścia rozmiaru $n$ w czasie ${\mathcal {O}}(f(n))$, to działanie maszyny $M$ zakończy się po wykonaniu ${\mathcal {O}}(f(n))$ pętli przeglądających całą używaną taśmę. Wykonanie pojedynczej pętli odbywa się w czasie proporcjonalnym do długości użytej części taśmy. Tą z kolei możemy ograniczyć do ${\mathcal {O}}(f(n))$ komórek na lewo i ${\mathcal {O}}(f(n))$ komórek na prawo od pozycji początkowej - gdyż żadna z głowic w czasie ${\mathcal {O}}(f(n))$ nie może pokonać większej odległości. W związku z tym otrzymujemy oszacowanie ${\mathcal {O}}(f(n)^{2})$ na złożoność czasową wynikowej maszyny.

Ćwiczenie 20 [Symulacja na maszynie off-line]

Pokaż jak zasymulować $k$-taśmową maszynę Turinga na $2$-taśmowej maszynie off-line.

Podpowiedź

Użyj rezultatu z poprzedniego ćwiczenia.

Rozwiązanie

Używając konstrukcji pozwalającej zasymulować $k$-taśmową maszynę Turinga na jednotaśmowej można całe obliczenie przeprowadzić na drugiej taśmie maszyny off-line. Wystarczy skopiować słowo wejściowej z pierwszej taśmy do odpowiednio przygotowanych komórek drugiej taśmy.

Niedeterministyczna maszyna Turinga

Najciekawszym i bardzo istotnym dla dalszej części wykładu rozszerzeniem modelu maszyny Turinga jest wprowadzenie niedeterminizmu do funkcji przejścia. Niedeterministyczna maszyna Turinga to taka, dla której mechanizm sterujący może przy konkretnym stanie i odczycie z taśmy postąpić na kilka różnych sposobów.

Definicja 21

Niedeterministyczna maszyna Turinga, to maszyna Turinga, w której funkcja przejścia jest częściową funkcją wielowartościową:

$\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{\leftarrow ,\rightarrow \})$

Na niedeterministyczną maszynę Turinga można patrzeć jak na automat zachowujący się losowo - podając słowo na wejście maszyny nie wiemy jakich wyborów dokona mechanizm sterujący, jeżeli będzie miał możliwość wykonania różnych przejść. Nie jest to jednak podejście najlepsze. Żeby zrozumieć różnicę podamy teraz definicję akceptacji słowa przez niedeterministyczną maszynę Turinga.

Definicja 22

Mówimy, że niedeterministyczna maszyna $M$ akceptuje słowo $w$ jeżeli istnieje taki ciąg przejść, który kończy się stanem akceptującym.

Taka definicja akceptacji powoduje, że zamiast traktować niedeterministyczne maszyny jak maszyny zachowujące się losowo, lepiej patrzeć na nie jak na maszyny, które sprawdzają wszystkie możliwości postępowania. To podejście pozwala lepiej wyobrazić sobie potencjał obliczeniowy, jaki jest ukryty w niedeterminizmie.

Pytanie o to jak dużą moc obliczeniową zyskuje się wprowadzając niedeterminizm jest kluczowym dla teorii złożoności i jest istotą sławnego problemu $P{\text{ vs }}NP$, który omówimy dokładnie w dalszej części kursu.

Przykład 23 [Drzewo możliwych wykonań]

Drzewo możliwych wykonań z zaznaczonymi wykonaniami akceptującymi

Przyjrzyjmy się teraz diagramowi przykładowej niedeterministycznej maszyny Turinga. Można zauważyć, że niedeterminizm pojawia się w stanie $A$. Maszyna będąc w stanie $A$ i czytając z taśmy symbol $0$ może zarówno:

• pozostawić $0$ na taśmie i przesunąć głowicę w prawo nie zmieniając stanu.

• zamienić $0$ na $1$, przesunąć się w prawo i zmienić stan na $B$.

Podobnie reakcja maszyny na symbol $1$ może być dwojaka.

Żeby zobrazować działanie niedeterministycznej maszyny Turinga można narysować drzewo możliwych wykonań. W korzeniu drzewa zapisujemy stan początkowy maszyny, a od każdego wierzchołka reprezentującego stan obliczenia rysujemy strzałkę do kolejnych możliwych stanów.

Na drzewie zaznaczyliśmy ścieżkę, która prowadzi do akceptacji kolorem zielonym, a obliczenia, które prowadzą do odrzucenia słowa na czerwono. Zauważmy, że jest tylko jedna ścieżka akceptująca i każde odejście od niej prowadzi do odrzucenia słowa.

Złożoność

Wprowadzenie definicji złożoności czasowej i pamięciowej dla niedeterministycznej maszyny Turinga nastręcza pewnych trudności. Jest kilka podejść do tego zagadnienia, a subtelne różnice są zazwyczaj pomijane w literaturze. My zdecydowaliśmy się na najbardziej wymagającą definicję.

Przede wszystkim definiujemy, że niedeterministyczna maszyna $M$ zatrzymuje się na słowie $w$, kiedy żaden z możliwych scenariuszy obliczenia nie jest nieskończony.

Definicja 24

Czas i pamięć zużytą przez maszynę $M$, która zatrzymuje się na słowie $w$ definiujemy następująco:

• Czas wykonania $NT(M,w)$ jako liczbę kroków najdłuższego z możliwych obliczeń.

• Pamięć potrzebną do obliczenia $NS(M,w)$ jako maksimum z liczby komórek potrzebnych w każdym możliwym scenariuszu obliczenia.

Zauważmy, że czas wykonania odpowiada wysokości drzewa możliwych wykonań.

Definicje miary złożoności czasowej i pamięciowej maszyny niedeterministycznej są analogiczne do tych dla zwykłych maszyn. Są one określone dla maszyn z własnością stopu i dla długości $n$ są równe maksimum z czasu i pamięci potrzebnej do wykonania po wszystkich słowach wejściowych tej długości.

Ćwiczenia

Ćwiczenie 25 [Symulacja maszyny niedeterministycznej na maszynie deterministycznej]

Pokaż, że jeżeli język $L$ jest rozpoznawany przez niedeterministyczną maszynę Turinga w czasie ${\mathcal {O}}(f(n))$, to istnieje deterministyczna maszyna Turinga rozpoznająca ten sam język w czasie ${\mathcal {O}}(c^{f(n)})$ dla pewnej stałej $c$.

Podpowiedź

Skonstruuj wielotaśmową deterministyczną maszynę, która będzie przeglądać wszystkie ścieżki drzewa możliwych wykonań.

Rozwiązanie

Niech $d=max_{A\in Q,x\in \Gamma }{\vert \delta (A,x)\vert }$. Zauważmy, że $d$ jest maksymalnym stopniem rozgałęzienia, jaki może wystąpić w drzewie możliwych obliczeń maszyny.

Mając dany ciąg $x$ o długości $m$ liczb z przedziału $[1,d]$ możemy zdeterminować działanie maszyny w następujący sposób: W $i$-tym kroku wykonania wybieramy $x_{i}$-te z dostępnych przejść. Jeżeli obliczenie kończy się w mniej niż $m$ krokach to ciąg $x$ wyznacza działanie maszyny. Jeżeli obliczenie nie kończy się w pierwszych $m$ krokach, to będziemy musieli sprawdzić dłuższe ciągi $x$.

Nasza maszyna będzie $4$-taśmową maszyną deterministyczną. Pierwsza taśma będzie zawsze przechowywać słowo wejściowe. Druga taśma będzie zawierać ciąg determinujący obliczenie niedeterministyczne. Na trzeciej taśmie będzie się odbywać symulacja. Czwarta taśma z kolei będzie służyć do przechowywania specjalnego znacznika. Maszyna będzie działać w następujący sposób, że dla kolejnych liczb naturalnych $m$:

• usunie znaczniki z czwartej taśmy.

• przeglądnie wszystkie ciągi $x$ długości $m$ liczb z przedziału $[1,d]$ zapisując je na drugiej taśmie i dla każdego z nich:

• skopiuje zawartość pierwszej taśmy na trzecią taśmę i uruchomi tam zdeterminowany przy pomocy ciągu $x$ program niedeterministycznej maszyny.

• jeżeli obliczenie się nie zakończyło w ciągu pierwszych $m$ kroków, to zaznaczy ten fakt zapisując specjalny symbol na czwartej taśmie.

• wyczyści trzecią taśmę używając techniki „czystego” obliczenia.

Jeżeli którekolwiek ze zdeterminowanych obliczeń zakończy się akceptacją, to maszyna akceptuje słowo wejściowe. Jeżeli dla jakiejś liczby $m$ wszystkie obliczenia się zakończą (a więc nie będzie odpowiedniego znacznika na czwartej taśmie), to obliczenie powinno się zakończyć z błędem.

Tak skonstruowana maszyna rozpoznaje ten sam język co zadana maszyna niedeterministyczna. Jeżeli słowo $w$ należy do języka, to ciąg wyborów $x$, który o tym świadczy zostanie w końcu przeglądnięty i słowo zaakceptowane. Należy zwrócić uwagę, że obliczenie nie zostanie wcześniej przerwane z błędem, gdyż prefiksy $x$ zapewnią kontynuację obliczeń.

Jeżeli natomiast słowo $x$ nie należy do języka, to przy $m=f({\vert x\vert })$ wszystkie możliwe scenariusze wykonania muszą się zakończyć i w związku z tym obliczenie zostanie przerwane z błędem.

Czas działania tak powstałej maszyny dla słowa wejściowego długości $n$ możemy oszacować przez:

$\sum _{i=1}^{f(n)}{\mathcal {O}}(i)d^{i}\leq \sum _{i=1}^{f(n)}{\mathcal {O}}({(2d)}^{i})={\mathcal {O}}((2d)^{f(n)+1})={\mathcal {O}}(e^{f(n)})$

dla pewnej stałej $e$.

Możemy teraz użyć symulacji $4$-taśmowej maszyny Turinga działającej w czasie ${\mathcal {O}}(e^{f(n)})$ na jednotaśmowej maszynie w czasie ${\mathcal {O}}((e^{f(n)})^{2})$, czyli ${\mathcal {O}}(c^{f(n)})$ dla $c=e^{2}$.

Ćwiczenie 26 [Symulacja maszyny niedeterministycznej $k$-taśmowej na $2$-taśmowej]

Pokaż, że język rozpoznawany przez $k$-taśmową niedeterministyczną maszynę Turinga $M$ w czasie ${\mathcal {O}}(f(n))$ jest również rozpoznawany przez $2$-taśmową niedeterministyczną maszynę Turinga w czasie ${\mathcal {O}}(f(n))$.

Podpowiedź

Użyj niedeterminizmu do wylosowania obliczenia akceptującego na $k$-taśmowej maszynie, a następnie sprawdź, że wylosowałeś poprawną ścieżkę obliczeń.

Rozwiązanie

Niech $d$ oznacza tak jak poprzednio $max_{A\in Q,x\in \Gamma }{\vert \delta (A,x)\vert }$.

Maszyna $2$-taśmowa, którą skonstruujemy będzie działać w następujący sposób, że na drugiej taśmie zapisze ciąg grup : $k$ symboli z $\Gamma$ i jedna liczba z przedziału $[1,d]$. Znaczenie $i$-tej grupy postaci $(x_{1},x_{2},\ldots ,x_{k},w)$ jest takie, że w obliczeniu akceptującym maszyny $M$ w $i$-tym kroku z $k$ taśm są wczytane symbole $x_{1},x_{2},\ldots ,x_{k}$, a maszyna wybiera $w$-te z dostępnych przejść.

Zauważmy, że taki ciąg wyznacza jednoznacznie zachowanie maszyny - znamy stan początkowy, a każda grupa wyznacza następny stan maszyny.

Aby skonstruować naszą maszynę chcemy mieć możliwość sprawdzenia, czy taki arbitralny ciąg może rzeczywiście wystąpić. Możemy wykonać takie sprawdzenie symulując za każdym razem tylko jedną z $k$ taśm na pierwszej taśmie konstruowanej maszyny $2$-taśmowej. Taka symulacja musi sprawdzić, czy rzeczywiście odczyt z $i$-tej taśmy w kroku $j$ jest taki jak przewiduje to scenariusz zapisany na drugiej taśmie.

Widać już, że możemy skonstruować maszynę, która generuje przy pomocy przejść niedeterministycznych ciąg opisujący całe obliczenie, a następnie sprawdza, że jest to rzeczywiście możliwy ciąg odczytów z taśmy. Kiedy sprawdzone obliczenie prowadzi do stanu akceptującego, to maszyna akceptuje słowo wejściowe.

Jedyny problem jaki pozostał to metoda niedeterministycznego generowania ciągu grup. Ponieważ nie chcemy uzależniać metody od funkcji $f(n)$ zastosujemy następujące podejście, że będziemy generować po kolei ciągi o długości kolejnych potęg $2$. Zaczniemy od ciągu długości $1$. Potem za każdym razem jeżeli obliczenie kodowane przez poprzedni ciąg się nie zakończyło, ale ciąg był poprawny, to wydłużamy go dwukrotnie.

Takie podejście zapewnia, że o ile słowo $x$ należało do języka maszyny, to obliczenie o tym świadczące zostanie odkryte przez naszą nową maszynę.

Jeśli natomiast $x$ nie należy do języka, to żadne z obliczeń nie prowadzi do akceptacji, a kiedy długość testowanych ciągów przekroczy $f({\vert x\vert })$ to każde z obliczeń się kończy i dłuższe ciągi nie będą już testowane.

Czas działania nowej maszyny dla słowa długości $n$ jest proporcjonalny do

$\sum _{i=0}^{[\log f(n)]}k2^{i}\leq 4kf(n)={\mathcal {O}}(f(n))$