Serwis Edukacyjny w I-LO w Tarnowie ![]() Materiały dla uczniów liceum |
Autor artykułu: mgr Jerzy Wałaszek |
©2021 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
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:
![]() |
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.
←... | 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 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:
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ę.
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. |
![]() |
Zespół Przedmiotowy |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.