|
|
| Linia 1: |
Linia 1: |
| ==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 <math>M</math>, to siódemka:
| |
|
| |
| M <nowiki>=</nowiki> (Q,,,,,q_0,F)
| |
|
| |
| , gdzie:
| |
| [*]
| |
| ; <math>Q</math>
| |
| :[:]to skończony zbiór ''stanów'' maszyny.
| |
|
| |
| ; <math>\Sigma</math>
| |
| :[:]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.
| |
|
| |
| ; <math>\Gamma</math>
| |
| :[:]to skończony zbiór ''symboli taśmowych'' - są to wszystkie symbole jakie mogą się znajdować na taśmie. Oczywiście <math>\Sigma \subseteq \Gamma</math>.
| |
|
| |
| ; <math>\#</math>
| |
| :[:]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ę.
| |
|
| |
| ; <math>\delta</math>
| |
| :[:]to ''funkcja przejścia''. Jest to funkcja częściowa prowadząca z <math>Q \times \Gamma</math> w <math>Q \times Gamma \times \{\leftarrow,\rightarrow\}</math>. Wartość <math>\delta(A,x) = (B,y,K)</math> oznacza, że maszyna będąca w stanie <math>A</math> i czytając symbol <math>x</math> z taśmy przejdzie do stanu <math>B</math>, zapisze symbol <math>y</math> na taśmie i przesunie głowicę o jedną komórkę w lewo (<math>K = \leftarrow</math>) lub w prawo (<math>K = \rightarrow</math>).
| |
|
| |
| ; <math>q_0</math>
| |
| :[:]to ''stan początkowy'' w jakim znajduje się maszyna przed rozpoczęciem obliczenia.
| |
|
| |
| ; <math>F</math>
| |
| :[:]to zbiór ''stanów akceptujących'' będący podzbiorem <math>Q</math>. Obliczenie maszyny kończy się kiedy osiągnięty zostanie któryś ze stanów <math>F</math>.
| |
| }}
| |
|
| |
| ===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 <math>\#</math> 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 <math>q_0</math> i uruchomić maszynę.
| |
|
| |
| Maszyna będzie działać zgodnie z algorytmem zapisanym w funkcji <math>\delta</math> - 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 <math>A</math> przeczyta z taśmy symbol <math>x</math>, a wartość funkcji częściowej <math>\delta(A,x)</math> 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 <math>\delta</math>. Możemy po prostu zapisywać w kolejnych wierszach ciągi <math>A,x: B,y,K</math> oznaczające <math>\delta(A,x) = (B,y,K)</math>. 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 <math>\#</math>. 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 <math>\leftarrow</math> lub <math>\rightarrow</math>. Strzałka etykietowana <math>x,y,K</math> prowadząca od stanu <math>A</math> do stanu <math>B</math> oznacza <math>\delta(A,x) = (B,y,K)</math>.
| |
|
| |
| {{przyklad|[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 <math>n</math> jest reprezentowana w systemie unarnym przez <math>n+1</math> jedynek zapisanych na taśmie obok siebie.
| |
|
| |
| Zakładamy, że na wejściu maszyny znajdą się dwie liczby naturalne <math>n</math> i <math>m</math> zapisane unarnie oddzielone pojedynczym zerem. Po zakończeniu działania maszyny na taśmie powinna być zapisana liczba <math>n+m</math>. W związku z tym, językiem wejściowym maszyny będzie <math>\Sigma = \{0,1\}</math>. Maszyna będzie miała <math>4</math> stany <math>Q = \{A,B,C,D\}</math>, stanem początkowym będzie <math>A</math>, a jedynym stanem akceptującym będzie <math>D</math>.
| |
|
| |
| {
| |
| {}{{}{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 <math>M</math> nazwiemy <math>L(M) \subseteq {\Sigma^\ast}</math> zbiór tych słów wejściowych, dla których obliczenie maszyny <math>M</math> kończy się w stanie akceptującym. Będziemy mówić, że <math>M</math> rozpoznaje język <math>L(M)</math>.
| |
| }}
| |
|
| |
| {{definicja|[Uzupelnij]||
| |
| Język <math>L \subseteq {\Sigma^\ast}</math> nazywamy ''rekurencyjnie przeliczalnym'', albo ''częściowo rozstrzygalnym'', jeżeli istnieje taka maszyna <math>M</math>, że <math>L = L(M)</math>.
| |
| }}
| |
|
| |
| Dlaczego język <math>L</math> jest tylko ''częściowo'' rozstrzygalny? Ponieważ jeżeli słowo <math>w \in L</math>, to da się to sprawdzić - należy uruchomić maszynę <math>M</math> na słowie <math>w</math> i zostanie ono zaakceptowane. Natomiast jeżeli <math>w \notin L</math>, to niekoniecznie da się to sprawdzić. Możemy oczywiście uruchomić <math>M</math> na <math>w</math>, ale jeżeli to obliczenie nigdy się nie kończy, to nigdy nie dowiemy się czy <math>M</math> akceptuje <math>w</math>.
| |
|
| |
| Żeby uchwycić własność pełnej rozstrzygalności definiujemy własność stopu dla maszyny Turinga.
| |
|
| |
| {{definicja|[Uzupelnij]||
| |
| Mówimy, że <math>M</math> ma ''własność stopu'', jeżeli dla dowolnego słowa <math>w \in {\Sigma^\ast}</math> obliczenie <math>M</math> na <math>w</math> się kończy. Język <math>L \subseteq {\Sigma^\ast}</math> nazywamy ''rekurencyjnym'', lub ''rozstrzygalnym'', jeżeli istnieje maszyna Turinga <math>M</math> z własnością stopu taka, że <math>L = L(M)</math>.
| |
| }}
| |
|
| |
| 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 <math>ww^\leftarrow</math>.
| |
|
| |
| Przedstawimy teraz drugą maszynę Turinga, której zadaniem jest rozpoznanie konkretnego języka:
| |
|
| |
| ^ : w
| |
