Maszyna Turinga

Maszyny Turinga pomimo swej prostoty posiada obecnie olbrzymie znaczenie teoretyczne, ponieważ wszystkie współczesne komputery dają się do niej sprowadzić. Problem jest rozwiązalny na komputerze, jeśli da się zdefiniować rozwiązującą go maszynę Turinga.

 Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

W roku 1937 angielski matematyk Alan Turing pracując nad koncepcją obliczalności funkcji matematycznych opisuje bardzo prostą maszynę logiczną, która dziś nosi nazwę Maszyny Turinga. Pomimo swej prostoty posiada ona obecnie olbrzymie znaczenie teoretyczne, ponieważ wszystkie współczesne komputery dają się do niej sprowadzić. Problem jest rozwiązalny na komputerze, jeśli da się zdefiniować rozwiązującą go maszynę Turinga.

(Informacje o pracach Turinga znajdziesz również w artykule o komputerach Colossus).

 

Pod koniec lat trzydziestych ubiegłego wieku Alan Turing nie posiadał do swojej dyspozycji komputerów, ponieważ w owym czasie ich jeszcze nie było (w powszechnym użyciu - zobacz na artykuły o Konradzie Zuse i jego komputerach). Dlatego na potrzeby swoich badań nad problemami obliczalności opracował model maszyny, który można zrealizować nawet na kartce papieru. Maszyna Turinga zbudowana jest z trzech głównych elementów: Nieskończonej taśmy zawierającej komórki z przetwarzanymi symbolami Ruchomej głowicy zapisująco-odczytującej. Układu sterowania głowicą.

Nieskończona taśma jest odpowiednikiem współczesnej pamięci komputera. Taśma dzieli się na komórki, w których umieszczone zostały symbole, czyli po prostu znaki przetwarzane przez maszynę Turinga. Symbole te stanowią odpowiednik danych wejściowych. Maszyna Turinga odczytuje te dane z kolejnych komórek i przetwarza na inne symbole, czyli dane wyjściowe. Wyniki obliczeń również są zapisywane w komórkach taśmy.
 

...

A

A

C

C

D

D

0

1

2

3

E

F

G

Z

?

?

...

Można definiować różne symbole dla maszyny Turinga. Najczęściej rozważa się jedynie symbole 0, 1 oraz tzw. znak pusty - czyli zawartość komórki, która nie zawiera żadnej danej do przetworzenia.  Wbrew pozorom taki prymitywny zbiór trzech symboli jest równoważny logicznie dowolnemu innemu zbiorowi. Przecież współczesne komputery wewnętrznie operują jedynie na bitach, a mimo to są w stanie przetwarzać prawie dowolną informację z obrazami, dźwiękiem i filmami włącznie. Dokładny opis tego faktu znajdziemy w naszym opracowaniu o systemach liczbowych i w przykładowej maszynie cyfrowej.

Na potrzeby naszego opracowania rozszerzamy alfabet do wszystkich znaków ASCII, lecz zwykle będziemy korzystać tylko z niewielkiego podzbioru tych symboli - w przeciwnym razie program bardzo się rozbudowuje. Za symbol pusty wybieramy dowolny znak, z którego nie korzystamy w danych wejściowych - na przykład spację, ?, #, itp.

Aby przetwarzać dane, maszyna Turinga musi je odczytywać i zapisywać na taśmę. Do tego celu przeznaczona jest właśnie głowica zapisująco-odczytująca, która odpowiada funkcjonalnie urządzeniom wejścia/wyjścia współczesnych komputerów lub układom odczytu i zapisu pamięci.

Głowica zawsze znajduje się nad jedną z komórek taśmy. Może ona odczytywać zawartość tej komórki oraz zapisywać do niej inny symbol - na tej zasadzie odbywa się przetwarzanie danych - z jednych symboli otrzymujemy inne. Oprócz odczytywania i zapisywania symboli w komórkach głowica wykonuje ruchy w prawo i w lewo do sąsiednich komórek na taśmie. W ten sposób może się ona przemieścić do dowolnie wybranej komórki taśmy.

Przed rozpoczęciem pracy maszyny Turinga głowica jest zawsze ustawiana nad komórką taśmy zawierającą pierwszy symbol do przetworzenia.

Przetwarzaniem informacji zarządza układ sterowania głowicą. Jego współczesnym odpowiednikiem jest procesor komputera. Układ ten odczytuje za pomocą głowicy symbole z komórek taśmy oraz przesyła do głowicy symbole do zapisu w komórkach. Dodatkowo nakazuje on głowicy przemieścić się do sąsiedniej komórki w lewo lub w prawo.

Podstawą działania maszyny Turinga są stany układu sterowania. Jest to pojęcie trudne do zrozumienia dla początkujących, jednakże gdy raz to się stanie, maszyna Turinga okaże się bardzo prostym automatem, który będziemy mogli dowolnie programować. Stan układu sterowania określa jednoznacznie jaką operację wykona, jak zareaguje maszyna Turinga, gdy odczyta z taśmy określony symbol.

Zatem operacje wykonywane przez układ sterowania zależą od dwóch czynników:

1. Symbolu odczytanego z komórki na taśmie.
2. Bieżącego stanu układu sterującego.

Stany będziemy określać kolejnymi nazwami: q₀, q₁, q₂, ... ,q_n, gdzie q₀ jest stanem początkowym, w którym znajduje się maszyna Turinga przed rozpoczęciem przetwarzania symboli na taśmie.

Instrukcją dla maszyny Turinga jest następująca piątka symboli:
 

Instrukcja maszyny Turinga	Znaczenia symboli
(So,qi,Sz,qj,L/P)	So	symbol odczytany przez głowicę z bieżącej komórki na taśmie
	qi	bieżący stan układu sterowania
	Sz	symbol, jaki zostanie zapisany w bieżącej komórce na taśmie
	qj	nowy stan, w który przejdzie układ sterowania po wykonaniu tej operacji
	L/R	ruch głowicy o jedną komórkę w lewo (L) lub w prawo (R)

S₀ i q_i są tzw. częścią identyfikacyjną instrukcji. Maszyna Turinga wykonuje tyle różnych instrukcji, ile zdefiniujemy części identyfikacyjnych - w programie nie może być dwóch różnych instrukcji o identycznej części identyfikacyjnej. Powód jest oczywisty - którą instrukcję należałoby w takim wypadku wykonać?

S_z, q_j i L/P są tzw. częścią operacyjną, która określa jakie działanie podejmuje dana instrukcja. Części operacyjne różnych instrukcji mogą być takie same - oznacza to jedynie, iż instrukcje te wykonują dokładnie to samo działanie.

Szybko, zanim ta wiedza ulotni się nam w niedostępne obszary mózgu, podajmy odpowiedni przykład. Oto on:

(A, q₀, B, q₀, R)

Co robi ta instrukcja? Otóż jeżeli odczytanym przez głowicę symbolem z taśmy będzie literka A, a układ sterowania znajduje się w stanie q₀, to głowica zamieni ten symbol na B, stan wewnętrzny nie zmieni się (pozostanie dalej q₀), a głowica przesunie się do sąsiedniej komórki po prawej stronie. Zawile? Chyba nie.

Pierwsze dwa elementy określają jednoznacznie instrukcję. Pozostałe trzy określają, co w ramach tej instrukcji należy zrobić, czyli jaki symbol umieścić w bieżącej komórce taśmy, w jaki nowy stan przejść i w którą stronę przesunąć głowicę.

Programem dla maszyny Turinga jest tablica, w której określamy wszystkie wykonywalne przez nią instrukcje. Kolejność tych instrukcji w żaden sposób nie jest istotna. Maszyna Turinga rozpoznaje instrukcje po symbolu z taśmy i swoim stanie wewnętrznym. Jeśli w tablicy zabraknie dla tej kombinacji odpowiedniej instrukcji, to program zatrzymuje się.

W celu lepszego zrozumienia działania maszyny Turinga, rozważmy następujący program złożony z dwóch instrukcji:
 

Program
0,q0,1,q0,L bit 0 zamień na 1 1,q0,0,q0,L bit 1 zamień na 0

Co robi przedstawiony program? Zobaczmy. Załóżmy, iż taśma zawiera następujący ciąg symboli:
 

...

?

1

0

1

1

0

?

...

Symbolem pustym jest znak pytajnika. Dane do przetworzenia przez program zawarte są w kolejnych 5 komórkach - 10110. Powiedzmy, iż jest to jakaś wartość binarna.

Przed rozpoczęciem wykonywania programu ustawiamy głowicę na określonej komórce taśmy. W tym przypadku niech będzie to ostatni symbol 0:
 

...

?

1

0

1

1

0

?

...

Uruchamiamy maszynę Turinga i obserwujemy co się stanie:
 

Taśma z głowicą	Odczytany znak	Stan bieżący	Wykonywana operacja
? 1 0 1 1 0 ?	0	q0	Kombinacja odczytanego znaku i stanu q0 wyznacza instrukcję 0,q0,1,q0,L. Zatem znak w bieżącej komórce maszyna Turinga umieści symbol 1, stanu nie zmieni (wciąż pozostanie w q0) i przemieści głowicę do sąsiedniej komórki po lewej stronie.
? 1 0 1 1 1 ?	1	q0	Teraz kombinacja odczytanego znaku i stanu wewnętrznego wyznacza instrukcję 1,q0,0,q0,L. Znak w bieżącej komórce taśmy zostanie zastąpiony znakiem 0, stan wewnętrzny nie zmieni się i głowica będzie przesunięta w lewo do następnej komórki.
? 1 0 1 0 1 ?	1	q0	To samo, co powyżej, instrukcja 1,q0,0,q0,L.
? 1 0 0 0 1 ?	0	q0	Instrukcja 0,q0,1,q0,L..
? 1 1 0 0 1 ?	1	q0	Instrukcja 1,q0,0,q0,L
? 0 1 0 0 1 ?	?	q0	Takiej instrukcji nie zdefiniowaliśmy, zatem program się zakończy

Porównajmy stan taśmy przed i po wykonaniu programu:

Symbole 1 zostały zmienione na 0 i na odwrót, symbole 0 na 1. Zatem podany program dokonuje binarnej negacji bitów wejściowych (zmiany stanu bitów na przeciwny), 

		W przeciwieństwie do współczesnych komputerów, których program składa się z ciągu kolejno wykonywanych instrukcji, program dla maszyny Turinga jest tablicą instrukcji. Dla każdej pary symbolu wejściowego i stanu wewnętrznego określamy symbol wyjściowy, przejście do nowego stanu i ruch głowicy. Kolejność tych instrukcji w tablicy jest zupełnie dowolna. Maszyna Turinga napotykając na taśmie określony symbol i będąc w danym stanie wewnętrznym szuka w tablicy programu takiej właśnie pary i po znalezieniu wykonuje część operacyjną instrukcji. Jeśli program nie definiuje działania dla bieżącego symbolu wejściowego i stanu wewnętrznego, to maszyna Turinga kończy wykonywanie programu.

Źródło: mgr Jerzy Wałaszek