Symulator Maszyny Turinga


Inne rozdziały:

W rozdziale tym przedstawiamy bardzo prosty symulator maszyny Turinga opracowany w języku JavaScript. Pomimo tej prostoty pozwala on przetestować olbrzymią klasę algorytmów. Poniżej przedstawiamy szczegółową instrukcję obsługi tego programu.

 

Wprowadzanie danych na taśmę

MASZYNA TURINGA
(C)2004 mgr Jerzy Wałaszek, I LO w Tarnowie
TAŚMA Z GŁOWICĄ
 ? 0 1 1 1 1 0 0 1 0 1 ? ? ? ? ? ? ? ? ? ? ? ? ?

 

Aby wprowadzić dane na taśmę maszyny Turinga, kliknij myszką obszar taśmy. Ukaże się okienko dialogowe wprowadzania danych:


pic

 

W okienku tym wprowadź znaki, które zostaną rozmieszczone w kolejnych komórkach taśmy. Pierwszy znak definiuje wypełnienie komórek i najczęściej będzie to tzw. znak pusty. Po kliknięciu przycisku  OK  wprowadzone znaki pojawią się na taśmie. Jasny prostokąt oznacza głowicę zapisująco-odczytującą, którą program umieszcza nad komórką zawierającą pierwszy znak wprowadzonego tekstu. Jeśli położenie to ci nie odpowiada, to możesz je zmienić za pomocą dwóch przycisków  <   >  umieszczonych z boku taśmy.

W rzeczywistej maszynie Turinga taśma jest nieskończenie długa. U nas nie mogliśmy pozwolić sobie na taki luksus i długość taśmy została ograniczona do 100 komórek - dla większości przypadków jest to ilość zupełnie wystarczająca. Taśma zapętla się, tzn. po ostatniej komórce następuje pierwsza. Głowica może zatem płynnie przesuwać się w obu kierunkach.

 

Wprowadzanie programu

Program dla maszyny Turinga wprowadzamy w polu tekstowym umieszczonym na spodzie symulatora. Instrukcje muszą być wprowadzone poprawnie, aby zostały wykonane. Błędne instrukcje są ignorowane przez maszynę. Format każdej instrukcji jest następujący:

 

[znak odczytany z taśmy] [stan bieżący] [znak do zapisu na taśmę] [nowy stan] [kierunek ruchu głowicy] [dowolny tekst]

 

Poszczególne składniki muszą być rozdzielone przecinkami bez spacji - spacja może wystąpić w roli znaku dla taśmy. Inne użycie spacji odradzamy. Stan początkowy nazywa się q0. Pozostałe stany można nazywać w sposób dowolny - my stosujemy konsekwentnie nazwy q1, q2, q3..., jednak wy nie musicie się do tego stosować. Nazwy stanów mogą zawierać spacje, lecz odradzamy to rozwiązanie. Również nie stosujcie zbyt długich nazw.. Po zapisie pełnej instrukcji można umieszczać dowolny tekst, np. komentarz. Zawarte w poprzednim rozdziale programy są przykładami poprawnie skonstruowanych instrukcji dla naszej maszyny Turinga. Oto przykład:

 

Program
** Bit parzystości
** (C)2004 mgr Jerzy Wałaszek
** I LO w Tarnowie
************************************************
0,q0,0,q0,L bity 0 ignorujemy
1,q0,1,q1,L bity 1 uzupełniamy do parzystych
0,q1,0,q1,L bity 0 ignorujemy
1,q1,1,q0,L bity 1 uzupełniamy do parzystych
?,q0,0,q2,L zapisujemy wynikowy bit
?,q1,1,q2,L parzystości


Programy można wprowadzać za pomocą schowka. W tym celu zaznacz na stronie WWW odpowiedni tekst programu, skopiuj go do schowka, przejdź do edytora programu maszyny Turinga i wklej. W podobny sposób można ładować i zapisywać programy kopiując poprzez schowek do notatnika i zapisując jego zawartość do pliku na dysku. Rozwiązanie to wybraliśmy ze względu na prostotę i bezpieczeństwo - sam dbasz o to, co ma zostać zapisane i w którym miejscu na twoim dysku twardym.

 

Uruchamianie programu

Po wprowadzeniu programu do edytora można go uruchamiać. Maszyną sterujemy za pomocą czterech przycisków:

 

START

Przycisk ten uruchamia program w trybie ciągłym. Instrukcje będą kolejno wykonywane, aż do napotkania kombinacji znaku z taśmy i stanu wewnętrznego maszyny, który nie został zdefiniowany w tablicy instrukcji. W takim przypadku nastąpi zatrzymanie programu. Przed uruchomieniem programu należy określić zawartość taśmy oraz ustawić odpowiednio głowicę.

STOP

Wstrzymuje wykonywanie programu w trybie ciągłym. Po wstrzymaniu można zmodyfikować taśmę, ustawić głowicę i ponownie wznowić wykonywanie programu klikając na przycisk  START .

KROK

Oprócz trybu ciągłego programy można wykonywać instrukcja po instrukcji za pomocą tego przycisku. Każde kliknięcie powoduje wykonanie bieżącej instrukcji maszyny.

 

UKŁAD STEROWANIA GŁOWICĄ
znak
z taśmy
stan
bieżący
instrukcja do wykonania znak
na taśmę
nowy
stan
1 q0 1,q0,1,q1,L 1 q1

 

Rodzaj instrukcji wyświetlany jest w panelu sterowania głowicą umieszczonym poniżej taśmy. Kliknięcie przycisku  KROK  uruchomi pokazaną w tym panelu instrukcję. Pierwsze pole wyświetla znak, który odczytała głowica z taśmy. Drugie pole wyświetla nazwę bieżącego stanu wewnętrznego maszyny. Następnie widzimy instrukcję, która ma zostać wykonana dla tej kombinacji znaku z taśmy i stanu wewnętrznego. Pozostałe dwa pola wyświetlają kolejno znak, który instrukcja umieści w komórce wskazywanej przez głowicę oraz nowy stan wewnętrzny, w który przejdzie maszyna po wykonaniu tej instrukcji.

RESET

Jeśli poprzednio był uruchamiany program, to maszyna mogła zatrzymać się w stanie końcowym. W takim przypadku przed ponownym uruchomieniem konieczne jest wyzerowanie jej za pomocą tego przycisku.

 

Pod przyciskami symulator wyświetla różne teksty informujące o stanie maszyny lub wykonywanego przez nią programu.

 

Symulator

Po tym wstępie zapraszamy do skorzystania z naszego symulatora maszyny Turinga. Autor usilnie prosi o przesyłanie na adres naszego serwisu własnych programów dla maszyny Turinga. Pozwoli to wzbogacić prezentowany materiał.

 

MASZYNA TURINGA
(C)2004 mgr Jerzy Wałaszek, I LO w Tarnowie
TAŚMA Z GŁOWICĄ
.
UKŁAD STEROWANIA GŁOWICĄ
znak
z taśmy
stan
bieżący
instrukcja do wykonania znak
na taśmę
nowy
stan
. . . . .

.

 



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.