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 rzeczywiście ż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

Uwaga do zespołu redakcyjnego: To chyba niezłe miejsce na biografię Alana Turinga.

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 [Maszyna Turinga $M$]

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

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

$\mathrm{\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.

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

$\mathrm{\#}$ 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 \mathrm{\Gamma }$ w $Q\times Gamma\times \{\leftarrow ,\to \}$. 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=\to$).

$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 $\mathrm{\#}$ 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 nigdy 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 $\mathrm{\#}$. 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 podwójny prostokąt.

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

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

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 $m$ zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba $n+m$. W związku z tym, językiem wejściowym maszyny będzie $\mathrm{\Sigma }=\{0,1\}$. Maszyna będzie miała $4$ stany $Q=\{A,B,C,D\}$, stanem początkowym będzie $A$, a jedynym stanem akceptującym będzie $D$.

Rysunek: diagram maszyny dodającej dwie liczby - ZO-1.1

Animacja: działanie maszyny dodającej dwie liczby - ZO-1.2

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 [Język maszyny $M$]

Językiem maszyny $M$ nazwiemy $L(M)\subseteq {\mathrm{\Sigma }}^{\ast }$ zbiór tych słów wejściowych, dla których obliczenie maszyny $M$ kończy się w stanie akceptującym. Będziemy mówić, że $M$ rozpoznaje język $L(M)$.

Definicja

Język $L\subseteq {\mathrm{\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

Mówimy, że $M$ ma własność stopu, jeżeli dla dowolnego słowa $w\in {\mathrm{\Sigma }}^{\ast }$ obliczenie $M$ na $w$ się kończy. Język $L\subseteq {\mathrm{\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 [Maszyna rozpoznająca język $w{w}^{\leftarrow }$]

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

Parser nie mógł rozpoznać (nieznana funkcja „\kleene”): {\displaystyle {ww^\leftarrow : w \in \kleene{\{0,1\}}}

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

Specyfikacja problemu narzuca język wejściowy $\mathrm{\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$.

Rysunek: diagram maszyny rozpoznającej język $w{w}^{\leftarrow }$

Animacja: działanie maszyny rozpoznającej język $w{w}^{\leftarrow }$

Ćwiczenia

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

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 $\mathrm{\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,\dots ,n-1\}$.

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

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

4. $s\le 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,\to )$, 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

{{{3}}}

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 [Uzupelnij]

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)=\mathrm{\infty }$.

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

Definicja [Uzupelnij]

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

{n {N

: f(n) = max T(M,w) : w ^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 [Uzupelnij]

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 [Uzupelnij]

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

{n {N

: f(n) = max S(M,w) : w ^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

p{0.4}

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.

{ {}{{}{1pt}{}{0pt}{}{0.12}{}{0.12}}

Rysunek: wielotaśmowa maszyna 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

{{{3}}}

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

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 [Uzupelnij]

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

Q {P}(Q ,)

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 [Uzupelnij]

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 niedeterminiźmie.

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 [Uzupelnij]

Drzewo możliwych wykonań.

{ {}{{}{1pt}{}{0pt}{}{0.12}{}{0.12}}

Rysunek: 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 [Uzupelnij]

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

{{{3}}}

Ćwiczenie

{{{3}}}