Poszukiwanie prostej i uniwersalnej maszyny obliczeniowej Przykład tablicy dwuwymiarowej
Algorytm = operacje elementarne + struktury sterujące
7 45 -3
Program obliczeniowy =
91 0 12
= język programowania + algorytm + struktury danych
-15 11 17
Maszyna obliczeniowa (MO) =
= model pamięci + zapis sterowania + zestaw operacji elementarnych
Jak dalece można uprościć model pamięci, aby można było tworzyć
# 7 45 -3 " 91 0 12 " -15 11 17 #
różne struktury danych?
Czy pamięć MO mogłaby być jednowymiarową  taśmą podzieloną
Strukturę tablicy można zapisać na jednowymiarowej taśmie
na komórki?
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 1 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 2
Przykład drzewa ukorzenionego
Każdą strukturę danych da się zlinearyzować,
I
tzn. zapisać na jednowymiarowej taśmie
N F O
W MO przyjmujemy najprostszy model pamięci:
R M A T
# # # #
Y K A
pamięcią MO jest nieskończoną jednowymiarową taśmą
podzieloną na komórki,
# I " N F O " R M A T " Y K A #
pojedyncza komórka może przechowywać jeden znak z
przyjętego alfabetu symboli,
lub lepiej
puste komórki wypełnione są umownym symbolem #
( I ) ( N F O ) ( R M ) ( A ) ( T ) ( ) ( Y ) ( ) ( K A )
Strukturę drzewa można zapisać na jednowymiarowej taśmie
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 3 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 4
symbole
Jak dalece można uprościć zapis sterowania, tak aby można alfabetu
było realizować różne algorytmy?
stan a
aktualny
Sterowanie powinno wskazywać kolejność wykonywania
możliwe
b
operacji w procesie wyznaczania wyniku wg przyjętego następne
c stany
algorytmu (w każdym momencie może być wykonywana co
najwyżej jedna operacja)
wszystkie stany, które mogą pojawić się przy realizacji danego
znajdowanie się w określonym miejscu procesu realizacji
algorytmu są zaznaczane jako węzły na tzw. diagramie przejść
algorytmu nazwiemy stanem procesu,
międzystanowych
stan początkowy symbolizuje rozpoczęcie realizacji algorytmu
dla każdego stanu na diagramie, zbiór następnych stanów wynika
(start), a stan końcowy jego zatrzymanie (stop),
ze struktury sterowania przyjętej w danym algorytmie
proces jest sekwencją stanów przechodzonych jeden po drugim,
wybór jednego z możliwych stanów następnych zależy od
w każdym przebiegu algorytmu kolejność stanów wynika z
zawartości komórek pamięci, w których zapisano dane
zawartości określonych komórek w pamięci MO.
początkowe dla konkretnego przebiegu algorytmu
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 5 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 6
1
Maszyna Turinga (MT)
Jak dalece można uprościć zestaw operacji, tak aby można
było realizować różne algorytmy?
Jeden z wielu modeli prostej MO
Zestaw podstawowych operacji musi zawierać zapisanie i odczytanie
symbolu z komórki pamięci, wskazanie pojedynczej komórki w celu
STEROWANIE
dokonania zapisu lub odczytu oraz przejście do kolejnego stanu.
(diagram przejść
głowica
między stanami)
Okazuje się, że nie musi zawierać już niczego więcej!
ruch głowicy
ODCZYTUJ
CO
o jedną komórkę
-ZAPISUJ
CA
Operacje wykonywane przez MO:
w lewo lub w prawo
1. przeczytanie jednego symbolu ze wskazanej komórki taśmy,
# # a # #
2. zapisanie jednego symbolu do wskazanej komórki taśmy,
PAMI
Ć (nieskończona taśma)
komórka
3. wskazanie jednej z dwóch komórek sąsiednich po wykonaniu
pamięci pojedynczy
odczytu i zapisu w bieżącej komórce,
symbol alfabetu
4. przejście do kolejnego stanu.
Wszystkie podane operacje mogą być wykonywane zawsze razem
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 7 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 8
Węzłami (wierzchołkami) diagramu przejść są wszystkie stany
Na MT składa się:
w jakich może znajdować się MT podczas realizacji algorytmu,
skończony alfabet symboli do zapisywania danych,
dla którego została zdefiniowana.
Węzły na diagramie są połączone odcinkami skierowanymi,
skończony zbiór stanów, w których może się znajdować proces
które symbolizują możliwe przejścia od stanu do stanu.
realizacji algorytmu zapisanego w postaci MT,
Każde przejście opisane jest tzw. etykietą.
nieskończona taśma podzielona na komórki przechowujące
pojedyncze symbole alfabetu,
akcja
etykieta
stan
(węzeł grafu)
krokowo poruszająca się głowica odcztująco-zapisująca,
przejście
a / b L
diagram przejść miedzy stanami, który steruje głowicą tak,
nazwa stanu
że po każdym odczytaniu zawartości komórki następuje zapisanie
do niej podanego symbolu, głowica jest przesuwana w lewo lub
kierunek przesunięcia
wyzwalacz przejścia
głowicy (L lub P)
(symbol alfabetu odczytany
w prawo o jedną komórkę i następuje przejście do kolejnego
przez głowicę z taśmy)
stanu, co rozpoczyna znów tę samą sekwencję operacji, symbol alfabetu zapisywany
przez głowicę na taśmie
jeden stan początkowy i stany końcowe, których może być kilka.
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 9 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 10
dokładnie jeden ze stanów w diagramie przejść MT
dla każdego stanu w diagramie MT muszą być opisane
jest wyróżniony jako stan początkowy,
przejścia do kolejnych stanów dla wszystkich symboli
w przyjętym alfabecie i dla dodatkowego symbolu #,
MT jest deterministyczna, jeżeli z żadnego stanu nie
Stan 1.
wychodzi więcej niż jedno przejście z tym samym
wyzwalaczem, tzn. nie pozostawiamy
wyboru przejścia maszynie, zakładając,
w stanie początkowym głowica MT jest ustawiona na pierwszej
a / b L
że wybierze właściwie;
od lewej niepustej komórce taśmy,
odczytanie z taśmy symbolu
stany, z których nie wychodzą już żadne przejścia, nazywane
a / c P
wyzwalacza jednoznacznie wskazuje,
są stanami końcowymi  MT kończy w nich swoje działanie,
(determinuje), który ze stanów jest
stanem następnym,
Stan  TAK
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 11 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 12
2
Przykład MT do wykrywania palindromów
# # a b b a # #
# # # b b a # #
# # # b b a # #
# # # b b a # #
# # # b b a # #
# # # b b a # #
# # # b b # # #
# # # b b # # #
# # # b b # # #
# # # b b # # #
# # # # b # # #
# # # # b # # #
# # # # b # # #
# # # # # # # #
# # # # # # # #
# # # # # # # #
Alfabetem symboli jest zbiór {a, b}
# / # L
ruch dla a test dla a
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
ruch dla a test dla a
a / # L b / b L
b / b P a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # L b / b L
a / # P b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
a / a L a / # P
a / # P
a / # P
a / # P
a / # P
a / # P
a / # P
a / # P
a / # P
a / # P
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a P b / b L a / a L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
a / a P b / b L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
1. z lewej TAK NIE powrót
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L # / # L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L
a / a L a / a L
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P
b / b P b / b P
b / # P
b / # P
b / # P
b / # P
b / # P
b / # P
b / # P
b / # P
b / # P
b / # P b / # P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
a / a P
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
b / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
# / # L
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
ruch dla b test dla b
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
# / # P
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 13 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 14
Przykład taśmy MT przy dodawaniu dwóch liczb dziesiętnych
Jakie algorytmy może realizować MT?
# # # # # # # # 7 3 6 + 6 3 5 1 9 #
Wszystkie!
# # # # # # 5 ! 7 3 # + 6 3 5 1 # #
Teza Churcha-Turinga (tzw. Teza CT)
# # # # # 5 5 ! 7 # # + 6 3 5 # # # Na maszynie Turinga można zrealizować rozwiązanie każdego
efektywnie rozwiązywalnego problemu algorytmicznego!
# # # # 2 5 5 ! # # # + 6 3 # # # #
MT jest uniwersalną MO
# # # 4 2 5 5 ! # # # + 6 # # # # #
efektywnie rozwiązywalny problem algorytmiczny = problem,
dla którego można znalez
ć algorytm dający się zapisać w
# # 6 4 2 5 5 ! # # # + # # # # # #
jakimkolwiek języku jako program wykonujący się na
jakimkolwiek istniejącym lub możliwym do zbudowania
# ! 6 4 2 5 5 ! # # # + # # # # # #
komputerze (nawet jeśli wymagałby on nieograniczonej ilości
MT może realizować także algorytmy obliczeniowe czasu i pamięci)
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 15 Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 16
MT stosowana jest w wielu odmianach:
maszyna z taśmą tylko jednostronnie nieskończoną,
maszyna z wieloma taśmami i głowicami,
maszyna z taśmą dwuwymiarową,
Teza CT
maszyna niedeterministyczna.
Wszystkie te odmiany są równoważne w sensie zbioru problemów
algorytmicznych, które mogą być nimi rozwiązane.
Proponowano różne inne uniwersalne MO:
rachunek lambda (A. Church), system produkcji do manipulowania
symbolami (E. Post), klasa funkcji rekurencyjnych (S. Kleen) itd.
Wszystkie te modele są równoważne MT Teza CT
Jarosław Sikorski - BUDOWA i ANALIZA ALGORYTMÓW, WIT 2006 r. 17
3