Maszyna Turinga 3

Przykład 3:

W kolejnym przykładzie zobaczymy jak MT realizuje jeden z typowych algorytmów — wyszukiwanie elementu maksymalnego.

Musimy wzbogacić alfabet T o separator np. & na taśmie wejściowej:

MT = ({q, p. r, s, t}, {\. &}, <\_t #}. R. q. {q. p. r»

niewykorzystane

Oznacza, że niewykorzystana częsc zbioru jest pusta czyli nie bedzie wczytywał

R = {(q, \, #) — (q, \, lewo). (q, &.

#)

(p. #, prawo), (p.    \), (p. \, prawo), (p. @. #) —

(r, #. lewo), (r, \, \) —(r. \, lewo), (r, &. \) —(P. \. prawo), (r. \, #)

Znajdziemy teraz największy element w ciągu (3. 4, 2)

Moglibyśmy pominąć część stanów, a maszyna i tak rozwiąże ten problem, ale może nie rozwiązać innego — problem maszyny uniwersalnej.

	wczytanie pierwszej liczby wg pierwszego rozkazu — trzykrtnie		2-go rozkazu
(q, \\\ & \\\\ & W, #)	=*•	(q, &\\\\&\\,\\\^A#)	=*•
	4—ty rozkaz		trzykrotnie 5—ty rozkaz
(p,\\\\&\\, ^A#\\\)	=>	(r, \\\\ & W, ^A \\\)	=>
	4 razy 3—ci rozkaz		1 raz 4-y rozkaz
(p. W. \\\^\)	=*•	(p, W,^A #\\\\)

Zatem, jak należało oczekiwać największym elementem jest 4.

	trzykrotnie 3—ci rozkaz bez wczytywania
(p.WW&W.WM)	=*•
	1 raz 7-y rozkaz	3-y rozkaz
(r, \ & W, \\\^A #)	=£•	(r, & W, \\\\^A #j =*
	2 razy 5—ty rozkaz
(r, W, ^A \\\\)	=*•