46693

Instrukcją dla maszyny Turinga jest ciąg symboli:

Instrukcja maszyny Turinga	Znaczenia symboli
	s„	symbol odczytany przez głowicę z bieżącej komórki na taśmie
	qi	bieżący stan układu sterowania
(S„,qi,Sz,qj.L/P)	s.	symbol, jaki zostanie zapisany w bieżącej komórce na taśmie
	<li	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)

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

S_z, 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.

Przykład działania maszyny Turinga:

Zostaje wprowadzona instrukcja (stan) :A, qo, B, q₀, R

Działanie: jeżeli odczytanym przez głowicę symbolem z taśmy będzie literka A, a układ sterowania znajduje się w stanie qo, to głowica zamieni ten symbol na B, stan wewnętrzny nie zmieni się (pozostanie dalej qo), a głowica przesunie się do sąsiedniej komórki po prawej stronie. 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ąć glowicę.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ę.

Bibliografia :

www.ncurosoft.edu.pl/akozioro/Maszyna_Turinga.pdf

http://www. mimuw.edu.pl/-kubica/aug/frames-jfa-main-node 16.html

http://www.cioba.pl/al921/maszyna_turinga