złożoność obliczeniowa algorytmu Maszyny Turinga, Algorytmy i struktury danych
[ Pobierz całość w formacie 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
Podstawy maszyn Turinga
Definicja
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
[ Pobierz całość w formacie PDF ]