Maszyna Turinga

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ą.

Alan Turing 1912-1954

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.

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 o stanach 0 i 1, 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:

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:

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:

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:

Uruchamiamy maszynę Turinga i obserwujemy co się stanie:

  ? 1 0 1 1 0 ?  

  ? 1 0 1 1 1 ? 

  ? 1 0 1 0 1 ? 

  ? 1 0 0 0 1 ? 

  ? 1 1 0 0 1 ?  

  ? 0 1 0 0 1 ? 

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)