Составители:
15
ñëîâà, ïðåäñòàâëåííûå â àëôàâèòå S). Âíóòðåííÿÿ ïàìÿòü ìàøèíû Òüþ-
ðèíãà ìîæåò áûòü ïðåäñòàâëåíà â âèäå äâóõ ÿ÷ååê: ÿ÷åéêè ñäâèãà D, â
êîòîðóþ çàíîñèòñÿ çíàê (íàïðàâëåíèå) ñäâèãà, è ÿ÷åéêè ñîñòîÿíèÿ Q,
îòîáðàæàþùåé òåêóùåå ñîñòîÿíèå ìàøèíû. Ýëåìåíòàðíûìè øàãàìè
ìàøèíû Òüþðèíãà ÿâëÿþòñÿ: ñ÷èòûâàíèå è çàïèñü ñèìâîëîâ, ñäâèã ãî-
ëîâêè íà ÿ÷åéêó âïðàâî èëè âëåâî, èëè, èíà÷å ãîâîðÿ, èçìåíåíèå àäðåñà
îáîçðåâàåìîé ÿ÷åéêè ëåíòû íà 1, ïåðåõîä ÓÓ â íîâîå ñîñòîÿíèå.
3.2. Äåòåðìèíèðîâàííîñòü ìàøèíû Òüþðèíãà
Ìàøèíà Òüþðèíãà îáëàäàåò ñâîéñòâîì äåòåðìèíèðîâàííîñòè, ò. å.
ïîñëåäîâàòåëüíîñòü åå øàãîâ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì.
Äëÿ ëþáîãî âíóòðåííåãî ñîñòîÿíèÿ q
i
è ñèìâîëà àëôàâèòà s
j
îäíî-
çíà÷íî çàäàíà ëîãè÷åñêàÿ ôóíêöèÿ, êîòîðàÿ îïðåäåëÿåò ñëåäóþùåå ñî-
ñòîÿíèå
′
i
q
; ñèìâîë
′
i
s
, êîòîðûé äîëæåí áûòü çàïèñàí; íàïðàâëåíèå ñäâè-
ãà ãîëîâêè d
k
Ì {L, R, E}, ãäå L ñäâèã âëåâî, R ñäâèã âïðàâî, Å
îòñóòñòâèå ñäâèãà; ïðè÷åì ìíîæåñòâî À = {L, R, E, q
1
, ..., q
m
} íàçûâàåò-
ñÿ âíóòðåííèì àëôàâèòîì ìàøèíû Òüþðèíãà.
Òàêèì îáðàçîì ëîãè÷åñêàÿ ôóíêöèÿ ìàøèíû Òüþðèíãà ñîïîñòàâëÿ-
åò êàæäîé ïàðå çíàêîâ (q
i
, s
j
) òðîéêó çíàêîâ (
′
i
s
,
′
i
q
, d
k
) è ìîæåò áûòü
çàïèñàíà ðàçíûìè ñïîñîáàìè.
Ïåðâûì ñïîñîáîì çàïèñè ëîãè÷åñêîé ôóíêöèè ÿâëÿåòñÿ ô óíêöè-
îíàëüíàÿ ñõåìà ìàøèíû Òüþðèíãà, ïðåäñòàâëÿþùåé ñîáîé
òàáëèöó, ñòðîêàì êîòîðîé ñîîòâåòñòâóþò âõîäíûå ñèìâîëû èç ìíîæå-
ñòâà S, ñòîëáöàì ñîñòîÿíèÿ èç ìíîæåñòâà Q, à íà ïåðåñå÷åíèè ñòðîê è
ñòîëáöîâ çàïèñàíà òðîéêà ñèìâîëîâ
′
i
q
′
i
s
d
k
. (ðèñ. 3.2).
Ðèñ. 3.2
q
1
q
2
q
3
…q
r
s
1
s
2
q
8
s
7
L
s
3
…
s
k
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
