Złożoność obliczeniowa algorytmów

Maszyny Turinga

Kordian A. Smoliński

Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej

2007/2008

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

1 / 50

Maszyny Turinga (wykład 1)

1

Podstawy maszyn Turinga

2

Maszyny Turinga jako algorytmy

3

Maszyny Turinga z wieloma taśmami

4

Liniowe przyśpieszanie

5

Ograniczenia pamięciowe

6

Maszyny o dostępie swobodnym (RAM)

7

Maszyny niedeterministyczne

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

2 / 50

Podstawy maszyn Turinga

Podstawy maszyn Turinga

Definicja

Maszyna Turinga

jest uporządkowaną czwórką

M = (K , Σ, δ, s)

, gdzie

K

— skończony zbiór

stanów

,

s ∈ K

—

stan początkowy

,

Σ

— skończony

zbiór

symboli

(Σ jest

alfabetem

M ), K ∩ Σ = ∅. Σ zawsze zawiera

symbol

pusty t

i

symbol końcowy .

.

δ

—

funkcja przejścia

odwzorowująca

K × Σ

w

(K ∪ {h, „tak”, „nie”}) × Σ × {←, →, −}

. Stany:

h

(

stan końcowy

),

„tak”

(

stan akceptujący

),

„nie”

(

stan odrzucający

) i

kierunki ruchu

kursora

:

←

(w lewo)

→

(w prawo) i

−

(pozostanie w miejscu) nie należą

do

K ∪ Σ

.

Σ

∗

oznacza zbiór

skończonych ciągów

nad alfabetem Σ.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

3 / 50

Podstawy maszyn Turinga

Funkcja δ jest

programem

maszyny. Dla każdej kombinacji stanu

i symbolu określa kolejny stan, symbol zastępujący symbol na taśmie
i kierunek przesunięcia kursora:

K × Σ 3 (q, σ)

δ

7→ (p, ρ, D) ∈ K × Σ × {←, →, −} .

Jeżeli dla q i p δ(q, .) = (p, ρ, D), to ρ = . i D =→.
Początkowym stanem maszyny Turinga jest

s

, kursor wskazuje na pierwszy

symbol

słowa wejściowego

(

danej

)

x ∈ (Σ \ {t})

∗

, którym musi być

.

.

Maszyna zgodnie z funkcją δ zmienia stan, zapisuje symbol i przesuwa
kursor. Po czym wykonuje kolejny krok. . .
Kursor nie ma możliwości przesunięcia się poza lewy koniec słowa
wejściowego. Jeżeli kursor przesuwa się poza prawy koniec słowa
wejściowego, przyjmujemy, że czyta symbol

t

.

Maszyna

zatrzymuje się

w przypadku osiągnięcia trzech stanów:

h

,

„tak”

lub

„nie”

. Jeżeli stanem jest

„tak”

, to mówimy, że maszyna

akceptuje

słowo wejściowe, jeżeli

„nie”

— to, że je

odrzuca

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

4 / 50

Podstawy maszyn Turinga

Jeżeli maszyna zatrzymuje się na słowie wejściowym x, to jako

wynik

(

słowo wyjściowe

) maszyny

M (x)

uważamy:

„tak”

jeżeli maszyna zaakceptowała x;

„nie”

jeżeli maszyna odrzuciła x;

y

jeżeli osiągnęła stan h, gdzie y jest słowem zapisanym na
taśmie maszyny w chwili zatrzymania,

y ∈ (Σ \ {t})

∗

i rozpoczyna się od . (na końcu może być ciąg symboli t).

Jeżeli M nie kończy obliczeń na słowie x, to piszemy

M (x) =%

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

5 / 50

Podstawy maszyn Turinga

Przykład

M = (K , Σ, δ, s), gdzie K = {s, p, q, r }, Σ = {0, 1, t, .}, δ w tabeli, x = 010

Tablica:

δ

(s,0)7→ (s, 0, →)
(s,1)7→ (s, 1, →)
(s,t)7→(p, t, ←)
(s,.)7→ (s, ., →)

(p,0)7→(q, t, →)
(p,1)7→(r , t, →)
(p,t)7→ (p, t, −)
(p,.)7→(h, ., →)

(q,0)7→(s, 0, ←)
(q,1)7→(s, 0, ←)
(q,t)7→(s, 0, ←)
(q,.)7→(h, ., →)
(r ,0)7→(s, 1, ←)
(r ,1)7→(s, 1, ←)
(r ,t)7→(s, 1, ←)
(r ,.)7→(h, ., →)

(s, .010) (s, .010)
(s, .010) (s, .010)
(s, .010t) (p, .010t)
(q, .01 t t) (s, .01t0)
(p, .01

t 0) (r , .0 t t0)

(s, .0t10) (p, .0 t 10)
(q, . t t10) (s, .t010)
(p, . t 010) (h, .t010)

Rysunek:

Obliczenie

maszyny Turinga

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

6 / 50

Podstawy maszyn Turinga

Konfiguracja

maszyny Turinga M jest trójką

(q, w, u) ∈ K × Σ

∗

× Σ

∗

,

gdzie

q

jest bieżącym stanem M ,

w

jest słowem na taśmie na lewo od

kursora wraz z symbolem wskazywanym przez kursor,

u

jest słowem na

prawo od kursora (być może pustym).

(s, ., 010) (s, .0, 10) (s, .01, 0) (s, .010, ) (s, .010t, ) (p, .010, t)

(q, .01 t t, ) (s, .01t, 0) (p, .01, t0) (r , .0 t t, 0) (s, .0t, 10)

(p, .0, t10) (q, . t t, 10) (s, .t, 010) (p, ., t010) (h, .t, 010)

Rysunek:

Konfiguracje maszyny Turinga z poprzedniego przykładu

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

7 / 50

Podstawy maszyn Turinga

Definicja

Maszyna Turinga M z (q, w, u)

przechodzi w jednym kroku

do (q

0

, w

0

, u

0

):

(q, w, u)

M

→ (q

0

, w

0

, u

0

)

, jeżeli dla σ będącego ostatnim symbolem w,

i δ(q, σ) = (p, ρ, D), zachodzi q

0

= p oraz dla

D =→

w

0

jest w z ρ zamiast ostatniego σ i dołączonym pierwszym

symbolem u (jeżeli u = , dołączamy t); u

0

jest u bez

pierwszego symbolu ( pozostaje );

D =←

w

0

jest w bez σ; u

0

jest u poprzedzonym przez ρ;

D = −

w

0

jest w z ρ zamiast σ, u

0

jest u.

M z (q, w, u)

przechodzi w k krokach

do (q

0

, w

0

, u

0

):

(q, w, u)

M

k

→ (q

0

, w

0

, u

0

)

, gdzie k ∈ N, jeżeli istnieją konfiguracje (q

i

, w

i

, u

i

),

i = 0, . . . , k, takie, że (q

i

, w

i

, u

i

)

M

→ (q

i+1

, w

i+1

, u

i+1

), przy czym

(q

0

, w

0

, u

0

) = (q, w, u) oraz (q

k

, w

k

, u

k

) = (q

0

, w

0

, u

0

).

M z (q, w, u)

przechodzi

do (q

0

, w

0

, u

0

):

(q, w, u)

M

∗

→ (q

0

, w

0

, u

0

)

, jeżeli

∃k ∈ N : (q, w, u)

M

k

→ (q

0

, w

0

, u

0

).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

8 / 50

Podstawy maszyn Turinga

Przykład (Maszyna Turinga obliczająca następnik dla liczb binarnych)

K = {s, q}, Σ = {0, 1, ., t}

p ∈ K

σ ∈ Σ

δ(p, σ)

s

0

(s, 0, →)

s

1

(s, 1, →)

s

t

(q, t, ←)

s

.

(s, ., →)

q

0

(h, 1, −)

q

1

(q, 0, ←)

q

t

(q, ., →)

(s, ., 11011) (s, .1, 1011) (s, .11, 011)
(s, .110, 11) (s, .1101, 1) (s, .11011, )
(s, .11011t, ) (q, .11011, t)
(q, .1101, 0t) (q, .110, 00t)
(h, .111, 00t)

Rysunek:

Obliczenie na wejściu 11011

(s, ., 111) (s, .1, 11) (s, .11, 1)
(s, .111, ) (s, .111t, ) (q, .111, t)
(q, .11, 0t) (q, .1, 00t) (q, ., 000t)
(h, .0, 00t)

Rysunek:

Obliczenie na wejściu 111

Dla słowa 1

k

następuje przepełnienie — błąd można naprawić stosując maszynę

z poprzedniego przykładu jako „podprogram” przesuwający słowo wejściowe
o jeden w prawo i dopisujący początkowe zero.

Maszyna realizująca taki program

poprawnie oblicza n + 1.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

9 / 50

Podstawy maszyn Turinga

Przykład (Maszyna Turinga dla palindromów)

s

0

(q

0

, ., →)

s

1

(q

1

, ., →)

s

.

(s, ., →)

s

t

(„tak”, t, −)

q

0

0

(q

0

, 0, →)

q

0

1

(q

0

, 1, →)

q

0

t

(p

1

, t, ←)

q

1

0

(q

1

, 0, ←)

q

1

1

(q

1

, 1, ←)

q

1

t

(p

1

, t, →)

p

0

0

(r , t, →)

p

0

1

(„nie”, 1, −)

p

0

.

(„tak”, ., →)

p

1

0

(„nie”, t, −)

p

1

1

(r , t, ←)

p

1

.

(„tak”, ., →)

r

0

(r , 0, ←)

r

1

(r , 1, ←)

r

.

(s, ., →)

(s, ., 0010)
(s, .0, 010)
(q

0

, . . 0, 10)

(q

0

, . . 01, 0)

(q

0

, . . 010, )

(q

0

, . . 010t, )

(p

0

, . . 010, t)

(r , . . 01, tt)
(r , . . 0, 1 t t)
(r , .., 01 t t)
(s, . . ., 1 t t)
(q

0

, . . .1, tt)

(q

0

, . . .1t, t)

(p

0

, . . .1, tt)

(„nie”, . . .1, tt)

Rysunek:

Obliczenie

dla 0010

(s, ., 101) (s, .1, 01)
(q

1

, . . 0, 1)

(q

1

, . . 01, )

(q

1

, . . 01t, )

(p

1

, . . 01, t)

(r , . . 0, tt)
(r , .., 0 t t)
(s, . . 0, tt)
(q

0

, . . .t, t)

(p

0

, . . ., tt)

(„tak”, . . .t, t)

Rysunek:

Obliczenie

dla 101

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

10 / 50

Maszyny Turinga jako algorytmy

Maszyny Turinga jako algorytmy

Maszyny Turinga nadają się do:

obliczania funkcji na słowach

rozpoznawania

i

rozstrzygania języków

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

11 / 50

Maszyny Turinga jako algorytmy

Definicja

Niech

L ⊂ (Σ \ {t})

∗

— język, a M — maszyna Turinga, taka że

∀x ∈ (Σ \ {t})

∗

:

(x ∈ L =⇒ M (x) = „tak”) ∧ (x 6∈ L =⇒ M (x) = „nie”) .

Mówimy wówczas, że

M rozstrzyga L

. Jeżeli język L jest rozstrzygany

przez pewną maszynę Turinga M , to L nazywamy

językiem rekurencyjnym

.

Maszyna M

rozpoznaje

język L, jeżeli

∀x ∈ (Σ \ {t})

∗

:

(x ∈ L =⇒ M (x) = „tak”) ∧ (x 6∈ L =⇒ M (x) =%) .

Jeżeli język L jest rozpoznawany przez pewną maszynę Turinga M , to L
nazywamy

językiem rekurencyjnie przeliczalnym

.

Rozpoznawanie nie jest prawdziwym problemem algorytmicznym a jedynie

użytecznym sposobem klasyfikacji problemów

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

12 / 50

Maszyny Turinga jako algorytmy

Stwierdzenie

Jeżeli język L jest rekurencyjny, to jest rekurencyjnie przeliczalny.

Dowód.

L jest rekurencyjny, więc istnieje M , króra rozstrzyga L. Zbudujemy M

0

, która

rozpoznaje L: niech M

0

zachowuje się tak jak M , z wyjątkiem sytuacji, gdy M ma

zatrzymać się i przejść do „nie”, wówczas M

0

przesuwa się w prawo i nigdy nie

zatrzymuje.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

13 / 50

Maszyny Turinga jako algorytmy

Definicja

Niech

f : (Σ \ {t})

∗

→ Σ

∗

i M jest maszyną Turinga z alfabetem Σ.

Mówimy, że

M oblicza f

, jeżeli

∀x ∈ (Σ \ {t})

∗

: M (x) = f (x) .

Jeżeli dla funkcji f istnieje obliczająca ją maszyna Turinga, to f nazywamy

funkcją rekurencyjną

.

Funkcja f : {0, 1}

∗

→ {0, 1, t}

∗

taka, że f (x) = tx, jest rekurencyjna

(obliczana przez maszynę z pierwszego przykładu). Funkcja
s : {0, 1}

∗

→ {0, 1, t}

∗

taka, że s(x) jest reprezentacją binarną n + 1, gdy

x jest reprezentacją binarną dotatniej liczby całkowitej n jest rekurencyjna.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

14 / 50

Maszyny Turinga jako algorytmy

Musimy zdecydować, w jaki sposób będziemy

zapisywać

problem

za

pomocą słowa

. Po ustaleniu reprezentacji, algorytm dla problemu

decyzyjnego jest maszyną Turinga rozstrzygającą odpowiedni język. Dla
problemów wymagających bardziej złożonej odpowiedzi, maszyna Turinga
oblicza odpowiednią funkcję na słowach.

Dowolny „skończony” obiekt matematyczny może być zapisany w postaci
skończonego słowa nad odpowiednim alfabetem: np. elementy zbioru skończonego
(wierzchołki grafu) jako liczby binarne, pary i k-krotki prostszych obiektów
zapisujemy z użyciem nawiasów i przecinków, zbiory skończone złożone
z prostszych obiektów reprezentujemy z użyciem nawiasów klamrowych itd. Graf
może być też reprezentowany przez

macierz sąsiedztwa

, którą można zapisać jako

słowo złożone z wierszy oddzielonych symbolem ‘;’.

Liczby całkowite, zbiory skończone, grafy i inne obiekty elementarne mogą
być zapisane na wiele sposobów, mogących się różnić formą i długością.

Wszystkie dopuszczalne kodowania są wielomianowo równoważne

. Dla

maszyny Turinga, rozwiązującej konkretny program obliczeniowy,
zakładamy, że używamy zwięzłej reprezentacji danych wejściowych.

Liczby

będziemy zawsze reprezentować binarnie

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

15 / 50

Maszyny Turinga z wieloma taśmami

Maszyny Turinga z wieloma taśmami

Definicja

Maszyna Turinga z k taśmami

(k ≤ 0) jest czwórką

M = (K , Σ, δ, s)

,

gdzie K , Σ i s mają takie same znaczenie jak dla zwykłej maszyny
Turinga, a

δ : K × Σ

k

→ (K ∪ {h, „tak”, „nie”}) × (Σ × {←, →, −})

k

jest

programem określającym kolejny stan maszyny, pisane symbole i kierunki
ruchu taśm na podstawie bieżącego stanu maszyny i czytanych symboli na
wszystkich taśmach.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

16 / 50

Maszyny Turinga z wieloma taśmami

Przykład (Maszyna Turinga o dwóch taśmach dla palindromów)

p ∈ K

σ

1

∈ Σ

σ

2

∈ Σ

δ(p, σ

1

, σ

2

)

s

0

t

(s, 0, →, 0, →)

s

1

t

(s, 1, →, 1, →)

s

.

.

(s, ., →, ., →)

s

t

t

(q, t, ←, t, −)

q

0

t

(q, 0, ←, t, −)

q

1

t

(q, 1, ←, t, −)

q

.

.

(p, ., →, t, ←)

p

0

0

(p, 0, →, t, ←)

p

1

1

(p, 1, →, t, ←)

p

0

1

(„nie”, 0, −, 1, −)

p

1

0

(„nie”, 1, −, 0, −)

p

t

.

(„tak”, t, −, ., →)

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

17 / 50

Maszyny Turinga z wieloma taśmami

Konfiguracja

maszyny Turinga z k taśmami jest to (2k + 1)-krotka

(q, w

1

, u

1

, . . . , w

k

, u

k

)

, gdzie q jest bieżącym stanem, w

i

u

i

słowem na i-tej

taśmie, a i-ty kursor wskazuje na ostatni symbol w

i

.

M z (q, w

1

, u

1

, . . . , w

k

, u

k

)

przechodzi do

(q, w

0

1

, u

0

1

, . . . , w

0

k

, u

0

k

):

(q, w

1

, u

1

, . . . , w

k

, u

k

)

M

→ (q, w

0

1

, u

0

1

, . . . , w

0

k

, u

0

k

) ,

jeżeli dla σ

i

będącego ostatnim symbolem w

i

(i = 1, . . . , k)

i δ(q, σ

1

, . . . , σ

k

) = (p, ρ

1

, . . . , ρ

k

, D

1

, . . . , D

k

) zachodzą dla każdego

i = 1, . . . , k takie warunki jak dla zwykłej maszyny Turinga. Analogicznie
definiujemy przechodzenie w n krokach.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

18 / 50

Maszyny Turinga z wieloma taśmami

Maszyna z k taśmami rozpoczyna obliczenia w konfiguracji

(s, ., x, ., , . . . , ., )

.

M (x) = „tak”

jeżeli

(s, ., x, ., , . . . , ., )

M

∗

→ („tak”, w

1

, u

1

, . . . , w

k

, u

k

)

M (x) = „nie”

jeżeli

(s, ., x, ., , . . . , ., )

M

∗

→ („nie”, w

1

, u

1

, . . . , w

k

, u

k

)

M (x) = y

jeżeli

(s, ., x, ., , . . . , ., )

M

∗

→ (h, w

1

, u

1

, . . . , w

k

, u

k

)

,

i

y = w

k

u

k

z usuniętymi początkowym . i końcowymi t

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

19 / 50

Maszyny Turinga z wieloma taśmami

Definicja

Jeżeli dla maszyny Turinga M z k taśmami i dla słowa wejściowego x
zachodzi relacja

(s, ., x, ., , . . . , ., )

M

t

→ (H , w

1

, u

1

, . . . , w

k

, u

k

) ,

gdzie H ∈ {h, „tak”, „nie”}, to

czas wymagany

przez maszynę M dla x

wynosi t. Jeżeli M (x) =%, to za czas wymagany przez M dla x
przyjmujemy ∞.
Maszyna M

działa w czasie f (n)

, jeżeli dla dowolnego słowa wejściowego

x czas wymagany przez maszynę M jest równy co najwyżej

f (|x|)

(|x| —

długość słowa

x).

Funkcja f (n) jest

ograniczeniem czasowym

dla M .

Niech

L ⊂ (Σ \ {t})

∗

będzie językiem rozstrzyganym przez maszynę

Turinga z wieloma taśmami działającą w czasie

f (n)

. Mówimy wówczas,

że

L ∈ TIME(f (n))

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

20 / 50

Maszyny Turinga z wieloma taśmami

TIME(f (n)) nazywamy

klasą złożoności

. Jest to zbiór języków

zawierający dokładnie te języki, które są rozstrzygane przez maszyny
Turinga z wieloma taśmami działające w czasie ograniczonym przez f (n).

Przykład

Liczba kroków potrzebnych maszynie Turinga (z jedną taśmą) do rozstrzygnięcia,
czy słowo długości n jest palindromem.
Maszyna działa w

d

n

2

e

etapach: Najpierw, w

2n + 1

krokach porównuje pierwszy

i ostatni symbol. Procedurę powtarza ze słowem długości

n − 2

, później

n − 4

,

itd. Całkowita liczba kroków wynosi co najwyżej
(2n + 1) + (2n − 3) + · · · = f (n) =

(n+1)(n+2)

2

. Język palindromów należy do

klasy

TIME(

(n+1)(n+2)

2

)

. Istotne jest tylko to, że f (n) jest funkcją kwadratową

n, tj., że f (n) = O(n

2

).

Oszacowanie jest pesymistyczne — obliczając f (n) musimy wziąć pod uwagę

najgorszy przypadek danych wejściowych

.

Dowolna

maszyna Turinga z jedną taśmą rozstrzygająca palindromy musi mieć

Ω(n

2

) czasu. Maszyna z dwiema taśmami potrzebuje czasu

f

0

(n) = 3n + 3

, czyli

palindromy są w klasie

TIME(3n + 3)

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

21 / 50

Maszyny Turinga z wieloma taśmami

Twierdzenie

Dla dowolnej maszyny Turinga z k taśmami działającej w czasie

f (n)

można zbudować maszynę Turinga M

0

działającą w czasie

O(f (n)

2

)

, taką

że dla dowolnego słowa wejściowego x zachodzi

M (x) = M

0

(x)

.

Dowód.

Niech M = (K , Σ, δ, s). Opiszemy M

0

= (K

0

, Σ

0

, δ

0

, s). Pojedyncza taśma M

0

musi

symulować k taśm M — na taśmie M

0

przechowujemy

konkatenację

słów z taśm M ,

pamiętamy także pozycję każdego kursora i prawy koniec każdego ze słów.
Niech Σ

0

= Σ ∪ Σ ∪ {.

0

, /}, gdzie Σ = {σ : σ ∈ Σ} jest zbiorem wersji symboli

z kursorem

. .

0

jest wersją ., przez którą można przejść w lewo, / oznacza prawy koniec

słowa. Konfiguracja (q, w

1

, u

1

, . . . , w

k

, u

k

) jest symulowana przez

(q, ., w

0

1

u

1

/ w

0

2

u

2

/ . . . w

0

k

u

k

/ /), w

0

i

oznacza w

i

z . zastąpionym przez .

0

i ostatnim σ

i

zastąpionym przez σ

i

; dwa / oznaczają koniec słowa M

0

.

Przed rozpoczęciem symulacji M

0

przesuwa słowo wejściowe o jedne w prawo, wstawia

na początku .

0

, po słowie wejściowym dopisuje /(.

0

/)

k−1

/ (co można uczynić dodając

2k + 2 nowych stanów M

0

).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

22 / 50

Maszyny Turinga z wieloma taśmami

Dowód (cd.)

M

0

symuluje jeden krok M dwukrotnie czytając swoje słowo od lewej do prawej

i z powrotem. W pierwszym przebiegu M

0

zbiera informacje o k symbolach

wskazywanych przez kursory, zapamiętuje je na nowych stanach, po jednym dla każdej
kombinacji stanu i k-krotki symboli M .
Na podstawie stanu w chwili zakończenia pierwszego przeglądu M

0

zna zmiany w słowie

odzwierciedlające zmiany wykonywane przez M w trakcie symulowanego kroku. M

0

w drugim przeglądzie zatrzymuje się przy symbolach podkreślonych i modyfikuje jeden
lub dwa symbole w sąsiedztwie, aby poprawnie zakodować zapisanie symbolu i zmianę
pozycji kursora M . (Jeżeli kursor na prawym końcu jednego ze słów M przesuwa się
w prawo, to trzeba utworzyć miejsce na nowy symbol (t): zmieniamy / na /

0

i przesuwamy kursor do prawego końca, a następnie przesuwamy wszystkie symbole o 1
w prawo, aż do /

0

włącznie, na jego pozycji piszemy t).

Symulację kontynuujemy aż do zatrzymania sie M . Wtedy M

0

kasuje zawartość

wszystkich taśm M z wyjątkiem ostatniej i zatrzymuje się.
M zatrzymuje się w czasie f (|x|), czyli żadne z jej słów nie jest dłuższe niż f (|x|).
Zatem całkowita długość słowa na taśmie M

0

nie przekracza k(f (|x|) + 1) + 1.

Symulacja jednego kroku wymaga najwyżej dwukrotnego przejścia tego słowa tam
i z powrotem, czyli 4k(f (|x|) + 1) + 4 ruchy plus najwyżej 3k(f (|x|) + 1) + 3 ruchów na
każdą taśmę symulowanej maszyny. Razem otrzymujemy O(k

2

f (|x|)

2

, czyli O(f (|x|)

2

),

gdyż k jest ustalone i niezależne od x.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

23 / 50

Maszyny Turinga z wieloma taśmami

Nie wymyślono żadnych „realnych” ulepszeń maszyny Turinga, które
zwiększyłyby dziedzinę rozstrzyganych przez nie języków czy wpłynęły
bardziej niż wielomianowo na szybkość ich działania.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

24 / 50

Maszyny Turinga z wieloma taśmami

Maszyny Turinga (wykład 2)

1

Podstawy maszyn Turinga

2

Maszyny Turinga jako algorytmy

3

Maszyny Turinga z wieloma taśmami

4

Liniowe przyśpieszanie

5

Ograniczenia pamięciowe

6

Maszyny o dostępie swobodnym (RAM)

7

Maszyny niedeterministyczne

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

25 / 50

Liniowe przyśpieszanie

Liniowe przyśpieszanie

Twierdzenie

Niech

L ∈ TIME(f (n))

. Wówczas ∀ > 0 zachodzi

L ∈ TIME(f

0

(n))

,

gdzie

f

0

(n) = f (n) + n + 2

.

Dowód.

M = (K , Σ, δ, s) jest maszyną z k taśmami, rozstrzygającą L i działającą w czasie f (n).
Zbudujemy M

0

= (K

0

, Σ

0

, δ

0

, s

0

) z k

0

taśmami, działającą w czasie f

0

(n) i

symulującą

M . Liczba taśm k

0

= k, gdy k > 1 i k

0

= 2, gdy k = 1. Każdy symbol M

0

koduje kilka

symboli M , stąd M

0

symuluje kilka ruchów M w czasie jednego ruchu.

Niech m będzie liczbą całkowitą zależną jedynie od M i . Alfabet M

0

prócz symboli M

zawiera m-

krotki

symboli M , tzn. Σ

0

= Σ ∪ Σ

m

. Początkowo M

0

przesuwa kursor po 1.

taśmie w prawo, czytając x. Po przeczytaniu m symboli σ

1

σ

2

. . . σ

n

na 2. taśmie

dopisywany jest

jeden symbol

(σ

1

, σ

2

, . . . , σ

n

) ∈ Σ

0

. Symbole zapamiętujemy w stanach

M

0

, jest to możliwe po dodaniu do K

0

stanów K × Σ

i

dla i = 1, . . . , m − 1. Jeżeli

w trakcie budowania m-krotki natrafimy na koniec x, uzupełniamy krotkę dopisując
wymaganą liczbę t. Po m



|x|

m



+ 2 krokach 2. taśma zawiera (za skrajnym lewym .)

skompresowane słowo wejściowe. Pozostałe taśmy M (o ile były), zawierają ..

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

26 / 50

Liniowe przyśpieszanie

Dowód (cd.).

Od teraz 2. taśmę traktujemy jako taśmę zawierającą wejście. Jeżeli k > 1, to 1. taśmę
traktujemy jako zwykłą taśmę roboczą (wpisujemy . po słowie wejściowym). Wszystkie
k taśm będzie zawierało jedynie m-krotki symboli.
M

0

symuluje m ruchów M w co najwyżej 6 swoich ruchach, taką symulację m kroków

M nazywamy

etapem

. Na początku etapu stan M

0

zawiera (k + 1)-krotkę

(q, j

1

, . . . , j

k

), gdzie q jest stanem M na początku etapu oraz j

i

≤ m jest pozycją i-tego

kursora

wewnątrz

aktualnie czytanej m-krotki. Jeżeli więc w pewnym momencie stan M

jest q, a i-ty kursor M jest na l-tym symbolu (licząc od pierwszego .), to i + 1-szy
kursor M

0

wskazuje na



l

m



-ty symbol na prawo od ., a stanem M

0

jest (q, l mod m).

Następnie M

0

przesuwa wszystkie kursory o jedną pozycję w prawo, potem o dwie

pozycje w prawo, następnie o jedną w lewo. W stanie M

0

zapamiętane są wszystkie

symbole wskazywane przez kursory lub stojące tuż obok (dodajemy do K

0

wszystkie

stany K × {1, . . . , m}

k

× Σ

3mk

).

Na podstawie tej informacji M

0

może w pełni

przewidzieć m kolejnych ruchów M

. Istotnie, w m krokach żaden z kursorów M nie

wyjdzie poza obszar bieżącej m-krotki oraz m-krotek bezpośrednio z nią sąsiadujących.
Dalej M

0

korzysta z δ

0

, aby w dwóch krokach dokonać zmian w zawartości taśm i ustalić

stan po m ruchach M . Symulacja m kroków M jest zakończona w 6 krokach M

0

.

Po zaakceptowaniu lub odrzuceniu słowa wejściowego przez M , M

0

zatrzymuje się

z takim samym wynikiem. Czas pracy maszyny M

0

dla słowa x wynosi w najgorszym

przypadku |x| + 2 + 6



f (|x|)

m



. Wybierając m =



6




otrzymujemy tezę.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

27 / 50

Liniowe przyśpieszanie

Maszyny działające w czasie krótszym niż n, istnieją, ale nie są
interesujące, gdyż maszyna Turinga potrzebuje n kroków na przeczytanie
całego słowa wejściowego. Zatem każde „przyzwoite” ograniczenie
czasowe spełnia zależność f (n) ≥ n. Jeżeli f (n) jest liniowa, np.
f (n) = cn dla stałej c > 1, to twierdzenie mówi, że można stałą c uczynić
dowolnie bliską 1. Jeżeli f (n) jest nadliniowa, wtedy stały czynnik
w najbardziej znaczącym wyrazie może być dowolnie zmniejszony, tzn.
ograniczenie czasowe może być

dowolnie liniowo zmniejszone

. Wyrazy

niższego rzędu mogą być całkowicie pominięte.
Każde wielomianowe ograniczenie czasowe może być reprezentowane przez
najbardziej znaczący wyraz. Jeżeli L jest językiem wielomianowo
rozstrzygalnym, to należy do klasy TIME(n

k

) dla pewnego k > 0.

Sumę wszystkich klas TIME(n

k

), czyli zbiór języków rozstrzygalnych

w czasie wielomianowym przez maszyny Turinga, oznaczamy przez P. Jest
to najważniejsza klasa złożoności obliczeniowej.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

28 / 50

Ograniczenia pamięciowe

Ograniczenia pamięciowe

Przyjmijmy, że

pamięć używana przez maszynę M na x

podczas obliczenia

(s, ., x, . . . , ., )

M

∗

→ (H , w

1

, u

1

, . . . , w

k

, u

k

) jest równa

P

k
i=1

|w

i

u

i

|.

W oszacowaniu tym ukryty jest spory nadmiar.

Przykład

Czy można rozpoznawać palindromy w pamięci zdecydowanie mniejszej niż n?
Taśma 1. zawiera x i

nigdy się nie zmienia

. W i-tym etapie taśma 2. zawiera

zapisaną binarnie liczbę całkowitą i. Rozpoznajemy i zapamiętujemy i-ty symbol
x: wpisujemy do taśmy 3. j = 1 i porównujemy i z j przez przesuwanie kursorów
na taśmach: jeżeli j < i, zwiększamy j o 1 i przesuwamy kursor taśmy 1.
w prawo; jeżeli j = i, zapamiętujemy czytany symbol, ustalamy j = 1
i odnajdujemy i-ty od końca symbol x.
Jeżeli odnalezione symbole są różne — zatrzymujemy w „nie”; jeżeli równe,
zwiększamy i o 1 i rozpoczynamy kolejny etap. Jeżeli podczas pewnego etapu
i-tym symbolem x będzie t — zatrzymujemy w stanie „tak”.
Używana pamięć wynosi

O(log n)

. Maszyna

tylko odczytuje

x. Słowa na

pozostałych taśmach są nie dłuższe niż

log n + 1

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

29 / 50

Ograniczenia pamięciowe

Niech k > 2 i k ∈ N.

Maszyna Turinga z k taśmami oraz wejściem

i wyjściem

jest maszyną Turinga z k taśmami, której program δ spełnia

następujący warunek: jeżeli δ(q, σ

1

, . . . , σ

k

) = (p, ρ

1

, D

1

, . . . , ρ

k

, D

k

), to

σ

1

= ρ

1

i D

k

6=←, a ponadto jeżeli σ = t, to D

1

=←.

Stwierdzenie

Dla dowolnej maszyny Turinga M działającej w czasie ograniczonym przez
f (n) istnieje maszyna Turinga M

0

o k + 2 taśmach z wyróżnionym

wejściem i wyjściem, działająca w czasie O(f (n)).

Dowód.

M

0

rozpoczyna pracę od przekopiowania wejścia na taśmę 2., a następnie symuluje pracę

M o k taśmach na taśmach o numerach od 2 do k + 1. Gdy M się zatrzymuje, M

0

kopiuje wynik na taśmę k + 2. i zatrzymuje się.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

30 / 50

Ograniczenia pamięciowe

Definicja

Niech dla maszyny Turinga z k taśmami i słowa wejściowego x zachodzi

(s, ., x, . . . , ., )

M

∗

→ (H , w

1

, u

1

, . . . , w

k

, u

k

), gdzie H ∈ {h, „tak”, „nie”}

jest stanem końcowym.

Pamięcią wymaganą przez maszynę M dla słowa

wejściowego x

jest

P

k
i=1

|w

i

u

i

|

. Jeżeli M jest maszyną z wyróżnionym

wejściem i wyjściem, to

pamięć wymagana przez maszynę M dla słowa

wejściowego x

jest

P

k−1
i=2

|w

i

u

i

|

. Niech f : N → N. Mówimy, że

maszyna

Turinga działa w pamięci ograniczonej przez f (n)

, jeżeli dla dowolnego

słowa wejściowego x M potrzebuje najwyżej pamięci f (|x|).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

31 / 50

Ograniczenia pamięciowe

Definicja

Niech L będzie językiem. Mówimy, że L należy do

klasy złożoności

pamięciowej SPACE(f (n))

, jeżeli istnieje maszyna Turinga

z wyróżnionym wejściem i wyjściem, która rozstrzyga L i działa w pamięci
ograniczonej przez f (n).

Palindromy należą do klasy SPACE(log n). Ta ważna klasa jest
oznaczana przez

L

.

Twierdzenie

Niech L będzie językiem z klasy SPACE(f (n)). Wtedy dla dowolnego
 > 0 zachodzi L ∈ SPACE(2 + f (n)).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

32 / 50

Maszyny o dostępie swobodnym (RAM)

Maszyny o dostępie swobodnym (RAM)

Czy maszyny Turinga mogą służyć do implementacji dowolnych
algorytmów?

Twierdzimy, że tak

. Nieformalne twierdzenie, znane jako

teza Churcha

,

stanowi, że każdy algorytm może być przedstawiony jako maszyna Turinga.

Każda sensowna próba stworzenia matematycznego modelu obliczeń
komputerowych i zdefiniowania czasu jego działania musi doprowadzić do
modelu obliczeń i związanej z nim miary kosztu czasowego, które są
wielomianowo równoważne maszynom Turinga.

Zdefiniujemy model obliczeń oddający wiele cech współczesnych
algorytmów komputerowych i pokażemy, że jest on wielomianowo
równoważny maszynie Turinga.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

33 / 50

Maszyny o dostępie swobodnym (RAM)

Maszyna o dostępie swobodnym

(

RAM

1

) jest urządzeniem liczącym

składającym się z programu operującego na jednej strukturze
danych —

tablicy rejestrów

. Każdy z rejestrów może przechowywać

dowolnie dużą liczbę całkowitą

. Instrukcje RAM przypominają instrukcje

prawdziwych komputerów:

Instrukcje RAM

READ

j

r

0

← i

j

READ

∗j

r

0

← i

r

j

STORE

j

r

j

← r

0

STORE

∗j

r

r

j

← r

0

LOAD

x

r

0

← x

ADD

x

r

0

← r

0

+ x

SUB

x

r

0

← r

0

− x

HALF

r

0

← b

r

0

2

c

JUMP

j

κ ← j

JPOS

j

if r

0

> 0 then κ ← j

JZERO

j

if r

0

= 0 then κ ← j

JNEG

j

if r

0

< 0 then κ ← j

HALT

κ ← 0

j — liczba całkowita; r

j

— zawartość rejestru j; i

j

— i-ty element wejścia;

x — argument postaci j, ∗j lub = j. Wartość j wynosi r

j

, ∗j — r

r

j

, = j — j.

κ — licznik rozkazów. Każda instrukcja, dla której jawnie nie zaznaczono zmiany
κ, powoduje κ ← κ + 1.

1

Random Access Machine.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

34 / 50

Maszyny o dostępie swobodnym (RAM)

Formalnie,

program

RAM jest skończonym ciągiem

instrukcji

Π = (π

1

, π

2

, . . . , π

m

)

, gdzie każda z instrukcji π

i

jest jedną z podanych.

W każdej chwili obliczeń rejestr i (i ≥ 0) zawiera liczbę całkowitą,
oznaczaną przez r

i

. W każdym momencie obliczeń wykonywana jest

instrukcja π

κ

, gdzie liczba κ jest „licznikiem programu”. Wykonanie

instrukcji może dać w wyniku zmianę wartości jednego z rejestrów i zmianę
κ.

Semantyka

(

znaczenie

) instrukcji jest zbliżona do asemblera.

Rejstr 0 jest

akumulatorem

, w którym wykonuje się obliczenia. Maszyna

RAM ma trzy

tryby adresowania

:

argumenty

mogą być: w rejestrze j (

j

),

w rejestrze,

którego numer znajduje się w

rejestrze j (

∗j

) lub samą liczbą j

(

= j

).

Instrukcja powoduje także zmianę κ. O ile nie jest to jedna z instrukcji
skoku lub HALT, to κ jest zwiększane o 1. HALT powoduje zatrzymanie
obliczeń, przyjmujemy, że dowolna

semantycznie niepoprawna

instrukcja

jest równoważna HALT. Początkowo rejestry zawierają 0.

Dane

programu

RAM to skończony ciąg liczb całkowitych zawartych w skończonej tablicy

rejestrów danych

, I = (i

1

, . . . , i

n

). W chwili zakończenia pracy poprawny

wynik znajduje się w akumulatorze.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

35 / 50

Maszyny o dostępie swobodnym (RAM)

RAM realizuje π

1

i wykonuje dyktowane przez nią zmiany. Następnie

realizuje π

κ

, gdzie κ jest nową wartością licznika programu, itd., aż do

zatrzymania. Obliczenia RAM można sformalizować, używając pojęcia

konfiguracji maszyny RAM

— pary C = (κ, R), gdzie κ jest instrukcją,

która ma być wykonana, a R = {(j

1

, r

j

1

), (j

2

, r

j

2

), . . . , (j

k

, r

j

k

)} jest

skończonym zbiorem

par rejestr-wartość

. R opisuje tylko te rejestry,

w których jest niezerowa wartość. Początkową konfiguracją jest więc (1, ∅).
Ustalmy program Π oraz dane I . Niech C = (κ, R) i C

0

= (κ

0

, R

0

) będą

konfiguracjami. RAM

przechodzi w jednym kroku

z C do C

0

,

(κ, R)

Π,I

→ (κ

0

, R

0

)

, jeżeli κ

0

jest nową wartością κ po wykonaniu π

κ

— κ-tej

instrukcji programu Π oraz R

0

= R, jeżeli π

κ

było instrukcją skoku lub

HALT, albo R

0

powstaje z R przez przez zastąpienie pary (j, x) parą (j, x

0

)

obliczoną zgodnie z treścią instrukcji π

κ

.

Przechodzenie w k krokach

Π,I

k

→

i

przechodzenie

Π,I

∗

→

definiujemy przez analogię.

Niech Π — program RAM, D — zbiór skończonych ciągów liczb
całkowitych i φ funkcja całkowitoliczbowa na D.

Π oblicza φ

, jeżeli dla

dowolnego I ∈ D zachodzi (1, ∅)

Π,I

∗

→ (0, R), gdzie (0, φ(I )) ∈ R.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

36 / 50

Maszyny o dostępie swobodnym (RAM)

Określając wymagania czasowe dla programów RAM, przyjmujemy
założenie, że

liczymy każdą operację jako pojedynczy krok

.

Niech b(i) będzie

binarną reprezentacją

liczby całkowitej i bez zer

wiodących i ze znakiem „−”, jeżeli i < 0.

Długością

liczby całkowitej i

jest `(i) = |b(i)|. Jeżeli I = (i

1

, . . . , i

k

) jest ciągiem liczb, to jego

długość

wynosi `(I ) =

P

k
j=1

`(i

j

).

Niech program Π RAM oblicza funkcję całkowitoliczbową φ na D. Niech f
będzie funkcją określoną na liczbach naturalnych o wartościach

naturalnych i niech dla dowolnego I ∈ D zachodzi (1, ∅)

Π,I

k

→ (0, R), gdzie

k ≤ f (`(I )). Mówimy, że

Π oblicza φ w czasie f (n)

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

37 / 50

Maszyny o dostępie swobodnym (RAM)

Dowolna maszyna Turinga może być symulowana przez program RAM.
Niech Σ = {σ

1

, . . . , σ

k

} będzie alfabetem maszyny Turinga. Niech D

Σ

będzie zbiorem skończonych ciągów liczb całkowitych:
D

Σ

= {(i

1

, . . . , i

n

, 0) : n ≥ 0, 1 ≤ i

j

≤ k, j = 1, . . . , n}. Jeżeli

L ∈ (Σ \ {t})

∗

jest językiem, to definiujemy na D

Σ

funkcję φ

L

o wartościach w {0, 1} taką, że φ

L

(i

1

, . . . , i

n

, 0) = 1, jeżeli

σ

i

1

, . . . , σ

i

n

∈ L, i 0 w przeciwnym razie.

Twierdzenie

Jeżeli L jest językiem należącym do TIME(f (n)), to istnieje program
RAM obliczający φ

L

w czasie O(f (n)).

Dowód.

Niech M = (K , Σ, δ, s) — maszyna Turinga rozstrzygająca L w czasie f (n). Program
RAM rozpoczyna od skopiowania danych do rejestrów o numerach od 4 do n + 3.
Rejestr 1 zawiera 4 — będzie wskazywał na rejestr zawierający symbol pod kursorem.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

38 / 50

Maszyny o dostępie swobodnym (RAM)

Dowód (cd.).

Następnie symulujemy działanie maszyny Turinga krok po kroku. Program ma ciąg
instrukcji symulujący działanie każdego stanu q ∈ K . Ciąg ten składa się z k podciągów,
gdzie k = |Σ|. Niech j-ty podciąg rozpoczyna się od instrukcji o numerze N

q,σ

j

.

Przypuśćmy, że δ(q, σ

j

) = (p, σ

l

, D). Wówczas instrukcje j-tego podciągu są

następujące:

N

q,σ

j

LOAD ∗1

pobierz symbol wskazywany przez kursor

N

q,σ

j

+ 1

SUB = j

odejmij j — numer badanego symbolu

N

q,σ

j

+ 2

JZERO N

q,σ

j

+ 4

jeżeli symbolem jest σ

j

, to trzeba coś wykonać

N

q,σ

j

+ 3

JUMP N

q,σ

j+1

w przeciwnym razie przejdź do następnego symbolu

N

q,σ

j

+ 4

LOAD l

σ

l

jest właśnie zapisanym symbolem

N

q,σ

j

+ 5

STORE ∗1

zapisz σ

l

N

q,σ

j

+ 6

LOAD 1

pozycja kursora

N

q,σ

j

+ 7

ADD = d

d jest 1 dla D =→, −1 dla D =← i 0 dla D = −

N

q,σ

j

+ 8

STORE 1

N

q,σ

j

+ 9

JUMP N

p,σ

1

rozpocznij symulację stanu p

Stany „tak” i „nie” są symulowane przez proste sekwencje instrukcji RAM, pobierające
odpowiednio stałą 1 lub 0 do akumulatora, a następnie wykonujące HATL.
Czas konieczny do wykonania instrukcji symulujących pojedynczy ruch jest stały (zależny
od M ). Dodatkowo potrzeba jedynie O(n) instrukcji na przekopiowanie danych.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

39 / 50

Maszyny o dostępie swobodnym (RAM)

Lemat

Po t krokach obliczeń programu RAM na danych I zawartość każdego
rejestru ma długość najwyżej t + `(I ) + `(B), gdzie B jest największą
liczbą całkowitą zapisaną jawnie w instrukcji programu Π.

Dowód.

Przez indukcję względem t. Teza jest prawdziwa przed wykonaniem pierwszego kroku,
gdy t = 0. Załóżmy jej prawdziwość aż do wykonania kroku t. Może zajść kilka
przypadków. Jeżeli wykonywana instrukcja jest instrukcją skoku lub zatrzymania, to
zawartość żadnego rejestru się nie zmienia. Jeżeli jest to LOAD lub STORE, to
zawartość modyfikowanych rejestrów pochodzi z innych rejestrów, była więc w nich
w poprzednim kroku obliczeń, więc teza zachodzi. Jeżeli instrukcją jest READ, to wyraz
`(I ) z ograniczenia gwarantuje zachodzenie tezy. Jeżeli instrukcja jest instrukcją
arytmetyczną, to wykonuje ona działanie na dwóch liczbach i i j, z których każda jest
albo zawarta w rejestrze w poprzednim kroku, albo zapisana w programie Π, więc w tym
przypadku nie większa niż B. Długość wyniku może być co najwyżej o 1 większa niż
długość najdłuższego argumentu, który z założenia indukcyjnego jest nie dłuższy niż
t − 1 + `(I ) + `(B). Zatem i w tym przypadku zachodzi teza.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

40 / 50

Maszyny o dostępie swobodnym (RAM)

Dowolna maszyna RAM może być symulowana przez maszynę Turinga
jedynie z wielomianową utratą efektywności. Załóżmy, że φ jest funkcją
określoną na D o wartościach całkowitych, gdzie D jest zbiorem
skończonych ciągów liczb całkowitych. Binarna reprezentacja ciągu
I = (i

1

, . . . , i

n

), oznaczana b(I ) jest słowem b(i

1

); . . . ; b(i

n

). Mówimy, że

maszyna Turinga M

oblicza φ

, jeżeli dla dowolnego I ∈ D zachodzi

M (b(I )) = b(φ(I )).

Twierdzenie

Jeżeli program Π maszyny RAM oblicza funkcję φ w czasie f (n), to
istnieje maszyna Turinga M z 7 taśmami, obliczająca φ w czasie O(f (n)

3

).

Dowód.

1. taśma M jest taśmą wejściową tylko do odczytu. 2. taśma zawiera reprezentację
zawartości rejestrów R i składa się z sekwencji słów postaci b(i) : b(r

i

) oddzielonych ‘;’

oraz, ewentualnie, ciągami znaków pustych. Całość kończymy specjalnym znakiem, np.
/. Za każdym razem, gdy uaktualniana jest zawartość rejestru i, poprzednia para jest
kasowana (zapisujemy w to miejsce ciąg t), a nowa para jest dopisywana na końcu
słowa.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

41 / 50

Maszyny o dostępie swobodnym (RAM)

Dowód (cd.).

Stany M dzielimy na m grup, gdzie m jest liczbą instrukcji w Π. Potrzebne w danej
chwili zawartości rejestrów odnajdujemy przeglądając 2. taśmę od lewej do prawej.
Wymagane są najwyżej dwa przejścia przez tę taśmę (w przypadku adresowania
pośredniego). 3. taśma zawiera bieżącą wartość κ. 4. taśmę wykorzystujemy do
przechowywania adresu poszukiwanego rejestru. Za każdym razem, gdy czytamy parę
b(i) : b(r

i

), zawrtość 4. taśmy jest porównywana z b(i). Jeżeli są identyczne, to b(r

i

)

jest przenoszone na inne taśmy celem dlaszego przetworzenia. Wszystkie operacje
wykonujemy na pozostałych trzech taśmach. W przypadku operacji arytmetycznych
dwie taśmy zawierają argumenty, a wynik wyliczany jest na trzeciej taśmie. Po
obliczeniu aktualizujemy drugą taśmę. Na koniec symulacji instrukcji kolejny stan
rozpoczyna wykonanie następnej instrukcji progamu Π. Po dojściu do HALT, zawartość
rejestru 0 jest przenoszona z taśmy 2. na 7.
Musimy pokazać, że symulacja instrukcji programu Π zabiera M czas O(f (n)

2

), gdzie n

jest długością danych. Zdekodowanie bieżącej instrukcji Π i stałych w niej
występujących można wykonać w stałym czasie. Pobranie z 2. taśmy wartości rejestrów
zabiera M O(f (n

2

)) czasu (taśma 2. zawiera O(f (n)) par, każda długości O(f (n))), jak

wynika z lematu; samo przeszukanie może być dokonane w czasie liniowym). Obliczenie
wyniku składa się z prostych operacji arytmetycznych na liczbach całkowitych długości
O(f (n)), z których każda może być wykonana w czasie O(f (n)).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

42 / 50

Maszyny niedeterministyczne

Maszyny niedeterministyczne

Wprowadzimy teraz

nierealistyczny

model obliczeń, który może być

symulowany przez wprowadzone wcześniej modele przy

wykładniczym

wzroście czasu.

Niedeterministyczna maszyna Turinga

jest czwórką

N = (K , Σ, ∆, s)

,

gdzie K , Σ i s są takie, jak w zwykłej maszynie Turinga, natomiast ∆ma
możliwość

wyboru

między kilkoma akcjami, nie jest funkcją, lecz relacją:

∆ ⊂ (K × Σ) × [(K ∪ {h, „tak”, „nie”}) × Σ × {←, →, −}]

— dla każdej

kombinacji stanu i symbolu może istnieć

więcej niż jeden

kolejny krok lub

nie istnieje żaden.
Konfigurację maszyn niedeterministycznych określamy tak samo, ale

przechodzenie

nie jest funkcją, lecz

relacją

: Niedeterministyczna maszyna

Turinga N

przechodzi w jednym kroku

z (q, w, u)

do (q

0

, w

0

, u

0

) —

(q, w, u)

N

→ (q

0

, w

0

, u

0

)

— jeżeli w ∆ jest reguła, która

pozwala na takie przejście.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

43 / 50

Maszyny niedeterministyczne

Formalnie:

(q, w, u)

N

→ (q

0

, w

0

, u

0

)

,

jeżeli istnieje ((q, σ), (q

0

, ρ, D)) ∈ ∆, że albo

D =→

i w

0

jest w z σ zastąpionym przez ρ i dołączonym pierwszym

symbolem u, a u

0

jest u bez pierwszego symbolu;

D =←

i w

0

jest w bez σ, a u

0

jest u poprzedzonym przez ρ;

D = −

i w

0

jest w z σ zastąpionym przez ρ i u

0

jest u.

Relacje

N

k

→

i

N

∗

→

definiujemy jak poprzednio.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

44 / 50

Maszyny niedeterministyczne

Niech L będzie językiem, a N niedeterministyczną maszyną Turinga. N

rozstrzyga

L, jeżeli dla każdego x ∈ Σ

∗

jest prawdą, że x ∈ L wtedy i tylko

wtedy, gdy (s, ., x)

N

∗

→ („tak”, w, u) dla pewnych słów w i u

Niedeterministyczna maszyna Turinga N rozstrzyga język L

w czasie f (n)

,

gdzie f jest funkcją z liczb naturalnych w liczby naturalne, jeżeli N
rozstrzyga L i ponadto dla dowolnego x ∈ Σ

∗

, jeżeli

(s, ., x)

N

k

→ („tak”, w, u), to k ≤ f (|x|).

Zbiór języków rozstrzyganych przez niedeterministyczne maszyny Turinga
tworzy klasę złożoności

NTIME(f (n))

.

Najważniejszą klasą złożoności

niedeterministycznej jest NP, suma wszystkich klas NTIME(n

k

)

.

Możemy natychmiast zauważyć, że

P ⊆ NP

, gdyż maszyny

deterministyczne są maszynami niedeterministycznymi, dla których ∆ jest
funkcją.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

45 / 50

Maszyny niedeterministyczne

Przykład

Nie wiadomo, czy tsp (d) jest w P, łatwo jednak można zauważyć, że tsp (d)
jest w NP.
Istotnie, tsp (d) może być rozstrzygnięty przez niedetermininstyczną maszynę
Turinga w czasie O(n

2

). Maszyna ta dla słowa wejściowego zawierającego

reprezentację przykładu tsp zapisuje

dowolny ciąg symboli

niedłuższy niż słowo

wejściowe, po czym wraca na początek zapisanego słowa i sprawdza, czy
reprezentuje ono permutacją wszystkich miast. Jeżeli tak, to sprawdza jeszcze,
czy permutacja ta jest drogą o koszcie mniejszym niż B. Oba zadania mogą być
wykonane w czasie O(n

2

) przy użyciu 2. taśmy. Jeżeli wygenerowane słowo jest

rzeczywiście kodem drogi tańszej niż B, to jest akceptowane, w przeciwnym
wypadku — odrzucane.
Maszyna rzeczywiście rozstrzyga tsp (d), gdyż akceptuje słowo wejściowe wtedy
i tylko wtedy, gdy jest pozytywnym przykładem tsp (d) — jeżeli na wejściu
podany jest przykład pozytywny, to istnieje droga przechodząca przez wszystkie
miasta o koszcie niższym niż B, a więc istnieje obliczenie maszyny, które tę
permutację „odgadnie” i sprawdzi, że ma niższy niż B koszt i zakończy się
akceptacją. Gdy takiej drogi nie ma, to maszyna nie może jej „odgadnąć” i każde
słowo odrzuci.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

46 / 50

Maszyny niedeterministyczne

Twierdzenie

Jeżeli istnieje niedeterministyczna maszyna Turinga N rozstrzygająca język
L w czasie

f (n)

, to istnieje deterministyczna maszyna Turinga o trzech

taśmach M , rozstrzygająca L w czasie

O(c

f (n)

)

, gdzie c > 1 jest stałą

zależną od N .

Wynik ten można wyrazić przy pomocy klas złożoności:

NTIME(f (n)) ⊆

[

c>1

TIME(c

f (n)

) .

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

47 / 50

Maszyny niedeterministyczne

Dowód.

Niech N = (K , Σ, ∆, s). Dla każdego (q, σ) ∈ K × Σ rozważmy zbiór wyborów
C

q,σ

= {(q

0

, σ

0

, D} : ((q, σ), (q

0

, σ

0

, D)) ∈ ∆}. C

q,σ

jest zbiorem skończonym,

d = max

q,σ

|C

q,σ

|, d > 1.

Obliczenie N jest ciągiem t wyborów niedeterministycznych (c

1

, c

2

, . . . , c

t

), gdzie

c

j

∈ {0, 1, . . . , d − 1}. M rozważa wszystkie takie ciągi w kolejności rosnących długości

i symuluje N na każdym z nich. Rozważany ciąg (c

1

, c

2

, . . . , c

t

) M przechowuje na

drugiej taśmie. M symuluje działanie N , tak jak

działałaby ona, gdyby dokonywała

wyboru c

i

w i-tym kroku

. M symuluje w ten sposób t początkowych kroków N . Jeżeli

doprowadza to N do „tak”, to M zatrzymuje się w „tak”, w przeciwnym razie M bada
kolejny ciąg wyborów.
M wykrywa, że N odrzuca słowo wejściowe jeżeli sprawdzając działanie N na wszystkich
ciągach długości t nie odkryje

żadnego obliczenia, które może być kontynuowane

(tzn.

wszystkie kończą się w h lub „nie”).
Czas potrzebny M na symulację jest ograniczony przez liczbę ciągów wyboru

P

f (n)

t=1

d

t

= O(d

f (n)+1

) razy czas konieczny do wygenerowania i rozważenia każdego

wyboru O(2

f (n)

).

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

48 / 50

Maszyny niedeterministyczne

Pamięć

używaną przez maszyny niedeterministyczne definiujemy

rozszerzając definicję niedeterministycznej maszyny Turinga do

niedeterministycznej maszyny Turinga z wyróżnioną taśmą wejściową
i wyjściową

.

Mówimy, że niedeterministyczna maszyna Turinga N = (K , Σ, ∆, s) z k
taśmami, w tym wyróżnioną taśmą wejściową i wyjściową, rozstrzyga język
L w pamięci f (n), jeżeli N rozstrzyga L i dodatkowo, jeżeli dla dowolnego

x ∈ (Σ \ {t})

∗

zachodzi (s, ., x, . . . , ., )

N

∗

→ (q, w

1

, u

2

, . . . , w

k

, u

k

), to

P

k−1
j=2

|w

j

u

j

| ≤ f (|x|).

Przykład

Algorytm deterministyczny dla reachibility wymagał pamięci liniowej. Na
maszynie niedeterministycznej wystarczy O(log n) pamięci.
Oprócz wejściowego używamy dwóch taśm: na 1. zapisujemy binarnie wierzchołek
i (początkowo 1), na 2. odgadniętą liczbę całkowitą j ≤ n (kolejny wierzchołek
ścieżki). Następnie sprawdzamy, czy bit (i, j) macierzy sąsiedztwa jest 1. Jeżeli
nie, maszynę zatrzymujemy i słowo odrzucamy. Jeżeli tak, to sprawdzamy, czy
j = n. Jeżeli tak, to kończymy i akceptujemy, jeżeli nie, to kopiujemy j na 1.
taśmę i całość powtarzamy.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

49 / 50

Maszyny niedeterministyczne

Niedeterministyczna maszyna Turinga nie jest rzeczywistym modelem
obliczeń. Niedeterminizm jest kluczowym pojęciem w teorii złożoności,
ponieważ skłania się ku

zastosowaniom obliczeń

, zwłaszcza w logice,

optymalizacji kombinatorycznej i sztucznej inteligencji. Logika zajmuje się
w dużej mierze

dowodami

— podstawowym pojęciem niedeterminizmu. Dla

zdania logicznego można wypróbować wszystkich możliwych dowodów
i uczynić je twierdzeniem,

jeżeli jeden z dowodów będzie poprawny

.

Kordian A. Smoliński (UŁ)

Złożoność obliczeniowa algorytmów

2007/2008

50 / 50