Uniwersytet Zielonogórski
Instytut Sterowania i Systemów Informatycznych
Algorytmy i struktury danych
Maszyna Turinga
Złożoność algorytmów
Klasyfikacja złożoności
Twierdzenie Churcha-Turinga
Maszyna Turinga
Symulacje
Warianty maszyny Turinga
Zastosowanie maszyn Turinga
Ćwiczenia do wykonania
Literatura
1
1 Złożoność algorytmów
Wychodząc z rozumienia pojęcia algorytmu, wszystkie problemy, spotykane w matematyce, moż-
na podzielić na dwie klasy:
" problemy, dla rozwiązania których algorytm nie istnieje. Problemy te nazywane są nie-
rozstrzygalnymi; pewne przypadki szczególne mogą być co prawda rozwiązane np.przez
zgadnięcie, ale ogólna metoda rozwiązania nigdy nie może zostać znaleziona,
" problemy które można rozwiązać za pomocą algorytmów.
Czas potrzebny na wykonanie każdego algorytmu zależy od, czyli jest funkcją, rozmiaru pro-
blemu, i określa się go mianem złożoności czasowej. Jeśli funkcje f(n) i g(n) są funkcjami
okreÅ›lonymi w zbiorze liczb naturalnych oraz istniejÄ… stale k, m " N takie, że f(n) d" k · g(n) dla
wszystkich n e" m , to mówimy, że f(n) jest rzędu g(n) i oznaczamy ten fakt przez O(g(n)).
Notacja 0(") jest stosowana przy określaniu złożoności algorytmów. . Algorytm o złożoności
czasowej wielomianowej, lub w skrócie algorytm wielomianowy jest algorytmem, którego
złożoność czasowa jest rzędu O(p(n)), przy czym p(n) jest wielomianem, zaś n oznacza rozmiar
problemu. W pozostałych przypadkach mamy do czynienia z algorytmem wykładniczym
(eksponencjalnym), czyli algorytmem o złożoności czasowej wykładniczej. Natomiast rozmiar
pamięci urządzenia liczącego, potrzebny do wykonania algorytmu, wyrażony w funkcji rozmia-
ru problemu nazywa się złożonością pamięciową algorytmu. Definicje i zagadnienia dotyczące
złożoności pamięciowej są analogiczne do opisywanych w przypadku złożoności czasowej. W kla-
syfikacji problemów rozwiązywalnych stosuje się podział dychotomiczny (dwudzielny) na klasę
problemów łatwych oraz klasę problemów trudnych. Problemy łatwe to takie, dla których istnieją
algorytmy co najwyżej wielomianowe, natomiast tmdne charakteryzują się co najmniej wykład-
niczą złożonością rozwiązujących je algorytmów. Podział algorytmów na klasy łatwo i trudno
rozwiÄ…zywalne
üÅ‚
A1 O(log n)
ôÅ‚
ôÅ‚
żł
A2 O(n)
Å‚atwo rozwiÄ…zywalny
A3 O(n log n) ôÅ‚
ôÅ‚
þÅ‚
A4 O(n2)
üÅ‚
A5 O(log n)
żł
A6 O(n) trudno rozwiÄ…zywalny
þÅ‚
A7 O(n log n)
Należy tu zauważyć, że w niektórych szczególnych przypadkach pewne algorytmy wykładni-
cze są efektywniejsze od algorytmów wielomianowych. Jeżeli założymy, że rzeczywista złożoność
algorytmu A3 wynosi n1000 , to dla wartości n d" 1165 algorytm A5 okaże się dawać lepsze wyniki
czasowe. Jednakże w ogólności, dla problemów o dowolnie dużych rozmiarach efektywniejsze są
oczywiście algorytmy wielomianowe. Zauważmy również, że w przypadku określania złożoności
algorytmu A2 zaznaczanie podstawy logarytmu jest nieistotne, ponieważ loga x = loga b-logb x.
W tym miejscu warto byłoby wprowadzić pojęcie dolnego i górnego ograniczenia proble-
mów algorytmicznych. Otóż w momencie opracowania algorytmu o określonej złożoności, roz-
wiązującego dany problem, ustanawia się górne ograniczenie problemu, ponieważ algorytm ten
stanowi rzeczywisty dowód na to, że problem nie może być trudniejszy, czyli nie wymaga więcej
czasu na rozwiÄ…zanie. Ewentualne odkrycie sprawniejszego czasowo algorytmu ustanawia nowe
górne ograniczenie. Natomiast udowodnienie, że żaden algorytm rozwiązujący dany problem nie
może posiadać lepszej złożoności czasowej niż wykazana w dowodzie, ustanawia dolne ograni-
czenie problemu algorytmicznego. Wydawałoby się, iż aby uzyskać dolne ograniczenie problemu,
należałoby rozpatrzyć wszystkie możliwe algorytmy rozwiązujące ów problem, co brzmi dość
nieprawdopodobnie. Istnieje jednak wiele sposobów na dowodzenie dolnych ograniczeń. Do ich
przeprowadzania wykorzystuje się między innymi modele obliczeniowe omówione w następnym
rozdziale.
1.1 Klasyfikacja złożoności
Uzupełnijmy wprowadzoną powyżej wstępną klasyfikację problemów. Na rysunku 1. wyróżniono
niektóre klasy powstałe w wyniku wielu badań prowadzonych nad teorią złożoności algorytmów.
2
Rys.1. Klasyfikacja problemów przy założeniu, że NP jest różne od P
W górnej części zbioru znajdują się problemy nierozstrzygalne, czyli takie, dla których udo-
wodniono, że nie istnieje algorytm służący do ich rozwiązania. Nie oznacza to jednak, jak już
wspomniano, że pewne przypadki nie mogą być rozwiązane przez zgadnięcie.
Klasa problemów trudnych zawiera tylko algorytmy o złożoności wykładniczej. Natomiast
problemy Å‚atwe, czyli problemy wchodzÄ…ce do klasy P (oznaczenie pochodzÄ…ce od pierwszej litery
słowa polynomial), to problemy o złożoności wielomianowej. Rozbudujmy jeszcze tak wprowa-
dzonÄ… klasyfikacjÄ™. Klasa NP (z ang. nondetermimstic polynomial) zawiera wszystkie problemy
łatwe, a także problemy, których status jest mniej pewny - otóż jedyne znane algorytmy służą-
ce do ich rozwiązania mają złożoność eksponencjalną, lecz nie dowiedziono że nie istnieją dla
nich lepsze algorytmy wielomianowe. Klasę NP charakteryzuje również fakt, że należące do mej
problemy można rozwiązać za pomocą algorytmów niedetermmistycznych o złożoności wie-
lomianowej. Algorytm niedetenninistyczny jest rozumiany tutaj jako algorytm składający się z
dwóch etapów :
1. etapu zgadnięcia,
2. etapu weryfikacii.
W pierwszym etapie po prostu zgadujemy rozwiązanie, a weryfikacja polega na sprawdzeniu, już
w sposób deterministyczny z zastosowaniem algorytmu wielomianowego, poprawności rozwiąza-
nia.
Rozpatrując opisane wcześniej problemy decyzyjne, należy podkreślić pewnego rodzaju sy-
metrię ich rozwiązania za pomocą algorytmów deterministycznych. Otóż stosując algorytm tego
typu można rozwiązać zarówno problem  Czy X jest prawdziwe dla zadanego przypadku I ? 
jak i problem komplementarny  Czy X jest fałszywe dla zadanego przypadku I ? . W przypadku
wielomianowych algorytmów niedeterministycznych nie ma pewności czy symetria taka wystę-
puje, dlatego wyróżniono dodatkową klasę co - NP , czyli klasę problemów komplementarnych
(dopełnieniowych) do problemów NP . Definiuje się ją następująco
co - NP = { c = (D , D  - Y )|  = (D , D ) " NP }
Faktem jest, że przekrój klasy NP od co - NP jest niepusty. Przykładem problemu należącego
do obydwu klas jest problem liczb złożonych[2], w którym pytamy czy liczba naturalna jest
iloczynem dwóch liczb naturalnych od niej mniejszych.
Być może dla rozwiązania problemów typu NP istnieją algorytmy deterministyczne wielo-
mianowe, lecz jak dotąd problem  czy P = NP ? jest nierozwiązany, choć przypuszcza się, że
P = NP .

Twierdzenie 1 Jeśli  " NP , to wówczas istnieje wielomian p(n) taki, że  można rozwiązać
za pomocą algorytmu deterministycznego o złożoności O(cp(n)), przy czym c jest pewną stałą.
Zatrzymajmy się jeszcze przez moment przy klasie NP. Wyróżniono w niej podklasę proble-
mów NP-zupełnych odznaczających się ciekawą własnością - każdy problem klasy NP- zupełnej
może być zredukowany do innego problemu tej klasy za pomocą algorytmu wielomianowego. Za-
tem jeśli choć jeden z tych problemów można by rozwiązać za pomocą wielomianowego algorytmu
3
deterministycznego, to także wszystkie pozostałe można by rozwiązać przy pomocy takich algo-
rytmów. Innymi słowy udowodnienie łatwej rozwiązywalności jednego problemu NP -zupełnego
pociągałoby za sobą łatwą rozwiązywalność pozostałych. Na tym fakcie opiera się często dowody
na NP -zupełność danego problemu - wystarczy bowiem wykazać, że problem jest redukowalny
do innego znanego problemu NP -zupełnego, a także wykazać, że wybrany znany problem NP -
zupełny redukuje się do badanego problemu. Redukcja taka (zwana również przywiedlnością [2])
odbywa się w czasie wielomianowym, a jej mechanizm jest często wykorzystywany do określania
różnych cech problemów, m.in. przy dowodzeniu rozstrzygalności.
Istnieje ścisła zależność między problemami NP -zupełnymi i hipotezą, że NP = co - NP .

Otóż jeśliby istniał problem NP -zupełny taki, że jego wersja komplementarna byłaby typu NP ,
to wówczas klasa NP i klasa co - NP stanowiłyby tę samą klasę problemów.
1.2 Twierdzenie Churcha-Turinga.
Już od lat trzydziestych, jeszcze przed powstaniem pierwszych komputerów cyfrowych, poszuki-
wano modelu matematycznego uściślającego pojęcie algorytmu i tzw. efektywnej obliczalności.
Powstało wiele matematycznych określeń pojęcia algorytmu, wśród mch : fimkcje częściowo reku-
rencyjne [2], rachunek lambda [2], maszyna Turinga [1,2,3], maszyna Posta i algorytmy normalne
Markowa [2].
Mniej więcej w tym samym czasie, w roku 1936, A. Church i A.M. Turing wysunęli hipo-
tezę że wszystkie te uściślenia są równoważne w tym sensie, że definiują tę samą klasę funkcji
częściowych. Innymi słowy, takie klasy funkcji częściowych jak
" klasa funkcji częściowo rekurencyjnych,
" klasa funkcji lambda-określonych,
" klasa funkcji obliczalnych według Turinga,
" klasa funkcji obliczalnych według Markowa,
" klasa funkcji obliczalnych za pomocą maszyny o dostępie swobodnym
stanowiÄ… tÄ™ samÄ… klasÄ™ funkcji. HipotezÄ™ tÄ™ nazwano tezÄ… Churcha-Turinga Nie jest ona
twierdzeniem; w jej sformułowaniu posługujemy się intuicyjnym pojęciem algorytmu. Nie moż-
na jej udowodnić w ramach tradycyjnej praktyki matematycznej. Jest to raczej spostrzeżenie
bÄ…dz
prawo przyrody potwierdzające nagromadzone w ciągu wieków algorytmy, wśród których
me znaleziono takiego, który me byłby obliczalny za pomocą maszyny Turinga. Ten materiał
eksperymentalny potwierdza słuszność tezy Churcha-Turinga w takim samym stopniu, jak na
przykład odpowiednie eksperymenty potwierdzające prawo zachowania energii. Nie są znane wy-
jÄ…tki od zasady zachowania energii. Podobnie jak z tezÄ… Churcha-Turinga. Wszystko wskazuje
na to, że obie te zasady są bezwarunkowo obowiązujące.
1.3 Maszyna Turinga
Maszyna Turinga jest abstrakcyjnym automatem wyposażonym w jednostronnie nieskończona
taśmę, na której za pomocą głowicy może odczytywać i zapisywać symbole z pewnego alfabetu
(rys. 2.). W stanie początkowym w n najbardziej na lewo znajdującym się komórkach taśmy jest
umieszczone słowo wejściowe. Pozostałe komórki zawierają symbole  puste oznaczane najczę-
ściej znakiem #.
Rys.2. Maszyna Turinga
4
Mając taką formalną definicję, można wyrazić udoskonaloną wersję Churcha-Turinga w po-
staci stwierdzenia, że wszystkie rozsądne modele obliczeń sekwencyjnych są wielomianowe rów-
noważne zwykłym maszynom Turinga, ponieważ jak wiadomo, każdą maszynę można zasymu-
lować za pomocą innej maszyny w czasie O(p(n)), przy czym p(n) jest wielomianem. Należy tu
jednak podkreślić, że teza ta dotyczy wyłącznie modeli sekwencyjnych, czyli przetwarzających
określone instrukcje krok po kroku, nie po kilka równocześnie (jak to ma miejsce w modelach
niedeterministycznych lub systemach współbieżnych), z tego względu nazywa się ją czasem tezą
obliczenia sekwencyjnego. Gdyby bowiem niedeterministyczne maszyny Turinga spełniały kryte-
rium sekwencyjności, z udoskonalonej tezy Churcha-Turinga wynikałoby pozytywne rozwiązanie
problemu, czy P = NP , ponieważ zrównałaby ona klasy problemów rozwiązywalnych w czasie
wielomianowym na obu wersjach maszyny. Jak siÄ™ jednak okazuje, niedeterministycznych ma-
szyn Turinga nie uważa się za sekwencyjne. Teza ta jest więc nieprawdziwa dla takich maszyn i
nie pozwala na stwierdzenie porównywalności klas P i NP .
Sformułowanie problemu, czy P = NP , w jego formalnej postaci jest interesujące, ponie-
waż wynika z niego, że aby rozwiązać problem negatywnie musimy jedynie pokazać, że maszyny
Turinga nie mogą rozwiązać pewnego problemu NP -zupełnego w czasie krótszym niż wykład-
niczy. Oznaczałoby to, że wszystkie pozostałe problemy również są trudno rozwiązywalne, a to
oznaczałoby, że P = NP .

Powróćmy do opisanych w poprzednim rozdziale górnych i dolnych ograniczeń problemów
algorytmicznych. Otóż aby udowodnić górne ograniczenie danego problemu, czyli znalez
ć dobry
algorytm, powinno się użyć najbogatszego i najsilniejszego dostępnego formalizmu. W prakty-
ce badacze, aby wymyśleć niebanalne algorytmy, stosują zwykle konstrukcje programowe bar-
dzo wysokiego poziomu i zawiłe struktury danych. Następnie bazują na mocy wariantów tezy
Churcha-Turinga wyciągając wnioski z powstałego algorytmu we wszystkich modelach. Zatem
jeśli komuś nawet uda się udowodnić, że P = NP , będzie to prawdopodobnie zrobione z użyciem
modeli bardzo wysokiego poziomu służących do opisania złożonego algorytmu o czasie wielomia-
nowym dla pewnego problemu NP -zupełnego. Natomiast do udowodnienia dolnych ograniczeń
znacznie odpowiedniejsze są prymitywne modele, ponieważ stosuje się w nich tylko kilka nad-
zwyczaj prostych konstrukcji. I znowu jeżeli ktoś udowodni, że P = NP , to prawdopodobnie

dokona tego posługując się bardzo prymitywnym modelem, takim jak maszyny Turinga.
Maszyny Turinga stosuje się powszechnie do dowodzenia dolnych ograniczeń wszystkich ty-
pów. Przykładem może być użycie maszyny Turinga do pokazania nierozstrzygalności pewnych
problemów domina [1] (nierozstrzygalność jest oczywiście rodzajem dolnego ograniczenia - przy-
nosi złą informację o statusie problemu).
Jedną z najważniejszych metod ustalania dolnych ograniczeń za pomocą prymitywnych mo-
deli, takich jak maszyna Turinga, jest metoda diagonalizacji [1,2]. Pomysł pochodzi od Georga
Cantora, wybitnego matematyka XIX-wiecznego, który użył go w kontekście niealgorytmicznym.
Formalnie maszynę Turinga opisuje się jako uporządkowaną szóstkę [3]
M = (S, T, P, s0, F, #)
taką, że
" S jest skończonym niepustym zbiorem stanów,
" T jest skończonym alfabetem symboli taśmowych,
" P jest programem złożonym ze skończonej liczby instrukcji,
" s0 " S jest stanem poczÄ…tkowym,
" F ą" S jest zbiorem stanów końcowych,
" # " T jest pustym symbolem taśmowym.
Każda instrukcja programu P może mieć jedną z dwóch postaci
s(t/t , right)s
s(t/t , left)s
5
przy czym s, s " S, t, t " T . Instrukcja taka określa sposób przechodzenia maszyny ze stanu
s do stanu s . Symbol t nazywany jest wyzwalaczem przejścia, natomiast symbol t wraz z
oznaczeniem kierunku left lub right stanowi akcjÄ™. Instrukcje maszyny Turinga przedstawia siÄ™
również za pomocą graficznych oznaczeń pokazanych na rysunku 3 Stan początkowy maszyny
jest wskazywany strzałką.
Rys.3. Graficzne symbole instrukcji maszyny Turinga: a)s(t/t , right)s , b) s(t/t , left)s
W wyniku wykonania instrukcji s(t/t , right)s maszyna wykonuje następujące czynności
" w komórce wskazywanej przez głowicę wymienia symbol t na t
" przesuwa głowicę o jedną komórkę w prawo,
" przechodzi ze stanu s do stanu s
W przypadku instrukcji s(t/t , left)s mozliwe są dwa jakościowo różne przypadki
1. głowica znajduje się przy najbardziej w lewo lezącej komórce, wówczas ruch nie może być
wykonany i maszyna zatrzyma siÄ™;
2. głowica znajduje się przy dowolnej z pozostałych komórek taśmy, wówczas kolejno
" we wskazanej komórce wymienia symbol t na t
" przesuwa się o jedną komórkę w lewo,
" maszyna przechodzi ze stanu s do stanu s
Konfiguracją maszyny Turinga [2,3] nazywamy czwórkę a = (s, x, t, y) taką, że s " S, t " T ;
"
x, y " T , przy czym najbardziej na lewo leżąca litera słowa y jest różna od #. Maszyna na
rysunku 2 jest w konfiguracji ( s, t1, t2,. . . ,tk-1,tk,tk+1,tk+1,. . .,tn). KonfiguracjÄ™ (sO, e, t, y)
nazywamy konfiguracjÄ… poczÄ…tkowÄ…, a konfiguracjÄ™ (sF , x, t, y), przy czym sF " F , konfiguracjÄ…
końcową. Jeśli będąc w danej konfiguracji maszyna nie może wykonać żadnego ruchu, to taką
konfiguracjÄ™ nazywamy martwÄ….
Wykonując instrukcja ruch głowicy powoduje przejście maszyny Turinga z jednej konfiguracji
do innej, co zapisujemy symbolicznie
(s, x, t, y) Ò! (s , x , t , y ).
1.4 Symulacje
Niech M będzie maszyną, która dla słowa wejściowego x osiąga konfiguracje ą1, ą2, . . . , ąm. Bę-
dziemy mówić, że maszyna M symuluje maszynę M, jeśli M po podaniu na jej wejście słowa x,
osiÄ…ga kolejne konfiguracje reprezentujÄ…ce konfiguracje Ä…1, Ä…2, . . . , Ä…m maszyny M. Nie wyklu-
cza się przy tym, że pomiędzy odcinkami czasu odpowiadającymi konfiguracjom ą1, ą2, . . . , ąm
maszyna M znajduje siÄ™ w konfiguracjach innych.
Maszyny Turinga stanowią klasę maszyn o pewnych możliwościach obliczeniowych. Jest to
jedna z wielu abstrakcyjnych klas maszyn. Nasuwa siÄ™ naturalne pytanie o moc obliczeniowÄ…
(możliwości obliczeniowe) tych klas. Istnieją dwie metody dowodzenia, że pewna klasa M maszyn
ma takÄ… samÄ… moc obliczeniowÄ… jak inna klasa M.
1. należy pokazać, że dla dowolnej maszyny M " M można skonstruować maszynę M " M,
która wykonuje te same obliczenia;
2. jeśli istnieje maszyna M " M, mogąca wykonywać obliczenia każdej maszyny z klasy M,
to klasa M ma co najmniej takÄ… samÄ… moc obliczeniowÄ… jak klasa M.
Maszyna M wykonuje postawione zadanie, korzystając z danych parametrycznych, uwzględ-
niających specyfikę przypadku. Taka metoda symulacji nazywa się interpretacją. Co ważne,
istnienie interpretera uniwersalnego stanowi podstawę teorii obliczalności.
6
1.5 Warianty maszyny Turinga
Istnieje kilka wariantów maszyny Turinga. Otrzymuje się je wprowadzając modyfikacje dotyczą-
ce kształtu oraz liczby taśm a także liczby głowic. Przyjęty powyżej model w postaci automatu
z taśmą jednostronnie nieskończoną (rys. 2) jest modelem ogólnym w tym sensie, że każdy inny
zmodyfikowany model można do niego sprowadzić. Jedną z odmian maszyny jest przedstawiona
na rys. 4 maszyna M z taśmą obustronnie nieskończoną taką, że każdej jej komórce odpowiada
jednoznacznie komórka taśmy nieskończonej jednostronnie. Odwzorowania takiego można do-
konać, gdy wyznaczymy w sposób dowolny  środek taśmy i ponumerujemy komórki leżące na
prawo liczbami całkowitymi nieujemnymi, a leżące na lewo - liczbami całkowitymi ujemnymi.
Wówczas funkcja f : Z N działająca ze zbioru liczb całkowitych Z w zbiór liczb naturalnych
N określona w taki sposób, że
2x, jeśli x > 0
f(x) =
-2x - 1, jeśli x < 0
wyznacza jednoznacznie odwzorowanie taśmy dwustronnie nieskończonej na taśmę nieskończoną
jednostronnie.
Rys.4. Maszyna symulowana M i maszyna symulujÄ…ca M
Odwzorowanie takie może służyć do skonstruowania (napisania programu) maszyny Turinga
z automatem skończonym AS, przeznaczonego do symulacji maszyny M za pomocą maszyny
M. W tym celu automat AS powinien składać się z dwóch automatów skończonych, jednego
(ASP) używanego wówczas, gdy maszyna symulowana działa w prawej części, i drugiego (ASL)
używanego, gdy maszyna działa w lewej części taśmy.
W sytuacji, gdy symulujemy działanie maszyny M pracującej w prawej części taśmy, każdy
ruch maszyny oryginalnej zastępujemy dwoma ruchami maszyny symulującej. W tym przypadku
maszyna działa zgodnie z programem zawartym w automacie ASP.
Jeśli głowica maszyny M znajduje się nad komórką o numerze 0 i według programu ma wyko-
nać ruch w lewo, to w maszynie symulującej M sytuacja taka jest reprezentowana przekazaniem
sterowania automatowi ASL, przy czym pierwszy symulowany ruch w lewo jest wykonywany w
maszynie M w taki sposób, że jej głowica zostaje przesunięta o jedną komórkę w prawo, a w
każdym następnym ruchu w prawo głowica jest przesuwana o dwie komórki.
W przypadku, gdy pracuje automat ASL i głowica po dojściu do lewego końca taśmy miałaby
się przesuwać zgodnie z programem zawartym a ASP, to sytuacja jest odwrotna do przedstawio-
nej powyżej.
Inną modyfikacją maszyny Turinga jest wprowadzenie kilku taśm wraz z kilkoma głowicami
[5]. Stosuje się również ograniczenia działania głowicy, zezwalając jedynie na odczyt symbolu z
taśmy, bez możliwości zmiany jej zawartości, czy też zakładając, że głowica może poruszać się
tylko w jednym wybranym kierunku. Możemy również zdefiniować maszyny z taśmami dwuwy-
miarowymi, zwiększając liczbę możliwych kierunków do czterech.
Poza podziałem maszyn w zależności od wprowadzonych modyfikacji, istnieje również po-
dział na maszyny deterministyczne i niedeterministyczne. Otóż jeśli dla każdej konfiguracji
maszyny Turinga dopuszczalne jest wykonanie co najwyżej jednej instrukcji, to taką maszynę
7
nazywamy deterministycznÄ…. W przeciwnym wypadku mamy do czynienia z maszynÄ… niedeter-
ministyczną. Konsekwencją tej definicji jest, iż klasa deterministycznych maszyn Turinga jest
podklasÄ… maszyn niedeterministycznych.
1.6 Zastosowanie maszyn Turinga
Istotne z punktu widzenia teorii złożoności jest omówienie zasad określania złożoności czaso-
wej i pamięciowej procesów obliczeniowych (algorytmów) realizowanych przy pomocy maszyny
Turinga. Otóż złożoność czasową określa się liczbą wszystkich ruchów głowicy wykonanych w
trakcie realizacji danego algorytmu, natomiast złożoność pamięciową wyznacza maksymalna
liczba komórek taśmy wykorzystanych w trakcie procesu. Omawiając klasy złożoności, wymie-
nione w poprzednim rozdziale, warto byłoby spojrzeć a ich definicje korzystając z mechanizmu
uniwersalnego modelu obliczeń, jakim jest maszyna Turinga. Otóż klasę NP definiuje się jako
zawierającą dokładnie te problemy, które są rozwiązywalne przez modele niedeterministyczne
maszyny Turinga w czasie wielomianowym, podczas gdy klasÄ™ P definiuje siÄ™ jako zawierajÄ…cÄ…
problemy rozwiązywalne przez zwykłe maszyny Turinga w czasie wielomianowym.
2 Ćwiczenia do wykonania
1. Zapoznać się z programami Edytor i Maszyna.
2. Wykonać w programie Edytor model maszyny Turinga rozpoznającej palindromy
3. Uruchomić utworzony model w programie Maszyna.
4. Wyznaczyć złożoność pamięciową oraz czasową algorytmu.
Aby zademonstrować sposób korzystania z programu w celu stworzenia modelu obliczeniowego
posłużymy się przykładem modelu maszyny Turinga rozpoznającej palindromy. Problem jest
typowo decyzyjny - maszyna powinna rozpoznać, czy słowo zapisane na taśmie jest palindromem,
tzn. czy wygląda tak samo czytane w obie strony. Dla uproszczenia przyjmiemy, że nasze słowa
mogą się składać wyłącznie z dwóch rodzajów liter - a i b. W takim razie przykładowe słowo
aababaa będzie palindromem, podczas gdy np. aab - nie. Takie słowo umieszczone na taśmie
przed uruchomieniem stanowić będzie zbiór danych wejściowych dla naszego modelu.
Jakiej odpowiedzi oczekiwać od maszyny ? Otóż wystarczy zaprojektować dwa stany - tak
oraz nie, w których maszyna powinna się zatrzymać po zakończeniu procesu. Możemy więc
zacząć.
KorzystajÄ…c z funkcji programu tworzymy nowy projekt. W projekcie automatycznie poja-
wia siÄ™ diagram o nazwie Diagram1. Teraz utworzymy stan, wybierajÄ…c odpowiednie polecenie
z menu, a następnie klikając myszką w wybranym miejscu ekranu uruchamiamy okno dialogo-
we Stan. W oknie dialogowym wpisujemy nazwÄ™ stanu - w naszym przypadku  tak - oraz
określamy typ jako zwykły. Podobnie postępujemy ze stanem  nie .
Teraz określimy mechanizm działania maszyny. Najprostszym sposobem jest porównywanie
pierwszej litery słowa z ostatnią i jeżeli są takie same, usunąć je, skracając w ten sposób słowo.
Czynność tę należy powtarzać do momentu wymazania całego słowa (wówczas przejść do stanu
tak) lub znalezienia na jego końcach różnych liter (i zakończenia działania w stanie nie).
W stanie początkowym powinniśmy odczytać pierwszą literę słowa i w zależności od tego,
czy literą tą jest a czy b, przejść do odpowiedniego stanu następnego. Utwórzmy więc stan
poczÄ…tkowy o nazwie zaznacz.
8
W tym stanie odczytujemy literę. Załóżmy, że literą tą jest a. W takim razie maszyna powinna
wymazać tę literę i przejść do stanu, w którym po dotarciu do ostatniej litery sprawdzi, czy jest
nią również a. Utwórzmy więc najpierw stan o nazwie ruch a, który posłuży nam do przesunęcia
głowicy na koniec słowa.
Jak określić, że maszyna po odczytaniu litery a powinna ją wymazać (czyli wpisać na jej miejsce
znak pusty) i przejść do stanu ruch a (przesuwając od razu głowicę w prawo na następną literę
?). Otóż tym pytaniem zdefiniowaliśmy właśnie przejście. Wybieramy więc narzędzie tworzenia
nowego przejścia i ustawiamy kursor myszy jak najbliżej górnej krawędzi stanu zaznacz. W tym
momencie kursor myszy powinien zmienić swój wygląd. Klikamy lewym przyciskiem myszy i
zauważamy, że między wierzchołkiem kursora a krawędzią stanu pojawiła się linia przerywana.
Ustawiamy więc kursor myszy w pobliżu stanu ruch a i ponownie klikamy myszą - stany zostały
połączone. Pojawiło się okno, w którym należy wpisać wyzwalacze. zamienniki oraz określić
kierunek przesunięcia głowicy. Wyzwalaczem naszego przejścia jest litera a - wpisujemy więc
 a . Zamiennikiem naszej litery jest znak pusty - wpisujemy więc  # . I wreszcie wybieramy
kierunek przesunięcia głowicy - w prawo. Wciskamy przyciskOK i na ekranie pojawia się gotowe
przejście opatrzone etykietą zawierającą podane przez nas informacje.
Teraz rozkażemy maszynie, żeby przesunęła się na koniec słowa. Aby to zrobić powinna kolejno
odczytywać litery słowa, nie zastępując ich innymi znakami (a w praktyce - zastępować takimi
samymi literami) i przesuwać głowicę w prawo - aż do napotkania końca słowa - czyli znaku
pustego. Realizacja tak poczynionych zamiarów polegać będzie na utworzeniu dwóch przejść.
Pierwsze przejście będzie wyzwalane literami a oraz b i spowoduje przesuwanie głowicy w prawo,
i najważniejsze - prowadzić będzie ze stanu ruch a do tego samego stanu. Powstanie w ten sposób
swojego rodzaju pętla, kończąca się w momencie, gdy maszyna trafi na taśmie (odczyta) znak
pusty - do tego celu posłuży nam drugie przejście. Ale po kolei.
Wybierzmy ponownie narzędzie tworzenia przejścia. Ustawmy kursor w pobliżu stanu ruch
a (najlepiej przy lewym górnym rogu), upewnijmy się, że kursor zmienił swój wygląd, a następnie
kliknijmy lewym przyciskiem myszy. Teraz powinniśmy zakończyć przejście w pobliżu naszego
stanu, ale nim to się stanie, spróbujemy wykorzystać możliwość kształtowania linii przejścia.
Przesuńmy więc kursor pionowo w górę na odległość mniej więcej równą wysokości prosto-
kąta stanu. Klikając w tym miejscu lewym przyciskiem myszy spowodujemy powstanie węzła
przejścia. Teraz przesuńmy kursor poziomo w prawo, aż do granicy stanu. Ponownie kliknijmy
myszką. Na koniec ustawmy kursor na prawym górnym rogu stanu ruch a. l ostatni klik. Pora
na wprowadzenie danych powstałego przejścia. W polu wyzwalacze wpiszemy litery a i b. Pole
zamienniki możemy pozostawić puste - oznacza to, że nie będziemy zastępować odczytanych
liter innymi literami, pozostawimy je tam gdzie sÄ…. Wprowadzenie do pola zamienniki liter a i
b (w tej samej kolejności) będzie miało ten sam efekt. Rozkażemy jeszcze przesunąć głowicę w
prawo i po wciśnięciu OK otrzymamy nowe przejście.
9
Jak zakończyć tę (wydawałoby się nieskończoną) pętlę ? Otóż musimy utworzyć jeszcze jedno
przejście wychodzące ze stanu ruch a w momencie, gdy odczytaną literą będzie znak pusty.
Przejście poprowadzi do nowego stanu. Jeżeli dodatkowo w trakcie przejścia przesuniemy głowi-
cę w lewo, okaże się, że znajdujemy się bezpośrednio nad ostatnią literą słowa. W tym momencie
możemy łatwo sprawdzić, czy tą literą jest również a (pamiętajmy, że dotarliśmy tu po początko-
wym odczytaniu litery a). Nazwijmy więc nowy stan test a i poprowadz
my do niego przejście,
którego wolna interpretacja może mieć postać  maszyna będąc w stanie ruch a, po odczytaniu
z bieżącej klatki taśmy symbolu pustego #, powinna pozostawić go na taśmie, przesunąć głowicę
w lewo i przejść do stanu test a . W rezultacie nasz diagram będzie wyglądał mniej więcej tak
Jak już wspomnieliśmy, w stanie test a już można spróbować stwierdzić, czy słowo jest palin-
dromem. Znajdujemy się przecież nad ostatnią literą słowa. Jeżeli więc odczytana litera będzie
inna, niż ta na początku, możemy ze spokojnym sumieniem zakończyć diałanie maszyny i przejść
do  stanu spoczynku - czyli stanu końcowego. Oznaczałoby to bowiem niezbicie, że słowo nie
jest palindromem. W naszym przypadku stałoby się tak, gdybyśmy w stanie test a odczytali z
taśmy literę b. Wówczas maszyna powinna przejść do stanu nie, co spowodowałoby zakończenie
procesu (ponieważ z tego stanu nie będą już wychodziły żadne przejścia) i jednoczesne udzie-
lenie odpowiedzi na zadane pytanie. W trakcie przejścia przesuniemy głowicę już w dowolnym
kierunku - powiedzmy w lewo - i pozostawimy na taśmie literę b jako dowód rzeczowy.
Może się również zdarzyć, że w stanie test a trafiliśmy na znak pusty - co by oznaczało,
że całe słowo zostało już wymazane z taśmy. Stanowiłoby to niezbity dowód na to, że słowo
było palindromem, ponieważ proces dotarł do tego miejsca bez problemów. Należałoby go więc
zakończyć w stanie tak.
10
A co w przypadku, gdy ostatnia litera będzie taką samą jak pierwsza ? Wówczas, z optymistycz-
nym przypuszczeniem, że słowo może być palindromem musimy powtórzyć test od początku -
czyli od pierwszej litery. W tym celu utworzymy stan o nazwie powrót do którego poprowa-
dzi nas z naszego stanu test a przejście o wyzwalaczu a. Musimy pamiętać o wymazaniu już
sprawdzonej ostatniej litery i przy okazji przesunąć już głowicę w kierunku pierwszej - czyli w
lewo. Z kolei stan powrót powinien posiadać przejście podobne do pętli w stanie ruch a, tym
razem przesuwając głowicę w lewo aż do napotkania znaku pustego.
Przesuwając głowicę w lewo napotkamy w końcu znak pusty. W tym momencie, po zostawieniu
znaku tak jak jest i przesunięciu głowicy w prawo znajdziemy się nad pierwszą literą słowa.
Możemy więc stworzyć przejście do stanu zaznacz, od którego rozpoczniemy ponowny proces
testowania.
I uwaga. Jeżeli będąc w stanie zaznacz stwierdzimy, że nie ma już żadnej pierwszej litery - to
podobnie jak w stanie test a możemy spokojnie zakończyć proces przechodząc do stanu tak,
ponieważ oznacza to, że albo słowa na taśmie nigdy było, albo było palindromem.
Podobnie rzecz się będzie miała w przypadku, gdy odczytaną pierwszą literą będzie b. Mu-
simy utworzyć stan ruch b, który przesunie nam głowicę maszyny na koniec słowa i stan test
b, w którym sprawdzimy, czy ostatnią literą jest również b, postępując dalej analogicznie do
procesu opisanego powyżej dla litery a. W rezultacie nasz diagram osiągnie końcową postać
11
W tym momencie powinniśmy zachować nasz projekt na dysku w celu przeprowadzenia symu-
lacji w programie Maszyna.
Literatura
1. P. A
apko, Modelowanie procesów obliczeniowych za pomocą maszyny Turinga - praca dy-
plomowa, PZ, 1997.
2. D. Harel, Rzecz o istocie informatyki - WNT, Warszawa 1992.
3. L. Banachowski, K. Diks, W. Rytter, Algorytmy i struktury danych - WNT, Warszawa
1996.
4. N. Wirtch, Algorytmy + struktury danych = programy- WNT, Warszawa 1989.
5. T. Bilski, K. Chmiel, J Stokłosa, Zbiór zadań ze złożoności obliczeniowej algorytmów-
Wydawnictwo Politechniki Poznańskiej, Poznań, 1992
12