Wstęp


Inne rozdziały:

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

 

Budowa Maszyny Turinga

pic

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

 


Taśma

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.

 

Głowica

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.

 

Układ sterowania

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: q0, q1, q2, ... ,qn, gdzie q0 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)

 


S0
i qi 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ć?

Sz, qj 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, q0, B, q0, 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 q0, to głowica zamieni ten symbol na B, stan wewnętrzny nie zmieni się (pozostanie dalej q0), 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ę.

 

Program dla Maszyny Turinga

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:

 

... ? 1 0 1 1 0 ? ...
... ? 0 1 0 0 1 ? ...

 

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)

 

Zapamiętaj:

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.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.