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

Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21

Wyszukiwarka

Podobne podstrony:
Maszyna Turinga
Automaty?strakcyjne maszyna Turinga
Maszyna Turinga
MASZYNA TURINGA A UMYSŁ LUDZKI
maszyna Turinga id 281783 Nieznany
3 Maszyna Turinga
Kubity i kot Schrödingera Od maszyny Turinga do komputerów kwantowych
złożoność obliczeniowa algorytmu Maszyny Turinga
3 maszyna turinga
maszyna Turinga przyklady id 28 Nieznany
Maszyna Turinga
Maszyna Turinga,v1 1

więcej podobnych podstron

ćw1 Maszyna turinga

Document Outline