Maszyna Turinga
Maszyna Turinga jest prostym urządzeniem algorytmicznym, uderzająco prymitywnym w porównaniu z dzisiejszymi komputerami i
językami programowania, a jednak na tyle silnym, że pozwala na wykonanie nawet najbardziej złożonych algorytmów.
Maszyna Turinga jest mechanizmem powstałym w wyniku ciągu uproszczeń: danych, sterowania nimi oraz uproszczeń
podstawowych operacji.
Maszynę tą wymyślił w roku 1936 brytyjski matematyk Alan M.Turing
UPRASZCZANIE DANYCH
Każdy element danych używany w algorytmie, czy to będą dane wejściowe, wyjściowe czy wartości pośrednie, można traktować
jako ciąg symboli, czyli napis. Liczba całkowita nie jest niczym innym, jak ciągiem cyfr, liczba ułamkowa zaś ciągiem cyfr,
który może zawierać kropkę. Prostej linearyzacji mogą podlegać zarówno słowa jak i teksty, które są ciągiem symboli składającym się
z liter, znaków przestankowych i odstępów. Wszystkie obiekty a nawet najbardziej skomplikowane struktury danych możemy
łatwo zakodować, traktując je cały czas symbolicznie, jako liczby, słowa lub teksty.
Liczba różnych symboli jest skończona i ustala się ją zawczasu. Każdą interesującą nas jednostkę danych możemy
więc zapisać na jednowymiarowej taśmie o nieograniczonej długości składającej się z ciągu kwadratów,
z których każdy zawiera pojedynczy symbol z pewnego skończonego alfabetu. Alfabet składa się z rzeczywistych symboli,
które same tworzą jednostki danych, oraz specjalny symbol pusty wskazujący brak informacji. Taśma zawsze będzie zawierać skończoną
znaczącą porcję danych, otoczoną z każdej strony nieskończonym ciągiem symboli pustych.
UPRASZCZANIE STEROWANIA
Jedną z najważniejszych rzeczy dla uproszczenia sterowania jest skończoność tekstu algorytmu. Procesor może znajdować się
tylko w jednym ze skończonej liczby miejsc w tym tekście. Wystarczy użyć więc prymitywnego mechanizmu zawierającego pewien rodzaj
skrzyni biegów, mającej skończenie wiele stanów. Stany skrzyni biegów będziemy traktować jako służące do kodowania miejsc
w algorytmie, więc poruszanie się w nim modelujemy zmianą stanu. W każdym punkcie wykonywania algorytmu miejsce, które ma być odwiedzone
jako następne, zależy od miejsca, w którym się znajdujemy, tak więc następny stan skrzyni biegów zależy od jego bieżącego stanu.
Zmiana stanu zależy od danych oraz od bieżącego stanu. W danej chwili czasu może być czytany tylko pojedynczy symbol, więc dopuszcza się badanie
tylko jednego kwadratu na raz. Mechanizm "zmienia bieg" w zależności od wartości czytanego symbolu i swojego stanu bieżącego,
przechodząc do nowego stanu. Mechanizm porusza się po taśmie przesuwając się wzdłuż nie po jednym kwadracie a kierunek ruchu zależy
od bieżącego stanu skrzyni biegów i bieżącego symbolu.
Te ograniczenia upraszczają sterowanie w algorytmie. Powstały mechanizm jest prostym mechanizmem
mogącym być w jednym ze skończonej liczby stanów, poruszając się wzdłuż taśmy po jednym kwadracie.
Mechanizm ten działa wyznaczając nowe stany i kierunki jako funkcje stanu bieżącego i bieżącego symbolu.
UPRASZCZANIE PODSTAWOWYCH OPERACJI
Poprawność działania algorytmów zależy od poprawnego manipulowania danymi, przekształcania ich,
wymazywania, czytania lub zapisywania, stosowania do nich operacji arytmetycznych lub tekstowych.
Do zmiany stanu i poruszania się o jeden kwadrat w lewo lub w prawo
omawiany mechanizm jest wyposażony w możliwości przekształcania w określonym stanie pewnego widzianego
symbolu w jeden ze skończonej liczby dostępnych symboli.
Podstawowy model maszyny Turinga
Maszyna Turinga
jest prostym modelem matematycznym komputera.
Podstawowy model
przedstawiony na rysunku 1 ma skończone sterowanie, taśmę wejściową
podzieloną na komórki (kwadraty) oraz głowicę taśmy, mogącą obserwować w
dowolnej chwili tylko jedna komórkę taśmy. Taśma ma komórkę położoną
najbardziej na lewo, ale jest prawostronnie nieskończona. Każda z
komórek taśmy może zawierać dokładnie jeden symbol z skończonego alfabetu
symboli. Przyjmuje się umownie, że ciąg symboli wejściowych umieszczony
jest na taśmie począwszy od lewej, pozostałe komórki ( na prawo od symboli
wejściowych) są wypełnione specjalnym symbolem taśmowym noszącym nazwę
symbolu pustego.
Maszyna Turinga składa się z następujących elementów:
skończonego alfabetu
symboli;
skończonego zbioru stanów;
nieskończonej
taśmy
z zaznaczonymi kwadratami, z których każdy może zawierać pojedynczy symbol;
ruchomej głowicy
odczytująco - zapisującej, która może wędrować wzdłuż taśmy przesuwając się na raz
o jeden kwadrat
diagramu przejść między stanami,
zawierającego instrukcje, które powodują, że zmiany następują przy każdym zatrzymaniu się.
Rysunek 1. Podstawowy model maszyny Turinga
W zależności od
obserwowanego symbolu przez głowicę taśmy oraz stanu sterowania
skończonego, maszyna Turinga w pojedynczym ruchu:
zmienia stan,
wpisuje symbol w obserwowanej
komórce taśmy, zastępując symbol tam wpisany,
przesuwa głowicę o jedną
komórkę w prawo lub w lewo.
Formalnie maszynę Turinga (MT) nazywamy:
M = <Q, 
, 
, ð, q0, B, F >
gdzie:
Q-
jest skończonym zbiorem stanów,
-
skończony zbiór dopuszczalnych symboli taśmowych,
B-
symbol pusty należący do
,
-
podzbiór
nie zawierający B, zwany zbiorem symboli
wejściowych,
ð
-
funkcja następnego ruchu, będąca odwzorowaniem Q x
w Q x
x
{ L, P }
gdzie:
L-
oznacza ruch w lewo
P-
ruch w prawo,
q0- stan
początkowy,
F
Q - zbiór stanów
końcowych
Działanie maszyny
Turinga przedstawia się jako diagram przejść między stanami lub jako
tabelę stanów, które to pojęcia zostały omówione poniżej.
Diagram przejść między stanami
zawiera instrukcje, które powodują, że zmiany następują po każdym
zatrzymaniu się. Diagram przejść jest grafem
skierowanym, którego wierzchołki
reprezentują stany. Krawędź prowadząca ze stanu s do stanu
t nazywa się przejściem i etykietuje się ją kodem postaci
(a/b, kierunek) gdzie a i b są
symbolami,
a kierunek określa ruch głowicy w prawo bądź w
lewo. Część a etykiety jest wyzwalaczem przejścia, a część
<b, kierunek> akcją:
W czasie swego
działania maszyna Turinga, kiedy znajdzie się w stanie s i
odczytywanym symbolem będzie a to nastąpi wpisanie w to miejsce
b i przesunięcie o jedno pole w kierunku kierunek. Fragment
przykładowego diagramu przejść przedstawia rysunek 2.
Rysunek 2. Fragment grafu przejść między stanami dla maszyny Turinga
Aby zapobiec niejednoznaczności, co do następnego ruchu maszyny (tj. aby jej zachowanie było deterministyczne),
z jednego stanu nie wychodzą dwa przejścia z tym samym wyzwalaczem. Jeden ze stanów w diagramie jest zaznaczony
skierowaną do niego strzałką opatrzoną etykietą start i jest nazywany stanem początkowym. Podobnie
stany z których nie wychodzą już żadne przejścia, nazywa się stanami końcowymi.
Tabela stanów -
która również obrazuje przejścia między stanami maszyny Turinga zawiera
wszystkie symbole
z skończonego alfabetu wejściowego jak
również wszystkie stany w których może znaleźć się maszyna Turinga.
Każde pole tabeli określa:
- dla danego stanu
qi kolejny stan qi+1
- symbol, który ma być zapisany
na taśmie
- kierunek (L / P) dla
ruchu głowicy
Rysunek 4. Fragment stanów
maszyny Turinga
Zarówno dla tabeli
stanów jak i
grafu przejść
wyróżnia się specyficzne stany będące
odpowiednio stanem początkowym i stanem (bądź stanami ) końcowym, zwane
też stanami biernymi. Zakłada się , że maszyna rozpoczyna swoje działanie
od swego stanu początkowego na pierwszym od lewej niepustym kwadracie
taśmy i postępuje krok po kroku zgodnie z narzuconym ruchem, zaś kończy
działanie po osiągnięciu stanu końcowego.
Teza Churcha-Turinga
Różnorodność zadań
stawianych przed maszyną Turinga postawiło pytanie :
Jakie problemy można
rozwiązać odpowiednio zaprogramowaną maszyną Turinga (oczywiście pomijając czas) ?
Otóż okazuje się że:
Maszyny Turinga potrafią rozwiązać każdy efektywnie rozwiązywalny
problem algorytmiczny.
Mówiąc inaczej, 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.
To stwierdzenie jest
jedną z wersji tzw. tezy Churcha-Turinga (Alonz Church, Alan M. Turing), którzy doszli do niej
niezależnie w połowie lat trzydziestych. Istotną sprawą jest aby
uświadomić sobie, że teza Churcha-Turinga jest tezą a nie twierdzeniem,
zatem nie może być dowiedziona w matematycznym tego słowa znaczeniu. Jedno
z pojęć, do której się odwołuje, jest bowiem nieformalnym i
nieprecyzyjnym, pojęciem “efektywnej obliczalności”.
Dlaczego jednak
powinniśmy wierzyć tej tezie, szczególnie, jeśli nie można jej
udowodnić?
Już od wczesnych
lat trzydziestych badacze proponowali różne modele komputera absolutnego,
wszechpotężnego, lub uniwersalnego. Chciano bowiem sprecyzować ulotne
pojęcie “efektywnej obliczalności”. Na długo przedtem nim wymyślono
pierwszy komputer, Turing zaproponował swoją maszynę, a Church wymyślił
matematyczny formalizm funkcji zwany rachunkiem lambda (jako podstawa
języka programowania Lisp). Mniej więcej w tym samym czasie Emil Post
zdefiniował pewien typ systemu produkcji do manipulowania symbolami, a
Stephen Kleene zdefiniował klasę obiektów zwanych funkcjami
rekurencyjnymi.
Wszyscy oni
próbowali użyć tych modeli do rozwiązania wielu problemów algorytmicznych,
do których znane były “efektywnie wykonalne” algorytmy.
Przełomowym
zdarzeniem istotnym dla wszystkich tych modeli stało się udowodnienie, iż
są one równoważne
w kategoriach problemów algorytmicznych, które
rozwiązują. I ten fakt jest dziś nadal prawdziwy nawet dla
najsilniejszych modeli, jakie można sobie wyobrazić.
Z tezy
Churcha-Turinga wynika, że najpotężniejszy superkomputer z wieloma
najwymyślniejszymi językami programowania, interpretatorami, kompilatorami
i wszelkimi zachciankami, nie jest potężniejszy od domowego komputera z
jego uproszczonym językiem programowania. Mając ograniczoną ilość czasu i
pamięci mogą obydwa rozwiązać te same problemy algorytmiczne, jak również
żaden z nich nie może rozwiązać problemów nierozstrzygalnych
(nieobliczalnych). Schematycznie rozstrzygalność problemów przedstawia
rysunek 4.
Rysunek 4. Sfera problemów algorytmicznych.
Problem algorytmiczny, do którego nie ma żadnego algorytmu jest nazywany nieobliczalnym;
jeśli to problem decyzyjny nazywa się nierozstrzygalnym. Dla problemów tego typu w żaden sposób nie można
skonstruować algorytmu, wykonywanego na dowolnym komputerze, bez względu na ilość wymaganego czasu i pamięci, który
mógłby je rozstrzygnąć.
ODMIANY MODELU MASZYNY TURINGA
Działanie maszyny Turinga można ograniczyć na wiele sposobów nie
zmniejszając jednak klasy problemów, które rozwiązuje. Można na przykład
żądać, żeby dane wejściowe pozostały nienaruszone i żeby przy
zatrzymaniu taśma zawierała tylko dane i wyniki otoczone symbolami pustymi.
Można zdefiniować maszynę Turinga z taśmą, która jest nieskończona
tylko z prawej strony, a dane są zapisywane na taśmie od lewego skraju. Obie
odmiany maszyny mogą rozwiązywać dokładnie te same problemy co model
podstawowy i wobec tego nie są od niego słabsze. Podobnie dodanie maszynom
dowolnie silnej własności nie powoduje żadnego rozszerzenia klasy rozwiązywalnych
problemów. W żadnym z rozszerzeń nie da się rozwiązać problemu nie rozwiązywalnego.
Maszyna, która może symulować działanie dowolnej maszyny Turinga na
dowolnych danych nazywa się uniwersalną maszyną Turinga. Uniwersalna
maszyna Turinga U akceptuje jako dane opis dowolnej maszyny Turinga M,
po którym jest umieszczony skończony ciąg X traktowany jako dane dla
maszyny M. Następnie symuluje ona akcje maszyny M na taśmie,
na której znajdują się dane X otoczone symbolami pustymi. Jeśli
maszyna M nie może zatrzymać się na taśmie, to także nie może
zatrzymać się maszyna U, jeśli maszyna M zatrzyma się to
zatrzyma się również maszyna U. Obie taśmy będą wyglądać dokładnie
tak samo po zakończeniu działania.
Ograniczenia narzucone na maszyny Turinga nie pomniejszają uniwersalności
modelu. Oczywiście nie wszystkie ograniczenia mają tę właściwość.
Maszyny, od których wymaga się, aby zatrzymywały się zaraz po uruchomieniu
lub nie zatrzymywały się w ogóle , nie dokonają wiele.
Istnieje również inny sposób ograniczenia modelu maszyny Turinga. Wiąże
się on z ograniczeniem samego mechanizmu maszyny. Jedną z najbardziej
interesujących degeneracji otrzymuje się ograniczając poruszanie się
maszyny Turinga na taśmie tylko do jednego kierunku (jednokierunkowa maszyna
Turinga), np. w prawo. Wynikiem jest urządzenie zwane automatem skończenie
stanowym lub automatem skończonym. Automat skończony rozwiązujący
problem decyzyjny działa następująco. Przechodzi wzdłuż podanej sekwencji
symbol po symbolu zmieniając stan w wyniku stanu bieżącego i nowego symbolu
z taśmy. Po osiągnięciu końca sekwencji zatrzymuje się, a odpowiedź zależy
od tego, czy automat zatrzymał się w stanie TAK czy NIE.
Automat skończony można przedstawić jako diagram przejść między stanami,
tak jak dla maszyny Turinga, teraz jednak baz części <b, kierunek>
w etykiecie; przejście jest etykietowane symbolem, który je wyzwala.
Przykłady zadań rozwiązanych za pomocą maszyny Turinga
Przykład 1:
Maszyna Turinga podwajająca symbole w słowie.
W celu zobrazowania
konstrukcji tabeli stanów przeanalizujmy maszynę Turinga, która dla
alfabetu wejściowego
={a, b} podwaja symbole w słowie.
={a,
b}
= { ø , a , b}
Przed wypisaniem
tabeli stanów przeanalizujmy jak podana maszyna Turinga ma działać. Dla
słowa:
ab
otrzymujemy aabb
aba
otrzymujemy aabbaa
Słowo na taśmie
zapisane jest jako ciąg symboli postaci na przykład ø
ø ø
a b ø
ø ø
Na początku w kolumnie wypisujemy wszystkie symbole
= { ø , a , b}
i stan
początkowy q0
Będąc w
stanie
q1 musimy iść tak długo w prawo aż pominiemy wszystkie
symbole łącznie z pierwszym symbolem ø . Wtedy w miejsce
drugiego ø (może się ono znajdować po kilku symbolach z
alfabetu
wejściowego) wpisujemy
a i przechodzimy do stanu
q3. Jedynym słusznym symbolem napotkanym w tym stanie
jest ø , w miejsce którego wpisujemy drugie a i
przechodzimy do stanu q4 (stan powrotu). Jeżeli będąc
w tym stanie przejdziemy nad wszystkimi symbolami i napotkamy symbol
ø , to sprawdzamy, czy są jeszcze jakieś symbole wejściowe na
taśmie. Jeżeli tak to zaczynamy algorytm od początku, w przeciwnym razie
przechodzimy do stanu końcowego q15
| |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
| ø |
q0
ø, P |
q2
ø, P |
q3
a, P |
q4
a, L |
q5
ø, L |
q15
ø, P |
q0
ø, P |
| a |
q1
ø, P |
q1
a, P |
q2
a, P |
q15
a, P |
q4
a, L |
q6
a, L |
q6
a, L |
Dla symbolu
b pola w tabeli stanów będą tworzone analogicznie.
Ostateczny
wygląd tabeli stanów przedstawia tabela 1.
| |
q0 |
q1 |
q2 |
q3 |
q4 |
q5 |
q6 |
q7 |
q8 |
q9 |
q10 |
q11 |
q12 |
q13 |
| ø |
q0
ø, P |
q2
ø, P |
q3
a, P |
q4
a, L |
q5
ø, L |
q13
ø, P |
q0
ø, P |
q8
ø, P |
q9
b, P |
q10
b, L |
q11
ø, L |
q13
ø, P |
q0
ø, P |
SK |
| a |
q1
ø, P |
q1
a, P |
q2
a, P |
q13
a, P |
q4
a, L |
q6
a, L |
q6
a, L |
q7
a, P |
q8
a, P |
q13
a, P |
q10
a, L |
q12
a, L |
q12
a, L |
SK |
| b |
q7
ø, P |
q1
b, P |
q2
b, P |
q13
b, P |
q4
b, L |
q6
b, L |
q6
b, L |
q7
b, P |
q8
b, P |
q13
b, P |
q10
b, L |
q12
b, L |
q12
a, L |
SK |
Tabela 1. Tabela stanów maszyny Turinga podwajająca
symbole w słowie dla alfabetu wejściowego
={a, b}
Przeanalizujmy
kilka początkowych taktów pracy powyższej maszyny Turinga dla ciągu
wejściowego: a b
Ciąg ten jest na taśmie w postaci ø ø ø a b ø
ø ø ø...
|
| ø
ø ø a b ø ø
ø ø ... / |
pozostajemy w stanie q0 i przechodzimy w prawo |
| ø ø ø
ø b ø ø ø
ø ... / |
napotkaliśmy a, wpisujemy ø i przechodzimy w prawo do stanu
q1 |
| ø ø ø ø
b ø ø ø ø
... / |
pozostajemy nadal w stanie q1 aż dojdziemy do pierwszego znaku
ø |
| ø ø ø ø b
ø ø ø ø ...
/ |
po napotkaniu pierwszego ø przechodzimy w prawo do stanu
q2 |
| ø ø ø ø b
ø a
ø ø ... / |
po napotkaniu ø wpisujemy a i przechodzimy do stanu
q3 |
| ø ø ø ø b
ø a a
ø ... / |
w stanie q3 wpisujemy drugie a i przechodzimy do stanu
q4, który
to stan powoduje powrót na początek słowa i rozpoczęcie pracy od
nowa o ile są jeszcze na taśmie symbole wejściowe |
Po przeanalizowaniu
wszystkich symboli wejściowych przechodzimy do stanu
q13, który to stan jest stanem końcowym SK
(stan bierny).
Dla rozpatrywanego
ciągu wejściowego można określić trzy elementy w
tabeli stanów:
- stan warunkowy - który
powoduje przejście do określonej sekcji manipulowania danym
symbolem,
- sekcja manipulowania -
stany odpowiadające za przepisywanie symboli,
- powrót- stan powodujący
przejście do początku i rozpoczęcie pracy od nowa
Jak zostało
wcześniej wspomniane, alternatywne do tabeli stanów stosuje się graf
przejść między stanami. Konstrukcję przykładowego grafu ilustruje
kolejny przykład .
Przykład 2:
Inkrementacja liczby binarnej bez znaku.
Maszyna Turinga
dodającą 1 do danej liczby w zapisie dwójkowym.
Analizę liczby rozpoczynamy
z prawej strony.
| |
q0 |
q1 |
q2 |
| ø |
q0
ø, L |
q2
1, L |
SK |
| 0 |
q2
1, L |
q2
1, L |
SK |
| 1 |
q1
0, L |
q1
0, L |
SK |
|
 |
Maszyny Turinga z
przykładów: 1 i 2 rozwiązują problemy algorytmiczne związane z manipulacją
danych wejściowych. Odmianę stanowią maszyny Turinga rozwiązujące problemy
decyzyjne - przykład 3.
Przykład
3:
Maszyna Turinga bada czy dane słowo jest
palindromem.
Maszyna Turinga
badająca czy dane słowo z alfabetu wejściowego
={a, b, c} jest
palindromem (to znaczy słowem, które czyta się tak samo z obu stron).
Dodatkowo przyjmuje się, że pojedynczy symbol jest palindromem. Wprowadza
się dodatkowo 2 stany akceptacji SA i nieakceptacji
SN. Przejście do stanu akceptacji oznacza, że dane słowo jest
palindromem, zaś przejście do stanu nieakceptacji oznacza, że słowo nie
jest palindromem. Tabela przejść miedzy stanami wygląda następująco:
| | q0 | q1 | q2 | q3 | q4 |
q5 | q6 | q7 |
q8 | q9 | q10 | q11 |
| ø |
q0
ø, P |
q2
ø, L |
q10
ø, P |
q0
ø, P |
q5
ø, L |
q10
ø, P |
q0
ø, P |
q8
ø, L |
q10
ø, P |
q0
ø, P |
SA | SN |
| a |
q1
ø, P |
q1
a, P |
q3
ø, L |
q3
a, L |
q4
a, P |
q11
a, P |
q6
a, L |
q7
a, P |
q11
a, P |
q9
a, L |
SA |
SN |
| b | q4
ø, P | q1
b, P | q11
b, P | q3
b, L | q4
b, P |
q6
ø, L | q6
b, L | q7
b, P | q11
b, P | q9
b, L | SA | SN |
| c | q7
ø, P |
q1
c, P |
q11
c, P |
q3
c, L |
q4
c, P |
q11
c, P |
q6
c, L |
q7
c, P |
q9
ø, L |
q9
c, L |
SA |
SN |
Symulacja akcji maszyny Turinga dla taśmy zawierającej słowo abba
(otoczone nieskończenie wieloma symbolami pustymi z obu stron).
Głowica maszyny umieszczona jest na kwadracie zawierającym a znajdujące się najbardziej na lewo.
Maszyna "pamięta" pierwszy przeczytany symbol, po czym wymazuje go zastępując symbolem pustym i przechodzi w prawo,
aż do osiągnięcia
pierwszego symbolu pustego. (etap 1-5)
Maszyna przesuwa się o jeden symbol w lewo,
zatrzymuje się więc na najbardziej prawym symbolu (etap 6), w omawianym przypadku jest
to symbol a. Gdyby odczytany symbol był różny od zapamiętanego, to maszyna przeszłaby do stanu nieakceptacji.
Maszyna wymazuje odczytany najbardziej prawy symbol a
i przechodzi do stanu, który doprowadza ją do pierwszego symbolu pustego po lewej stronie słowa.
(etap 10)
Maszyna przesuwa się o jeden kwadrat w prawo
i zapamiętuje przeczytany symbol, drugi symbol słowa - symbol b. Ruszając się w prawo maszyna porówna zapamiętany symbol
z przedostatnim symbolem słowa. (etap 13)Porównanie kończy się sukcesem i maszyna wymazuje symbol
b.
Maszyna rusza w lewo w poszukiwaniu dalszych symboli. Nie znajdując żadnego
i nie osiągając stanu nieakceptacji przechodzi do stanu akceptacji. (etap 14-16)
Całą symulację krok po kroku, z bieżącym położeniem głowicy
przedstawia rys.5.
Rysunek 5. Symulacja akcji maszyny Turinga dla taśmy zawierającej słowo abba.