To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Maszyna Turinga Maszyna Turinga była jednym z pierwszych modeli komputera, a dokładniej ideą, która w latach późniejszych miała posłużyć przy konstruowaniu komputerów. Jest twórcą jest Alan Turing, wybitny angielski matematyk, który pod koniec lat trzydziestych ubiegłego wieku na potrzeby swoich badań nad problemami obliczalności opracował model maszyny, którego celem było analizowanie algorytmów.
Maszyna Turinga zbudowana jest z trzech głównych elementów:
Nieskończonej taśmy podzielonej na komórki w których znajdują się symbole.
Odpowiednikiem takiej taśmy jest obecnie pamięć komputera, natomiast symbole znajdujące się w komórkach odpowiadają danym wejściowym.
Ruchomej głowicy zapisująco-odczytującej.
Jej zadaniem jest przetwarzanie taśmy. Głowica musi znajdować się nad jedną z komórek. W przypadku przetwarzania (modyfikacji) wartości znajdującej się w danej komórce, najpierw odczytuje symbol znajdujący się w niej, a następnie zamienia go na inny. Jej funkcja może się ograniczyć również jedynie do odczytu symbolu z komórki. Głowica ma możliwość poruszania się po taśmie w lewo lub prawo, w dowolne miejsce, do dowolnej komórki. Przy rozpoczęciu pracy maszyny Turinga, głowica ustawiana jest nad pierwszą komórką, której symbol ma zostać zmodyfikowany lub odczytany.
Ruchoma głowica odpowiada dzisiejszym urządzeniom wejścia-wyjścia lub układom odczytu i zapisu pamięci.
Układu sterowania głowicą.
Układ sterowania zarządza przetwarzaniem informacji, odczytuje za pomocą głowicy symbole z komórek taśmy oraz przesyła do głowicy symbole do zapisu w komórkach. Odpowiada również za zlecenie głowicy przemieszczenia się do sąsiedniej komórki (w lewo lub w prawo).
Odpowiednikiem układu sterowania w komputerach jest procesor.
Podstawą działania maszyny Turinga są stany układu sterowania. Określają one jednoznacznie jaką operację wykona i jak zareaguje maszyna Turinga, gdy odczyta z taśmy określony symbol. Operacje wykonywane przez układ sterowania zależą więc od dwóch czynników: Symbolu odczytanego z komórki na taśmie i bieżącego stanu układu sterującego. Przykładowe stany zostaną oznaczone jako q 0 , q 1 , q 2 , ... ,q n , gdzie q 0 jest stanem początkowym, w którym znajduje się maszyna Turinga przed rozpoczęciem przetwarzania symboli na taśmie.
Instrukcją dla maszyny Turinga jest ciąg symboli:
Instrukcja maszyny Turinga
Znaczenia symboli
(S o ,q i ,S z ,q j ,L/P)
S o symbol odczytany przez głowicę z bieżącej komórki na taśmie
q i bieżący stan układu sterowania
S
... zobacz całą notatkę
Komentarze użytkowników (0)