Теория автоматов. Лупал А.М. - 16 стр.

16

Ëîãè÷åñêàÿ ôóíêöèÿ ìîæåò áûòü çàäàíà òàêæå ñ ïîìîùüþ ñèñòå-

ìû Òüþðèíãîâûõ êîìàíä (Σ

Ò

), êîòîðûå èìåþò âèä

q

i

s

j

′

d

k

,(1)

ñîîòâåòñòâóþùàÿ ôðàãìåíòó ôóíêöèîíàëüíîé ñõåìû, ïðåäñòàâëåííîé

2

s

2

→ q

L

.

Òüþðèíãà ñîîòâåòñòâóþò âåðøèíû (óçëû), à êîìàíäàì âèäà (1) ðåáðà,

âåäóùèå èç q

j

k.

Íà ðèñ. 3.3 ïðèâåäåí ôðàãìåíò äèàãðàììû ïåðåõîäîâ ìàøèíû Òüþ-

ðèíãà, ñîîòâåòñòâóþùèé ôðàãìåíòó ôóíêöèîíàëüíîé ñõåìû, ïðåäñòàâ-

ëåííîé íà ðèñ. 3.2.

Òàêèì îáðàçîì, ìàøèíà Òüþðèíãà ïðåäñòàâ-

ëÿåò ñîáîé ìàêñèìàëüíî óïðîùåííûé âàðèàíò âû-

÷èñëèòåëüíîé ìàøèíû, èìåþùåé îäíîàäðåñíóþ

ñòðóêòóðó, ñ âîçìîæíîñòüþ èçìåíåíèÿ àäðåñà îáî-

çðåâàåìîé ÿ÷åéêè òîëüêî íà 1. Ïîýòîìó íåîáõî-

äèìîå äëÿ ïðîöåññà âû÷èñëåíèé ñîäåðæàíèå êà-

êîé-ëèáî ÿ÷åéêè îòûñêèâàåòñÿ ïóòåì ïîñòåïåííîé ïðîâåðêè âñåõ ÿ÷ååê

}.

Ïåðåä íà÷àëîì ðàáîòû ìàøèíû Òüþðèíãà íà ëåíòó çàíîñèòñÿ íà-

÷àëüíàÿ èíôîðìàöèÿ (íàïðèìåð, ïÿòü åäèíèö) è ôèêñèðóåòñÿ íà÷àëüíàÿ

îáîçðåâàåìàÿ ÿ÷åéêà (íàïðèìåð, 4-ÿ), ñäâèã îòñóòñòâóåò. Èíôîðìàöèÿ

1

ìàøèíû Òüþðèíãà.