złożoność obliczeniowa algorytmu Maszyny Turinga.pdf

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

Deﬁnicja

Maszyna Turinga jest uporz¡dkowan¡ czwórk¡ M = ( K, ,,s ) , gdzie

K — sko«czony zbiór stanów , s 2 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 ) 2 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 2 ( \{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 2 ( \{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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: