TEORETYCZNE

PODSTAWY

INFORMATYKI

Prowadzący:

ppor. mgr inż. Mariusz

CHMIELEWSKI

e-mail:

mchmiel@isi.wat.waw.pl

Temat 1:

Modele obliczeń – Maszyna

Turinga

ppor. mgr inż. Mariusz CHMIELEWSKI

Maszyna Turinga

Modele  obliczeń  zainicjowane  przez  Alana  M.  Turinga
(1912-1954) pozwalają dokonywać analizy algorytmów
i  problemów  bez  odwoływania  się  do  konkretnej
specyfiki  komputera  uwzględniając  tylko  istotę
obliczeń.

Teza Churcha
Każdy algorytm i dowolny język programowania można
przedstawić jako maszynę Turinga.

Deterministyczna, jednotaśmowa maszyna Turinga (DTM)

ppor. mgr inż. Mariusz CHMIELEWSKI

Model maszyny

Sterowanie

(program)

głowica odczytująco -

zapisująca

taśma o nieskończonej ilości klatek (1
bitowych)

. . .

-4

-3 -2 -1 0 1 2 3

DTM składa się z bloku sterowania,
głowicy odczytująco-zapisującej i
nieskończenie długiej taśmy z
jednobitowymi komórkami.

ppor. mgr inż. Mariusz CHMIELEWSKI

Formalna definicja modelu –

Deterministyczna Maszyna Turinga

Program dla DTM jest dany gdy ustalone są:

1.Skończony zbiór symboli taśmy, podzbiór symboli

wejściowych

oraz wyróżniony symbol pusty ,

1.Skończony zbiór Q stanów maszyny zawierający

wyróżniony stan początkowy q

i dwa stany końcowe: q

dla

odpowiedzi „tak” i q

dla odpowiedzi „nie”.

2.Funkcja przejść

czyli

Σ 

b













1,0,











  







ppor. mgr inż. Mariusz CHMIELEWSKI

Algorytm działania DTM

Łańcuch x(z) danych problem

u z um

ieszcza się początkowo w

klatkach od nr 1 do

 

x ; w pozostałych klatkach znajduje się

początkowo wyróżniony sym

bol pusty.

a) D

rozpoczyna wykonywanie program

u w stanie q

z głowicą

znajdującą się nad klatką nr 1 oraz zgodnie z funkcją przejść h.
b) Program

jest wykonywany do chwili gdy D

znajdzie się w

jednym

ze stanów końcowych tzn. q

lub q

ppor. mgr inż. Mariusz CHMIELEWSKI

Rozwiązywalność problemu

Określenie

Mówimy, że DTM rozwiązuje decyzyjny problem dla
ustalonego kodowania jeśli kończy obliczenia dla wszystkich

łańcuchów danych problemu , przy czym kończy obliczenia w

stanie q

dla wszystkich x(z) takich, że

z

i tylko dla nich.

ppor. mgr inż. Mariusz CHMIELEWSKI

Definicja przykładowej Maszyny

Turinga

Przykład
Zadajmy program DTM do badania czy dana liczba jest parzysta.
1





 

0,1

0,1,







Q 

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .







1,0,0

Krok 1

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .

Krok 2

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .

Krok 3

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .

Krok 4

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .

Krok 5

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Przykład działania

. . .

Krok 6

 





  







  







  







  







  







  































gdy

,1,

gdy

,0,

gdy

,1,

gdy

,0,

ppor. mgr inż. Mariusz CHMIELEWSKI

Diagram przejść stanów DTM

ppor. mgr inż. Mariusz CHMIELEWSKI

Definicja DTM – diagram stanów

ppor. mgr inż. Mariusz CHMIELEWSKI

Konfiguracja maszyny Turinga



Dowolna trójka

ppor. mgr inż. Mariusz CHMIELEWSKI

Konfiguracja DTM - Przykład

Przykład
Zadajmy program DTM obliczający następnik dla liczb binarnych.
1





 

0,1

0,1,







Q

 





  







  







  







  







  







  



























gdy

b,0

gdy

,1,0

gdy

,1,

gdy

,0,

Dla słowa
wejściowego 11011
mamy następującą
konfigurację DTM:

)

111

(

)

110

(

)

1101

(

)

11011

(

)

11011

(

)

11011

(

)

1101

(

)

110

(

)

011

(

)

1011

(





ppor. mgr inż. Mariusz CHMIELEWSKI

)

111

(

)

110

(

)

1101

(

)

11011

(

)

11011

(

)

11011

(

)

1101

(

)

110

(

)

011

(

)

1011

(





Dla słowa
wejściowego 11011
mamy następującą
konfigurację DTM:

Dla słowa
wejściowego 111
mamy następującą
konfigurację DTM:

)

000

(

)

000

(

)

(

)

(

)

111

(

)

111

(

)

111

(

)

(

)

(





ppor. mgr inż. Mariusz CHMIELEWSKI

Teza Churcha-Turinga



Cokolwiek da się obliczyć algorytmicznie, da
się przedstawić jako obliczenie pewnej
maszyny Turinga.

Inaczej mówiąc:



Jeżeli do jakiegoś problemu nie ma
rozwiązującej go maszyny Turinga, to
problem nie jest rozwiązywalny
algorytmicznie.

Ze względu na koncepcyjną prostotę maszyn

Turinga, łatwo jest użyć ich do badania
problemów obliczalności i rozstrzygalności.

ppor. mgr inż. Mariusz CHMIELEWSKI

Definicja Niedeterministycznej

Maszyny Turinga

N D T M j e s t m a s z y n ą n i e r e a l i s t y c z n ą m a j ą c ą z d o l n o ś ć p o w i e l a n i a s i ę w

d o w o l n y m s t a n i e i d o w o l n e j c h w i l i .

P r o g r a m d l a N D T M j e s t z a d a n y g d y z a d a n e s ą :

. S k o ń c z o n y z b i ó r  s y m b o l i t a ś m y , p o d z b i ó r s y m b o l i w e j ś c i o w y c h

Σ 

o r a z w y r ó ż n i o n y s y m b o l p u s t y

b 

. S k o ń c z o n y z b i ó r s t a n ó w m a s z y n y z a w i e r a j ą c y w y r ó ż n i o n y s t a n

p o c z ą t k o w y q

i d w a s t a n y k o ń c o w e : q

i q

. F u n k c j ę p r z e j ś ć

  

 







,...,



( 4 )

g d z i e









Γ,





;





;





0,1,





ppor. mgr inż. Mariusz CHMIELEWSKI

Zasady działania NDTM

O k r e ś le n i e

M ó w im y , ż e N D T M r o z w ią z u j e p r o b le m d e c y z y j n y  w c z a s ie

w ie lo m ia n o w y m j e ś l i d la k a ż d e g o

z 

z o d p o w ie d z i ą „ ta k ”





z 

is t n ie j e s e k w e n c j a w y b o r ó w N D T M ( c i ą g w a r t o ś c i f u n k c j i i p r z e j ś ć ) ,

k t ó r e j d łu g o ś ć j e s t o g r a n ic z o n a o d g ó r y w ie l o m i a n e m z m i e n n e j N ( z ) ,

p r o w a d z ą c a d o s t a n u q

T w ie r d z e n ie

J e ś l i N D T M r o z w ią z u j e d e c y z y j n y p r o b le m  w c z a s ie w ie lo m ia n o w y m
t o is t n i e j e a > 0 i w ie l o m ia n p t a k i, ż e D T M r o z w ią z u j e p r o b le m  w

c z a s ie n ie w ię k s z y m n iż a 2

p ( N ( z ) )

d l a k a ż d e g o

z 

U W A G A

Z w y r a ż e n ia ( 4 ) w y n i k a , i ż d l a k = 2 N D T M p o n k r o k a c h w y t w o r z y 2

s t a n ó w .

S y m u l a c j a t a k ie j m a s z y n y t r w a ł a b y n ie k r ó c e j n iż 2

j e d n o s t e k c z a s u .

Document Outline