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

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

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

Maszyna Turinga $M$, to siódemka:

M = (Q,,,,,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 [Uzupelnij]

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$.

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

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

}

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

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

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

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

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.

{{przyklad|[Uzupelnij]|| Maszyna rozpoznająca język $w{w}^{\leftarrow }$.

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

^ : w