[ Pobierz całość w formacie PDF ]
poniższe właściwości:
o zbiorem symboli używanych jest £ = {0,1, b} ,gdzie symbol
b oznacza blanc (pusty)
o zbiór stanów Q jest skończony i zawiera dwa stany
wyróżnione: stan początkowy q0 i stan końcowy q1.
o funkcja przejÅ›cia ´ jest odwzorowaniem zbioru Q × £2 w
zbiór Q × £2 × {L, S, R}2 , gdzie L reprezentuje przejÅ›cie w
lewo, R reprezentuje przejście w prawo, a S brak ruchu
głowicy czytającej.
Wezmy f, p argumentową funkcję częściową oraz M maszynę
Turinga. W tym rozdziale będziemy badali funkcje M obliczalne zdefiniowane
przy pomocy maszyny Turinga, innymi słowy Turing-obliczalne.
Standardowa reprezentacja zmiennych w maszynie jest reprezentacjÄ…
binarną. Od tej chwili będziemy posługiwali się inną notacją, która uprości
demonstrację: zmienna o wartości 0 jest reprezentowana przez 0, natomiast
zmienna n jest reprezentowana przez n pozycji, na których znajdują się
wartości 1.
W rozpatrywanych przez nas maszynach Turniga pierwsza taśma
reprezentuje ciąg danych wejściowych, natomiast druga taśma ciąg będący
rezultatem funkcji reprezentowanej przez maszynÄ™.
VI. 1 Funkcje rekursywne i Turing obliczalne
Na początku udowodnimy, że funkcje bazowe są Turing obliczalne.
o Funkcja stale równa 0 jest obliczalna na następującej
maszynie Turniga:
´(q0, 0, b) = (q0, 0, 0, R, R)
´(q0, 1, b) = (q0, 1, 0, R, R)
´(q0, b, b) = (q1, b, b, S, S)
69
- Grafy i rekurencje -
o Funkcja następnika jest realizowana na maszynie Turniga,
której funkcja przejścia spełnia warunki:
´(q0, 1, b) = (q0, 1, 1, R, R)
´(q0, b, b) = (q1, b, 1, S, S)
o Funkcja projekcji prpi (1 d" i d" p) jest obliczalna na maszynie
posiadającej p+1 stanów q0, q1, q2, ..., qp. Wejściem jest ciąg
wartości oddzielonych symbolem b. Przykładowo, funkcja
pr22 jest obliczalna na 3 stanowej q0, q1, q2 maszynie, której
funkcja przejścia spełnia:
´(q0, 1, b) = (q0, 1, b, R, S)
´(q0, 0, b) = (q0, 0, b, R, S)
´(q0, b, b) = (q2, b, b, R, S)
´(q2, 1, b) = (q2, 1, 1, R, R)
´(q2, 0, b) = (q2, 0, 0, R, R)
´(q2, b, b) = (q1, b, b, S, S)
Pozostaje nam dowieść, że zbiór funkcji częściowych, obliczalnych na
maszynie Turniga jest domknięty przez złożenie, rekurencję prymitywną i
minimalizację. Rezultat ten możemy osiągnąć kolejno utożsamiając maszynę z
każdym procesem konstrukcji funkcji rekursywnej.
VI. 2 Rekursywność funkcji Turing obliczalnych
Poniższe obliczenia zapewniają, że klasa funkcji rekursywnych
częściowych zamyka się razem z klasą funkcji Turnig obliczalnych.
Przedstawiona demonstracja używa kodowania zbioru operacji wykonanych
przez maszynę w trakcie obliczeń.
Wniosek 1:
Każda funkcja częściowa, obliczalna przez maszynę Turniga jest
rekursywna.
70
- Grafy i rekurencje -
Wezmy f, funkcję częściową, obliczalną przy pomocy maszyny Turniga
M, która posiada 2 taśmy i m stanów. Aby pokazać, że funkcja f jest rekursywna
musimy na początku zakodować sytuację maszyny przy pomocy zmiennej
wejściowej t oraz pokazać, że kod jest funkcją rekursywnie prymitywną, zależną
od t i od warunków początkowych. Każdy stan maszyny qi jest kodowany
przez wartość i , symbol pusty (blanc) przez wartość 0, natomiast symbol 0
przez wartość 2.
Definicje:
Konfiguracja maszyny M do danego momentu t jest nieskończonym
ciÄ…giem C(t) = (s0, ..., si, ...) symboli zapisanych do tego momentu przez dwie
taÅ›my maszyny M. CiÄ…g ten jest uzyskany przez konkatenacjÄ™ ciÄ…gów Ã0, Ã1, Ã2,
..., Ãj ..., gdzie dla każdej wartoÅ›ci j , Ãj jest ciÄ…giem symboli zapisanych w
komórkach o numerze j. Ten nieskończony ciąg posiada tylko jedną, skończona
ilość znaków nie pustych.
Sytuacja maszyny do momentu t jest ciÄ…giem (e, k1, k2, C(t)), gdzie e
jest kodem stanu maszyny do momentu t , k1 oraz k2 są numerami komórek,
przed którymi do tego momentu znajdują się głowice czytające, a C(t) jest
konfiguracjÄ… maszyny.
Konfiguracja C(t) może zostać zakodowana przez wartość:
“(C)= £ie"0 si " 3i . Funkcje dzielnika q i reszty z dzielenia r pozwalajÄ… na
odzyskanie z powyższego kodu symboli zapisanych w komórce o numerze u
dla taÅ›my o numerze v : r(q(“(C), 32(u-1)+v-1), 3). Sytuacja maszyny do
momentu t może więc zostać zakodowana przez wartość:
“(S) = "4(e, k1, k2, “(C)).
Na rysunku nr 35 przedstawiony jest sposób kodowania maszyny Turniga.
Zapisana jest uporzÄ…dkowana sekwencja C(t) = 1,0,0,0,0,1,1,1,1,1,0,0, k1=5
k2=2.
1 1 0
0 1
0 1 1 0
1
Rysunek 35 Kodowanie maszyny Turinga
71
- Grafy i rekurencje -
Lemat 1
Istnieje funkcja rekursywnie prymitywna g, która dostarcza kod sytuacji
maszyny do momentu t+1, na podstawie kodu sytuacji maszyny z momentu t.
Dowód:
Przejście zmiennej opisującej w stan następny odbywa się przy pomocy
funkcji przejścia. Funkcja, która pozwala wyrazić konfigurację maszyny do
momentu t+1 przy pomocy konfiguracji do momentu t może być
zdefiniowana w sposób rekursywnie prymitywny w przypadku odnoszącym się
do zbioru definicji funkcji przejścia.
Lemat 2
Funkcja Sit , która dostarcza kod sytuacji maszyny do momentu t na
podstawie poczÄ…tkowej konfiguracji danych jest rekursywnie prymitywna.
Dowód:
Funkcja Sit jest zdefiniowana przez rekurencję. Jej wartość do
momentu t = 0 jest uzyskiwana w sposób rekursywnie prymitywny począwszy
od konfiguracji początkowej. Przejście od momentu t do momentu t+1 jest
realizowane przy pomocy funkcji g.
W dalszej części identyfikujemy kod związany z Sit(t,x1, x2, ..., xp) oraz
czteroelementową sekwencję (e, k1, k2, C(t)). W szczególności
À41(Sit(t,x1, x2, ..., xp)) jest stanem e . Demonstracja powyższej wÅ‚asnoÅ›ci jest
stosunkowo prosta.
Dowód:
Czas obliczania wartości f(x1, x2, ..., xp) jest zadany przez:
T(x1, x2, ..., xp) = µt ( À41(Sit(t,x1, x2, ..., xp)) = 1 ),
gdyż maszyna osiąga tylko jeden stan końcowy q1.
Znając sytuację do momentu T(x1, x2, ..., xp) możliwe jest zliczenie ilości
wystąpień symbolu 1 na drugiej taśmie, która jest równa wartości f(x1, x2,..., xp):
f(x1, x2,..., xp) = µy(r(q(À44(Sit(T(x1, x2, ..., xp), x1, ..., xp)), 32y+1), 3) = 0)
Ta ostatnia funkcja oblicza przy pomocy funkcji q (dzielnika) i r (reszty)
ilość 1 na drugiej taśmie.
72
- Grafy i rekurencje -
VI. 3 Abstrakcja funkcjonalna
Jakakolwiek byłaby dziedzina aplikacji, użytkowanie komputera
sprowadza się za każdym razem do obliczania wartości funkcji. W
rzeczywistości dane na wejściu są kodowane do postaci ciągu bitów
interpretowanych jako sekwencje wejściowe, a na wyjściu rezultaty ponownie są
kodowane i interpretowane. Etapy pośrednie realizują wszystkie istotne
obliczenia.
Taka interpretacja oznacza proces arytmetyzacji, który jest szeroko
używany w realizacji procesów modelowania i symulacji. Przepływ danych
ilustruje rysunek nr 36.
System
Arytmetyzacja
p
Stan poczÄ…tkowy
N
Zdarzenia
Operacje
Stan końcowy
N
Rysunek 36 Proces arytmetyzacji
Powyższy schemat pokazuje wagę jaką kładzie się na analizowanie w
informatyce funkcji, w szczególności z przestrzeni Np w N. Rozpatrując te
ostatnie, matematycy i programiści wiedzą, że mogą one być stworzone przy
wykorzystaniu zaledwie kilku funkcji prymitywnych. Przyjrzymy siÄ™ teraz
niektórym procedurom konstrukcji, które pomogą nam zrozumieć matematykę
algorytmicznÄ….
Przypomnijmy, że funkcja jest regułą wiążącą obiekty, która pozwala
określić wartość dla każdego zadanego jej argumentu dziedziny. Użyteczne jest
zdefiniowanie tej reguły przez wyrażenie zależności pomiędzy argumentem i
jego wartoÅ›ciÄ…. Rozumiemy przez to, np. przypisanie x’!x2 lub f: x ’! f(x) ,
gdzie f jest właściwym oznaczeniem reguły.
73
- Grafy i rekurencje - [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl freetocraft.keep.pl
poniższe właściwości:
o zbiorem symboli używanych jest £ = {0,1, b} ,gdzie symbol
b oznacza blanc (pusty)
o zbiór stanów Q jest skończony i zawiera dwa stany
wyróżnione: stan początkowy q0 i stan końcowy q1.
o funkcja przejÅ›cia ´ jest odwzorowaniem zbioru Q × £2 w
zbiór Q × £2 × {L, S, R}2 , gdzie L reprezentuje przejÅ›cie w
lewo, R reprezentuje przejście w prawo, a S brak ruchu
głowicy czytającej.
Wezmy f, p argumentową funkcję częściową oraz M maszynę
Turinga. W tym rozdziale będziemy badali funkcje M obliczalne zdefiniowane
przy pomocy maszyny Turinga, innymi słowy Turing-obliczalne.
Standardowa reprezentacja zmiennych w maszynie jest reprezentacjÄ…
binarną. Od tej chwili będziemy posługiwali się inną notacją, która uprości
demonstrację: zmienna o wartości 0 jest reprezentowana przez 0, natomiast
zmienna n jest reprezentowana przez n pozycji, na których znajdują się
wartości 1.
W rozpatrywanych przez nas maszynach Turniga pierwsza taśma
reprezentuje ciąg danych wejściowych, natomiast druga taśma ciąg będący
rezultatem funkcji reprezentowanej przez maszynÄ™.
VI. 1 Funkcje rekursywne i Turing obliczalne
Na początku udowodnimy, że funkcje bazowe są Turing obliczalne.
o Funkcja stale równa 0 jest obliczalna na następującej
maszynie Turniga:
´(q0, 0, b) = (q0, 0, 0, R, R)
´(q0, 1, b) = (q0, 1, 0, R, R)
´(q0, b, b) = (q1, b, b, S, S)
69
- Grafy i rekurencje -
o Funkcja następnika jest realizowana na maszynie Turniga,
której funkcja przejścia spełnia warunki:
´(q0, 1, b) = (q0, 1, 1, R, R)
´(q0, b, b) = (q1, b, 1, S, S)
o Funkcja projekcji prpi (1 d" i d" p) jest obliczalna na maszynie
posiadającej p+1 stanów q0, q1, q2, ..., qp. Wejściem jest ciąg
wartości oddzielonych symbolem b. Przykładowo, funkcja
pr22 jest obliczalna na 3 stanowej q0, q1, q2 maszynie, której
funkcja przejścia spełnia:
´(q0, 1, b) = (q0, 1, b, R, S)
´(q0, 0, b) = (q0, 0, b, R, S)
´(q0, b, b) = (q2, b, b, R, S)
´(q2, 1, b) = (q2, 1, 1, R, R)
´(q2, 0, b) = (q2, 0, 0, R, R)
´(q2, b, b) = (q1, b, b, S, S)
Pozostaje nam dowieść, że zbiór funkcji częściowych, obliczalnych na
maszynie Turniga jest domknięty przez złożenie, rekurencję prymitywną i
minimalizację. Rezultat ten możemy osiągnąć kolejno utożsamiając maszynę z
każdym procesem konstrukcji funkcji rekursywnej.
VI. 2 Rekursywność funkcji Turing obliczalnych
Poniższe obliczenia zapewniają, że klasa funkcji rekursywnych
częściowych zamyka się razem z klasą funkcji Turnig obliczalnych.
Przedstawiona demonstracja używa kodowania zbioru operacji wykonanych
przez maszynę w trakcie obliczeń.
Wniosek 1:
Każda funkcja częściowa, obliczalna przez maszynę Turniga jest
rekursywna.
70
- Grafy i rekurencje -
Wezmy f, funkcję częściową, obliczalną przy pomocy maszyny Turniga
M, która posiada 2 taśmy i m stanów. Aby pokazać, że funkcja f jest rekursywna
musimy na początku zakodować sytuację maszyny przy pomocy zmiennej
wejściowej t oraz pokazać, że kod jest funkcją rekursywnie prymitywną, zależną
od t i od warunków początkowych. Każdy stan maszyny qi jest kodowany
przez wartość i , symbol pusty (blanc) przez wartość 0, natomiast symbol 0
przez wartość 2.
Definicje:
Konfiguracja maszyny M do danego momentu t jest nieskończonym
ciÄ…giem C(t) = (s0, ..., si, ...) symboli zapisanych do tego momentu przez dwie
taÅ›my maszyny M. CiÄ…g ten jest uzyskany przez konkatenacjÄ™ ciÄ…gów Ã0, Ã1, Ã2,
..., Ãj ..., gdzie dla każdej wartoÅ›ci j , Ãj jest ciÄ…giem symboli zapisanych w
komórkach o numerze j. Ten nieskończony ciąg posiada tylko jedną, skończona
ilość znaków nie pustych.
Sytuacja maszyny do momentu t jest ciÄ…giem (e, k1, k2, C(t)), gdzie e
jest kodem stanu maszyny do momentu t , k1 oraz k2 są numerami komórek,
przed którymi do tego momentu znajdują się głowice czytające, a C(t) jest
konfiguracjÄ… maszyny.
Konfiguracja C(t) może zostać zakodowana przez wartość:
“(C)= £ie"0 si " 3i . Funkcje dzielnika q i reszty z dzielenia r pozwalajÄ… na
odzyskanie z powyższego kodu symboli zapisanych w komórce o numerze u
dla taÅ›my o numerze v : r(q(“(C), 32(u-1)+v-1), 3). Sytuacja maszyny do
momentu t może więc zostać zakodowana przez wartość:
“(S) = "4(e, k1, k2, “(C)).
Na rysunku nr 35 przedstawiony jest sposób kodowania maszyny Turniga.
Zapisana jest uporzÄ…dkowana sekwencja C(t) = 1,0,0,0,0,1,1,1,1,1,0,0, k1=5
k2=2.
1 1 0
0 1
0 1 1 0
1
Rysunek 35 Kodowanie maszyny Turinga
71
- Grafy i rekurencje -
Lemat 1
Istnieje funkcja rekursywnie prymitywna g, która dostarcza kod sytuacji
maszyny do momentu t+1, na podstawie kodu sytuacji maszyny z momentu t.
Dowód:
Przejście zmiennej opisującej w stan następny odbywa się przy pomocy
funkcji przejścia. Funkcja, która pozwala wyrazić konfigurację maszyny do
momentu t+1 przy pomocy konfiguracji do momentu t może być
zdefiniowana w sposób rekursywnie prymitywny w przypadku odnoszącym się
do zbioru definicji funkcji przejścia.
Lemat 2
Funkcja Sit , która dostarcza kod sytuacji maszyny do momentu t na
podstawie poczÄ…tkowej konfiguracji danych jest rekursywnie prymitywna.
Dowód:
Funkcja Sit jest zdefiniowana przez rekurencję. Jej wartość do
momentu t = 0 jest uzyskiwana w sposób rekursywnie prymitywny począwszy
od konfiguracji początkowej. Przejście od momentu t do momentu t+1 jest
realizowane przy pomocy funkcji g.
W dalszej części identyfikujemy kod związany z Sit(t,x1, x2, ..., xp) oraz
czteroelementową sekwencję (e, k1, k2, C(t)). W szczególności
À41(Sit(t,x1, x2, ..., xp)) jest stanem e . Demonstracja powyższej wÅ‚asnoÅ›ci jest
stosunkowo prosta.
Dowód:
Czas obliczania wartości f(x1, x2, ..., xp) jest zadany przez:
T(x1, x2, ..., xp) = µt ( À41(Sit(t,x1, x2, ..., xp)) = 1 ),
gdyż maszyna osiąga tylko jeden stan końcowy q1.
Znając sytuację do momentu T(x1, x2, ..., xp) możliwe jest zliczenie ilości
wystąpień symbolu 1 na drugiej taśmie, która jest równa wartości f(x1, x2,..., xp):
f(x1, x2,..., xp) = µy(r(q(À44(Sit(T(x1, x2, ..., xp), x1, ..., xp)), 32y+1), 3) = 0)
Ta ostatnia funkcja oblicza przy pomocy funkcji q (dzielnika) i r (reszty)
ilość 1 na drugiej taśmie.
72
- Grafy i rekurencje -
VI. 3 Abstrakcja funkcjonalna
Jakakolwiek byłaby dziedzina aplikacji, użytkowanie komputera
sprowadza się za każdym razem do obliczania wartości funkcji. W
rzeczywistości dane na wejściu są kodowane do postaci ciągu bitów
interpretowanych jako sekwencje wejściowe, a na wyjściu rezultaty ponownie są
kodowane i interpretowane. Etapy pośrednie realizują wszystkie istotne
obliczenia.
Taka interpretacja oznacza proces arytmetyzacji, który jest szeroko
używany w realizacji procesów modelowania i symulacji. Przepływ danych
ilustruje rysunek nr 36.
System
Arytmetyzacja
p
Stan poczÄ…tkowy
N
Zdarzenia
Operacje
Stan końcowy
N
Rysunek 36 Proces arytmetyzacji
Powyższy schemat pokazuje wagę jaką kładzie się na analizowanie w
informatyce funkcji, w szczególności z przestrzeni Np w N. Rozpatrując te
ostatnie, matematycy i programiści wiedzą, że mogą one być stworzone przy
wykorzystaniu zaledwie kilku funkcji prymitywnych. Przyjrzymy siÄ™ teraz
niektórym procedurom konstrukcji, które pomogą nam zrozumieć matematykę
algorytmicznÄ….
Przypomnijmy, że funkcja jest regułą wiążącą obiekty, która pozwala
określić wartość dla każdego zadanego jej argumentu dziedziny. Użyteczne jest
zdefiniowanie tej reguły przez wyrażenie zależności pomiędzy argumentem i
jego wartoÅ›ciÄ…. Rozumiemy przez to, np. przypisanie x’!x2 lub f: x ’! f(x) ,
gdzie f jest właściwym oznaczeniem reguły.
73
- Grafy i rekurencje - [ Pobierz całość w formacie PDF ]