MASZYNA TURINGA

SPIS TREŚCI

1. Budowa maszyny Turinga.
2. Jak to działa??
3. Przykłady dla MT

1. Budowa maszyny Turinga

Maszyna Turinga to prosta maszyna, którą w 1937 roku opisał Alan Turing pracując nad koncepcją obliczalności funkcji matematycznych...
Dobra bez dalszego ściemniania. Czym właściwie jest taka maszyna?? Można powiedzieć, że MT (tak dalej nazywał będę maszynę Turinga), jest matematycznym modelem komputera.
MT składa się z trzech części:
1. Taśmy z komórkami zawierającymi przetwarzane przez MT symbole.
2. Głowicy zapisująco-odczytującej.
3. Układu sterowania głowicą

1. Taśma
Taśma jest częścią nieruchomą oraz nieskończoną. Służy do przechowywania informacji, analogicznie jak pamięć w komputerze. W każdej "komórce" taśmy może znajdować się jeden sybol. Alfabet symboli musi być skończony. Oprócz symboli przetwarzanych przez MT, na taśmie musi znaleźć się symbol informujący o końcu taśmy. Najbardziej popularnym rozwiązaniem jest zdefiniowanie alfabetu składającego się z dwóch znaków 0 oraz 1, oraz dowolnego znaku dodatkowego kończącego taśmę. Odpowiada to binarnemu zapisowi informacji w komputerze.

2. Głowica
Głowica jest częścią ruchomą MT. Służy ona do odczytywania i (po ich przetworzeniu) zapisywania informacji na taśmie. Oprócz odczytywania i zapisywania informacji głowica może się przemieszczać w lewo i prawo, aby ustawić się nad kolejną komórką z kolejnym symbolem do przetworzenia. Zanim MT przystąpi do pracy głowica musi być ustawiona nad pierwszym symbolem (pierwszą komórką) do przetworzenia (to chyba logiczne). Aha no i porównując MT do komputera, głowica byłaby urządzeniem we/wy (wejścia/wyjścia).

3. Układ sterowania głowicą
Układ sterowania głowicą to serce maszyny Turinga. Odpowiada on procesorowi w komputerze. To właśnie ten układ "decyduje" jak należy przetwarzać informacje, tzn. jaki symbol należy wpisać w komórce taśmy. Układ sterowania głowicą może tkwić w kilku "stanach". To właśnie stan układu sterowania w połączeniu z odczytanym symbolem powoduje wpisanie odpowiedniego symbolu do komórki taśmy. Jeśli czegoś (lub dosłownie niczego, to sie nie przejmuj niedługo sie wiele wyjaśni :) ).

2. Jak to działa??

Podsumowując to co już napisałem a musisz narazie wiedzieć, operacja wykonywana przez MT na taśmie zależą od stanu układu sterowania głowicą, oraz właśnie odczytanego sybolu z taśmy. Inaczej mówiąc wszystkie elementy składające się na wykonanie instrukcji przez MT wyglądają tak:

S₀

Q₀

S_Z

Q_Z

^L/_R

gdzie:
S₀ - Symbol właśnie odczytany z taśmy.
Q₀ - Aktualny stan układu sterującego głowicą.
S_Z - Nowy symbol zapisywany w miejsce starego.
Q_Z - Nowy stan układu sterującego.
^L/_R - Instrukcja czy głowica ma przemieścić się o jedną komórkę w lewo czy w prawo.
Jeśli chodzi o stan początkowy układu to przyjmuje się go za S₀, a wszystkie kolejne zdefiniowane przez nas stany układu przyjmuje się kolejno za S₁, S₂, S₃ itd.
Popatrz jeszcze raz na elementy instrukcji i ich opis. Łatwo zauważyć, że te elementy dzielą się na jakby dwie części. Pierwsze dwa elementy to część identyfikacyjna instrukcji, ponieważ to one identyfikują instrukcje która ma być wykonana (niedługo się o tym przekonasz). Skoro jest to część identyfikacyjna, to logiczne jest, że w dwóch różnych instrukcjach nie może ona być taka sama.
Teraz zajmijmy się drugą częścią instrukcji. Po zidentyfikowaniu instrukcji (przez pierwsze dwa elementy) która ma być wykonana, właśnie te trzy ostatnie elementy, mówią nam, co właściwie należy zrobić. Dlatego ta część instrukcji to część operacyjna.

3. Przykłady dla MT

Dobra, jeśli czegoś nie rozumiesz, to czas najwyższy wyjaśnić to na przykładach. Zacznijmy od najprostszej chyba operacji, czyli negacji bitów liczby. W naszym przykładzie niech będzie to liczba 33 (dec), którą, jeśli zamienimy na system binarny, otrzymamy 00100001. Zamieniliśmy ją na system binarny, ponieważ w naszych przykładach alfabet symboli mogących znaleźć się na taśmie będzie składał się ze znaków 0 i 1, oraz znaku pustego o oznaczeniu powiedzmy !. Przypominam, że jeśli głowica trafi na komórkę zawierającą znak pusty, znak taki nie jest przetwarzany przez MT.
O tym, że negacja bitów to zamiana jedynek na zera, a zer na jedynki chyba wiesz. Taka operacja jest najprostsza, ponieważ nowy symbol, zależy tylko od starego, a stan układu nie jest tu ważny. Ponieważ stan układu nie jest ważny, będzie on niezmienny, a więc taki jak w chwili rozpoczęcia pracy przez MT. Napiszmy więc instrukcje dla MT (bede je od razu opisywał):
0,Q₀,1,Q₀,L - Jeśli odczytanym wlaśnie symbolem będzie 0, a stanem układu będzie Q₀, to w miejsce starego symbolu zostanie zapisane 1, stan układu przejdzie w Q₀ (czyli sie nie zmieni), a głowica wykona ruch o jedną komórkę w lewo (w lewo, bo zanim MT rozpocznie pracę, ustawiamy głowicę nad pierwszą komórką taśmy od prawej strony).
1,Q₀,0,Q₀,L - Jeśli odczytanym wlaśnie symbolem będzie 1, a stanem układu będzie Q₀, to w miejsce starego symbolu zostanie zapisane 0, stan układu przejdzie w Q₀ (czyli sie nie zmieni), a głowica wykona ruch o jedną komórkę w lewo.
A więc operacja negacji bitów będzie wyglądać tak (na czerwono oznaczyłem właśnie przetwarzany symbol - bit):

LP	Taśma przed operacją	Wykonywana instrukcja	Taśma po operacji	Uwagi
1	...! 0 0 1 0 0 0 0 1 ! ...	1,Q₀,0,Q₀,L	...! 0 0 1 0 0 0 0 0 ! ...	---
2	...! 0 0 1 0 0 0 0 0 ! ...	0,Q₀,1,Q₀,L	...! 0 0 1 0 0 0 1 0 ! ...	---
3	...! 0 0 1 0 0 0 1 0 ! ...	0,Q₀,1,Q₀,L	...! 0 0 1 0 0 1 1 0 ! ...	---
4	...! 0 0 1 0 0 1 1 0 ! ...	0,Q₀,1,Q₀,L	...! 0 0 1 0 1 1 1 0 ! ...	---
5	...! 0 0 1 0 1 1 1 0 ! ...	0,Q₀,1,Q₀,L	...! 0 0 1 1 1 1 1 0 ! ...	---
6	...! 0 0 1 1 1 1 1 0 ! ...	1,Q₀,0,Q₀,L	...! 0 0 0 1 1 1 1 0 ! ...	---
7	...! 0 0 0 1 1 1 1 0 ! ...	0,Q₀,1,Q₀,L	...! 0 1 0 1 1 1 1 0 ! ...	---
8	...! 0 1 0 1 1 1 1 0 ! ...	0,Q₀,1,Q₀,L	...! 1 1 0 1 1 1 1 0 ! ...	---
9	...! 1 1 0 1 1 1 1 0 ! ...	Brak zdefiniowanej instrukcji	...! 1 1 0 1 1 1 1 0 ! ...	Koniec pracy MT

Dobra. Przykład z negacją bitów już za nami. Teraz może od razu kolejny przykładzik - dodanie do liczby binarnej jedynki. Posłużmy się tą samą liczbą co w poprzednim przykładzie, czyli liczbą 33 (dec), którą, jeśli zamienimy na system binarny, otrzymamy 00100001. Ten przykład będzie o tyle trudniejszy (choć o wiele krótszy), że symbol wpisywany nie będzie zależał już tylko od właśnie odczytanego symbolu. No to przejdźmy do napisania instrukcji dla MT.
0,Q₀,1,Q₂,L - Jeśli odczytanym symbolem będzie 0, a stanem układu będzie Q₀, to w miejsce starego symbolu zostanie wpisana 1, a stan układu przejdzie do Q₂. Q₂ to stan dla którego nie jest zdefiniowana żadna instrukcja, więc MT przerwie pracę gdy układ będzie w takim właśnie stanie.
1,Q₀,0,Q₁,L - Jeśli odczytanym symbolem będzie 0, a stanem układu będzie Q₀, to w miejsce starego symbolu zostanie wpisane 0, a stan układu przejdzie do Q₁. Q₁ to stan który mówi nam jakby: zapamiętaj, że do następnego odczytanego symbolu należy dodać 1.
0,Q₁,1,Q₂,L - Jeśli odczytanym symbolem będzie 0, a stanem układu będzie Q₁, to w miejsce starego symbolu zostanie wpisana 1, a stan układu przejdzie do Q₂. Q₂ to stan dla którego nie jest zdefiniowana żadna instrukcja, więc MT przerwie pracę gdy układ będzie w takim właśnie stanie.
1,Q₁,0,Q₁,L - Jeśli odczytanym symbolem będzie 1, a stanem układu będzie Q₁, to w miejsce starego symbolu zostanie wpisane 0, a stan układu przejdzie do Q₁. Q₁ to stan który mówi nam jakby: zapamiętaj, że do następnego odczytanego symbolu należy dodać 1.
!,Q₁,1,Q₂,L - Jeśli odczytanym symbolem będzie ! - znak pusty, który oznacza, że liczba się skończyła, ale stanem układu będzie Q₁, który mówi że do następnego symbolu należy dodać 1, to w miejsce starego symbolu zostanie wpisane 1, a stan układu przejdzie do Q₂. Q₁ to stan który mówi nam jakby: zapamiętaj, że do następnego odczytanego symbolu należy dodać 1.
No to operacja dodania do liczby 00100001 liczby 1 będzie wyglądała tak:

LP	Taśma przed operacją	Wykonywana instrukcja	Taśma po operacji	Uwagi
1	...! 0 0 1 0 0 0 0 1 ! ...	1,Q₀,0,Q₁,L	...! 0 0 1 0 0 0 0 0 ! ...	---
2	...! 0 0 1 0 0 0 0 0 ! ...	0,Q₁,1,Q₂,L	...! 0 0 1 0 0 0 1 0 ! ...	---
3	...! 0 0 1 0 0 0 1 0 ! ...	Brak zdefiniowanej instrukcji	...! 0 0 1 0 0 0 1 0 ! ...	Koniec pracy MT