Algorytmy

Cz¦±¢ III

wer. 1.2

Wojciech Myszka

23 listopada 2008

Upraszczanie danych

I

Komputery s¡ coraz szybsze i sprawniejsze.

I

Na potrzeby rozwa»a« naukowych

potrzebne s¡

modele uogólniaj¡ce i jak najprostsze. . .

I

Struktura pami¦ci komputera jest bardzo prosta
liniowa

Upraszczanie danych

I

Zmienne i wektory

bardzo ªatwo daj¡ si¦ zlinearyzowa¢

I

Tablice dwu (ale i wielowymiarowe) stosunkowo ªatwo
mo»na zapisa¢ w taki sposób: trzeba si¦ tylko umówi¢ czy
zapisujemy dane wierszami czy kolumnami

Przykªad

11 12 13
21 22 23
31 32 33
41 42 43

mo»e by¢ zapisane tak: 11; 12; 13 * 21; 22; 23 * 31; 32; 33 * 41;
42; 43 *
albo tak: 11; 21; 31; 41 * 12; 22; 32; 42 * 13; 23; 33; 43 *
albo tak: {{11, 21, 31, 41}, {12, 22, 32, 42}, {13, 23, 33}} czyli
jako lista!

Upraszczanie danych

I

Zmienne i wektory

bardzo ªatwo daj¡ si¦ zlinearyzowa¢

I

Tablice dwu (ale i wielowymiarowe) stosunkowo ªatwo
mo»na zapisa¢ w taki sposób: trzeba si¦ tylko umówi¢ czy
zapisujemy dane wierszami czy kolumnami

Przykªad

11 12 13
21 22 23
31 32 33
41 42 43

mo»e by¢ zapisane tak: 11; 12; 13 * 21; 22; 23 * 31; 32; 33 * 41;
42; 43 *
albo tak: 11; 21; 31; 41 * 12; 22; 32; 42 * 13; 23; 33; 43 *
albo tak: {{11, 21, 31, 41}, {12, 22, 32, 42}, {13, 23, 33}} czyli
jako lista!

Upraszczanie danych

I

Zmienne i wektory

bardzo ªatwo daj¡ si¦ zlinearyzowa¢

I

Tablice dwu (ale i wielowymiarowe) stosunkowo ªatwo
mo»na zapisa¢ w taki sposób: trzeba si¦ tylko umówi¢ czy
zapisujemy dane wierszami czy kolumnami

Przykªad

11 12 13
21 22 23
31 32 33
41 42 43

mo»e by¢ zapisane tak: 11; 12; 13 * 21; 22; 23 * 31; 32; 33 * 41;
42; 43 *

albo tak: 11; 21; 31; 41 * 12; 22; 32; 42 * 13; 23; 33; 43 *
albo tak: {{11, 21, 31, 41}, {12, 22, 32, 42}, {13, 23, 33}} czyli
jako lista!

Upraszczanie danych

I

Zmienne i wektory

bardzo ªatwo daj¡ si¦ zlinearyzowa¢

I

Tablice dwu (ale i wielowymiarowe) stosunkowo ªatwo
mo»na zapisa¢ w taki sposób: trzeba si¦ tylko umówi¢ czy
zapisujemy dane wierszami czy kolumnami

Przykªad

11 12 13
21 22 23
31 32 33
41 42 43

mo»e by¢ zapisane tak: 11; 12; 13 * 21; 22; 23 * 31; 32; 33 * 41;
42; 43 *
albo tak: 11; 21; 31; 41 * 12; 22; 32; 42 * 13; 23; 33; 43 *

albo tak: {{11, 21, 31, 41}, {12, 22, 32, 42}, {13, 23, 33}} czyli
jako lista!

Upraszczanie danych

I

Zmienne i wektory

bardzo ªatwo daj¡ si¦ zlinearyzowa¢

I

Tablice dwu (ale i wielowymiarowe) stosunkowo ªatwo
mo»na zapisa¢ w taki sposób: trzeba si¦ tylko umówi¢ czy
zapisujemy dane wierszami czy kolumnami

Przykªad

11 12 13
21 22 23
31 32 33
41 42 43

mo»e by¢ zapisane tak: 11; 12; 13 * 21; 22; 23 * 31; 32; 33 * 41;
42; 43 *
albo tak: 11; 21; 31; 41 * 12; 22; 32; 42 * 13; 23; 33; 43 *
albo tak: {{11, 21, 31, 41}, {12, 22, 32, 42}, {13, 23, 33}} czyli
jako lista!

Upraszczanie danych

I

Podobnie b¦dzie i ze stosem i z kolejk¡

I

Baza danych

to wªa±ciwie tak bardziej rozbudowana

tablica; ale nie znaczy »e b¦dzie ªatwo. . .

I

Co z drzewem?

T

V

Q

R

M

N

S

G

W

P

L

Upraszczanie danych

T

V

Q

R

M

N

S

G

W

P

L

Pokazane drzewo
mo»na próbowa¢
zapisa¢ tak:
T ** V; G ** Q; R; S;
W; L ** M; N; P**
(gwiazdki
oznaczaj¡ tu
koniec kolejnych

poziomów

drzewa). Ale jedno
co mo»na
odtworzy¢ to...

T

V

Q

R

M

N

S

G

W

P

L

Upraszczanie danych

T

V

Q

R

M

N

S

G

W

P

L

Pokazane drzewo
mo»na próbowa¢
zapisa¢ tak:
T ** V; G ** Q; R; S;
W; L ** M; N; P**
(gwiazdki
oznaczaj¡ tu
koniec kolejnych

poziomów

drzewa). Ale jedno
co mo»na
odtworzy¢ to...

T

V

Q

R

M

N

S

G

W

P

L

Upraszczanie danych

T

V

Q

R

M

N

S

G

W

P

L

Je»eli jednak troch¦ zapis
skomplikowa¢ to mo»na uzyska¢ co±
wi¦cej:
(T) (V; G) (Q; R; S) (W; L) () (M; N) ()
(P) ()
powy»szy zapis jest bardzo zwarty,
ale te» troch¦ skomplikowany:
nawiasy grupuj¡ tylko w¦zªy b¦d¡ce
potomkami tego samego w¦zªa.
Poziomy drzewa nie s¡ zaznaczane
w »aden specjalny sposób i musz¡
by¢ wyliczane.
Uwaga: jest to zapis listowy!

Upraszczanie danych

teza

Przyjmujemy, »e ka»d¡ struktur¦ danych mo»na zapisa¢
w postaci liniowej, na przykªad na odpowiednio dªugiej

ta±mie zªo»onej z krateczek w których zapisane s¡

pojedyncze dane.

Upraszczanie programu

I

Czym jest program (algorytm) komputerowy?

rodzaj struktury steruj¡cej okre±laj¡cej w jaki sposób
i w jakiej kolejno±ci przetwarzane s¡ dane wej±ciowe

I

Ka»dy algorytm jest sko«czony

I

Przej±cia pomi¦dzy instrukcjami (albo blokami algorytmu)
odbywaj¡ si¦ albo sekwencyjnie albo s¡ sterowane danymi
(wewn¦trznymi albo zewn¦trznymi)

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

Upraszczanie programu

I

Czym jest program (algorytm) komputerowy?
rodzaj struktury steruj¡cej okre±laj¡cej w jaki sposób
i w jakiej kolejno±ci przetwarzane s¡ dane wej±ciowe

I

Ka»dy algorytm jest sko«czony

I

Przej±cia pomi¦dzy instrukcjami (albo blokami algorytmu)
odbywaj¡ si¦ albo sekwencyjnie albo s¡ sterowane danymi
(wewn¦trznymi albo zewn¦trznymi)

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

Upraszczanie programu

I

Czym jest program (algorytm) komputerowy?
rodzaj struktury steruj¡cej okre±laj¡cej w jaki sposób
i w jakiej kolejno±ci przetwarzane s¡ dane wej±ciowe

I

Ka»dy algorytm jest sko«czony

I

Przej±cia pomi¦dzy instrukcjami (albo blokami algorytmu)
odbywaj¡ si¦ albo sekwencyjnie albo s¡ sterowane danymi
(wewn¦trznymi albo zewn¦trznymi)

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

Upraszczanie programu

I

Czym jest program (algorytm) komputerowy?
rodzaj struktury steruj¡cej okre±laj¡cej w jaki sposób
i w jakiej kolejno±ci przetwarzane s¡ dane wej±ciowe

I

Ka»dy algorytm jest sko«czony

I

Przej±cia pomi¦dzy instrukcjami (albo blokami algorytmu)
odbywaj¡ si¦ albo sekwencyjnie albo s¡ sterowane danymi
(wewn¦trznymi albo zewn¦trznymi)

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

Upraszczanie programu

I

Czym jest program (algorytm) komputerowy?
rodzaj struktury steruj¡cej okre±laj¡cej w jaki sposób
i w jakiej kolejno±ci przetwarzane s¡ dane wej±ciowe

I

Ka»dy algorytm jest sko«czony

I

Przej±cia pomi¦dzy instrukcjami (albo blokami algorytmu)
odbywaj¡ si¦ albo sekwencyjnie albo s¡ sterowane danymi
(wewn¦trznymi albo zewn¦trznymi)

Start

Znajdo-

wanie
reszty

Czy zero?

Stop

Uprasz-

czanie

Upraszczanie programów

teza

W pewnym uproszczeniu mo»emy na program (algorytm)
komputerowy popatrzy¢ jak na rodzaj skrzyni biegów :
urz¡dzenia posiadaj¡cego jedynie sko«czon¡ liczb¦
stanów.
Ka»dy program mo»na zapisa¢ w postaci zestawu stanów
i odpowiednich przej±¢ mi¦dzy nimi (sterowanych
danymi).

Maszyna Turinga

Maszyna Turinga skªada si¦ z:

1.

sko«czonego alfabetu symboli;

2.

sko«czonego zbioru stanów z wyró»nionymi stanami
ko«cowymi (po osi¡gni¦ciu których maszyna zatrzymuje
si¦);

3.

niesko«czonej ta±my z zaznaczonymi kwadratami,
z których ka»dy mo»e zawiera¢ pojedynczy symbol;

4.

ruchomej gªowicy odczytuj¡co-zapisuj¡cej, która mo»e
w¦drowa¢ wzdªu» ta±my przesuwaj¡c si¦ o jeden kwadrat
na raz;

5.

diagramu przej±¢ mi¦dzy stanami (zazwyczaj zwanego
diagramem przej±¢ po prostu) zawieraj¡cego instrukcje,
które powoduj¡, »e zmiany nast¦puj¡ przy ka»dym
zatrzymaniu si¦.

Maszyna Turinga

Opis formalny

Hopcroft i Ullman zde niowali formalnie maszyn¡ Turinga jako
nast¦puj¡c¡ siódemk¦ (7-tuple): M = hQ, Γ, b, Σ, δ, q

0

,

Fi

gdzie:

I

Q to sko«czny zbiór stanów,

I

Γ

to sko«czony zbiór symboli alfabetu

I

b ∈ Γ jest symbolem pustym

I

Σ ⊆ Γ \ {

b} to zbiór symboli wej±ciowych

I

δ :

Q × Γ → Q × Γ × {L, R} jest funkcj¡ przej±cia , L

onacza przesuni¦cie w lewo, a R przesuni¦cie w prawo.

I

q

0

∈

Q To stan pocz¡tkowy

I

F ⊆ Q jest zbiorem stanów ko«cowych

Ka»dy obiekt speªniaj¡cy powy»sze zaªo»enia nazywany
by¢ mo»e maszyn¡ Turinga.

Maszyna Turinga

Diagram przej±¢

Diagram przej±¢ to graf skierowany, którego wierzchoªki
reprezentuj¡ stany.
Kraw¦d¹ prowadz¡c¡ ze stanu s do t nazywa si¦
przej±ciem i etykietuje kodem postaci: a/b, kierunek;
gdzie a i b s¡ symbolami (alfabetu), a kierunek to albo

w prawo albo w lewo (R, L).

Cz¦±¢ a jest wyzwalaczem

1

przej±cia, a cz¦±¢ b, kierunek

akcj¡.

2

1

. . . je»eli na ta±mie spotkasz a. . .

2

. . . to zapisz w kratce b i przesu« si¦ w kierunku. . .

Przykªadowa maszyna Turinga

I

Alfabet

trzy symbole: a, b i # (co oznacza symbol

pusty, nic )

I

Dane

. . .

# # a b b a # # . . .

Przykªadowa maszyna Turinga

Diagram przej±¢, stany

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Stany ko«cowe to stany opisane jako TAK i NIE

Maszyna Turinga

Przykªad (1)

. . .

# # a b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # b b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # b # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # # # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # # # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (1)

. . .

# # # # # # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # a b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (2)

. . .

# # # b a b # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # a b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a a # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # b a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # # a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # # a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # # a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Przykªad (3)

. . .

# # # # a # # # . . .

•

zaznacz

start

ruchA

testA

ruchB

testB

TAK

NIE

powrot

a,#,P

b,#,P

#,#,L

#,#,L

(a,a,P) (b,b,P)

a,#,L

#,#,L

b,b,L

#,#,L

(a,a,P) (b,b,P)

b,#,L

#,#,L

a,a,L

(a,a,L) (b,b,L)

#,#,P

Maszyna Turinga

Warianty

I

Ta±ma jednostronnie niesko«czona (ma pocz¡tek,
nie ma ko«ca).

I

Dwie ta±my ( wej±ciowa i wyj±ciowa ).

I

Ta±ma dwuwymiarowa.

I

Maszyna niedeterministyczna (w wariancie
deterministycznym okre±lony wyzwalacz w danym
stanie powoduje zawsze tak¡ sam¡ reakcj¦;
w wariancie niedeterministycznym dopuszcza si¦ dla
jednego wyzwalacza kilka ró»nych akcji wybieranych
losowo).

Maszyna Turinga

Warianty

Wszystkie tak zmody kowane maszyny Turinga

s¡ sobie równowa»ne!

(to znaczy ka»dy problem,

który mo»na rozwi¡za¢ na jednej z nich mo»na rozwi¡za¢
na ka»dej innej; albo inaczej: ka»da z tych maszyn mo»e
emulowa¢ ka»d¡ inn¡).
Pokazano, »e komputer zaprojektowany przez Babbage'a

maszyna analityczna

jest równowa»ny z maszyn¡

Turinga.

Maszyna Turinga

Warianty

Wszystkie tak zmody kowane maszyny Turinga

s¡ sobie równowa»ne!

(to znaczy ka»dy problem,

który mo»na rozwi¡za¢ na jednej z nich mo»na rozwi¡za¢
na ka»dej innej; albo inaczej: ka»da z tych maszyn mo»e
emulowa¢ ka»d¡ inn¡).

Pokazano, »e komputer zaprojektowany przez Babbage'a

maszyna analityczna

jest równowa»ny z maszyn¡

Turinga.

Maszyna Turinga

Warianty

Wszystkie tak zmody kowane maszyny Turinga

s¡ sobie równowa»ne!

(to znaczy ka»dy problem,

który mo»na rozwi¡za¢ na jednej z nich mo»na rozwi¡za¢
na ka»dej innej; albo inaczej: ka»da z tych maszyn mo»e
emulowa¢ ka»d¡ inn¡).
Pokazano, »e komputer zaprojektowany przez Babbage'a

maszyna analityczna

jest równowa»ny z maszyn¡

Turinga.

Maszyna Turinga

Do czego sªu»y

1.

Maszyna Turinga ma tylko sko«czon¡ liczb¦ stanów.

2.

Programowanie jej nie musi by¢ ªatwe (spróbujcie
skonstruowa¢ maszyn¡ mno»¡c¡ liczby!)

3.

Jej dziaªanie zapewne b¦dzie bardzo powolne, a sama
symulacja (r¦czna) jest dosy¢ nu»¡ca.

4.

Ale co tak na prawd¦ maszyna Turinga mo»e zrobi¢?

Teza Churcha-Turinga

Ka»dy problem algorytmiczny, dla którego mo»emy
znale¹¢ algorytm daj¡cy si¦ zaprogramowa¢ w pewnym
dowolnym j¦zyku, wykonuj¡cy si¦ na pewnym, dowolnym
komputerze, nawet na takim, którego jeszcze nie
zbudowano, ale mo»na zbudowa¢, i nawet na takim, który
wymaga nieograniczonej ilo±ci czasu i pami¦ci dla coraz
wi¦kszych danych, jest

tak»e rozwi¡zywalny przez

maszyn¦ Turinga

.

Uwaga!

Jest to TYLKO teza, nie twierdzenie!
Powy»sze sformuªowanie jest jednym z wielu!

Teza Churcha-Turinga

Ka»dy problem algorytmiczny, dla którego mo»emy
znale¹¢ algorytm daj¡cy si¦ zaprogramowa¢ w pewnym
dowolnym j¦zyku, wykonuj¡cy si¦ na pewnym, dowolnym
komputerze, nawet na takim, którego jeszcze nie
zbudowano, ale mo»na zbudowa¢, i nawet na takim, który
wymaga nieograniczonej ilo±ci czasu i pami¦ci dla coraz
wi¦kszych danych, jest

tak»e rozwi¡zywalny przez

maszyn¦ Turinga

.

Uwaga!

Jest to TYLKO teza, nie twierdzenie!
Powy»sze sformuªowanie jest jednym z wielu!

Konsekwencje tezy Churcha-Turinga

1.

Domowy komputer jest równowa»ny

superkomputerowi z wielkiego centrum
obliczeniowego (co nie znaczy, »e rozwi¡»e ten sam
problem w tym samym czasie!)

2.

Wszystkie j¦zyki programowania s¡ sobie równowa»ne
(to znaczy to co mo»na zaprogramowa¢ w jednym
mo»na w ka»dym innym)

3.

. . .

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.
Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.
Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.
Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.
Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.

Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Dopuszcza si¦ jedynie trzy typy elementarnych operacji:

I

X ← 0,

I

X ← Y + 1,

I

X ← Y − 1 (zakªadamy, »e je»eli Y jest ju» równe 0 to
Y − 1 równie» jest zero.

I

Z instrukcji steruj¡cych dopuszczamy tylko skok
warunkowy: je±li X = 0 skocz-do L

Takie zmienne, których warto±¢ mo»e si¦ zmienia¢ o plus
lub minus jeden nazywamy licznikami.
Zwracam uwag¦, »e powy»szy model jest znacznie bli»szy
modelowi komputera zaproponowanemu przez von
Neumanna ni» maszyna Turinga!

Programy licznikowe

Przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

W powy»szym X i Y to dane wej±ciowe, Z

dana

wyj±ciowa; nieistniej¡ca etykieta L

koniec programu

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0

Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

2 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0

Z ← 0

A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

2 3

0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0

A: je±li X = 0 skocz-do L

X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

2 3

0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L

X ← X − 1

V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3

0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1

V ← Y + 1

V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 4 0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1

V ← V − 1

B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 3 0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 3 0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 2 0

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 2 1

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 2 1

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 2 1

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 1 1

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 1 2

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 1 2

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 1 2

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 0 2

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 0 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

1 3 0 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 0 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0

A: je±li X = 0 skocz-do L

X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

1 3 0 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L

X ← X − 1

V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 0 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1

V ← Y + 1

V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 4 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1

V ← V − 1

B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 3 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 3 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 2 3

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 2 4

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 2 4

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 2 4

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 1 4

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 1 5

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 1 5

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 1 5

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A

V ← V − 1

Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 0 5

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1

Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 0 6

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1

je±li U = 0 skocz-do B

X Y V Z

0 3 0 6

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1

B: je±li V = 0 skocz-do A

V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 0 6

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0

A: je±li X = 0 skocz-do L

X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 0 6

Programy licznikowe

Dziaªaj¡cy przykªad

U ← 0
Z ← 0
A: je±li X = 0 skocz-do L
X ← X − 1
V ← Y + 1
V ← V − 1
B: je±li V = 0 skocz-do A
V ← V − 1
Z ← Z + 1
je±li U = 0 skocz-do B

X Y V Z

0 3 0 6

KONIEC

Programy licznikowe

Mo»na pokaza¢, »e program licznikowy mo»e symulowa¢
dziaªanie maszyny Turinga oraz, »e maszyna Turinga mo»e
zasymulowa¢ program licznikowy.

Program licznikowy jest tak samo dobry jak Maszyna
Turinga i jak ka»dy inny komputer (z dokªadno±ci¡ do
czasu i przestrzeni).

Programy licznikowe

Mo»na pokaza¢, »e program licznikowy mo»e symulowa¢
dziaªanie maszyny Turinga oraz, »e maszyna Turinga mo»e
zasymulowa¢ program licznikowy.
Program licznikowy jest tak samo dobry jak Maszyna
Turinga i jak ka»dy inny komputer (z dokªadno±ci¡ do
czasu i przestrzeni).

Automaty sko«czone

Dla dociekliwych:
Deterministyczny automat sko«czony mo»e zosta¢
jednoznacznie opisany przez przez pi¡tk¦ (A, Q, q

0

,

F, d), gdzie

1.

A jest alfabetem

2.

Q jest zbiorem stanów

3.

q

0

jest wyró»nionym stanem pocz¡tkowym nale»¡cym do Q

4.

F jest zbiorem stanów akceptuj¡cych (ko«cowych),
b¦d¡cym podzbiorem Q

5.

d jest funkcj¡ przej±cia, przypisuj¡c¡ parze (q, a) nowy stan
p, w którym znajdzie si¦ automat po przeczytaniu symbolu
a w stanie q.

Prosz¦ porówna¢ powy»sz¡ de nicj¦ z de nicj¡ maszyny Turinga!