Составители:
20
Îñîáåííîñòüþ îïèñàíèÿ ìàøèíû Òüþðèíãà ÿâëÿåòñÿ òî, ÷òî ôóíê-
öèîíàëüíàÿ ñõåìà è ñòðóêòóðíàÿ ñõåìà, åå ðåàëèçóþùàÿ, ìîãóò áûòü
îòîæäåñòâëåíû, òàê êàê ñòðóêòóðíàÿ ñõåìà âñåãäà îäèíàêîâà äëÿ ëþ-
áîé ìàøèíû. Òàêèì îáðàçîì, ìàøèíû Òüþðèíãà îòëè÷àþòñÿ ðåàëèçóå-
ìîé ëîãè÷åñêîé ôóíêöèåé (Òüþðèíãîâîé ïðîãðàììîé), êîòîðàÿ ñóùåñòâóåò
èëè â âèäå ôóíêöèîíàëüíîé ñõåìû èëè â âèäå ñèñòåìû êîìàíä (∑
Ò
). Ïî-
ýòîìó òåðìèíû Ôóíêöèîíàëüíàÿ ñõåìà ÌÒ è Òüþðèíãîâà ïðîãðàì-
ìà ÿâëÿþòñÿ ñèíîíèìàìè.
Óäîáíåå ïîëüçîâàòüñÿ óïðîùåííîé çàïèñüþ Òüþðèíãîâûõ êîìàíä è
ôóíêöèîíàëüíûõ ñõåì, â êîòîðûõ íå çàïèñûâàþòñÿ âûõîäíûå ñèìâîëû
àëôàâèòà è íîâûå ñîñòîÿíèÿ, åñëè îíè íå ìåíÿþòñÿ, à òàêæå íå ôèêñè-
ðóåòñÿ çíàê Å, óêàçûâàþùèé íà îòñóòñòâèå ñäâèãà. Ýòî ïîçâîëÿåò â
òàáëèöå îïóñòèòü ñòîëáåö, ñîîòâåòñòâóþùèé ñòîï-ñîñòîÿíèþ, ñàìî
ñòîï-ñîñòîÿíèå îòìåòèòü çíàêîì ! , à â ñèñòåìå êîìàíä íåò íåîáõî-
äèìîñòè ôèêñèðîâàòü ïîñëåäíþþ êîìàíäó.
Íàïðèìåð, âìåñòî q2α→q2αR ìîæíî ïèñàòü q2α→R. Òîãäà óïðî-
ùåííàÿ ôóíêöèîíàëüíàÿ ñõåìà, ïðåäñòàâëåííàÿ íà ðèñ. 3.4, áóäåò èìåòü
âèä, ïîêàçàííûé íà ðèñ. 3.5.
 òàêîì ïðåäñòàâëåíèè áîëåå íàãëÿäåí ôàêò òîãî, ÷òî îêàçàâøèñü â
ñîñòîÿíèè q
1
ïðè îáîçðåâàåìîì çíàêå β, ìàøèíà íà÷èíàåò ñåðèþ ñäâè-
ãîâ âëåâî ñêâîçü âñå ðÿäîì ñòîÿùèå ñèìâîëû β, ïðè÷åì ñîäåðæàíèå
îáîçðåâàåìûõ ÿ÷ååê íå ìåíÿåòñÿ (îñòàåòñÿ β), äî òåõ ïîð ïîêà â ïîëå
çðåíèÿ ãîëîâêè íå ïîïàäåò êàêîé-ëèáî äðóãîé ñèìâîë. Òîëüêî ïðè ýòèõ
óñëîâèÿõ ìàøèíà Òüþðèíãà âûéäåò èç ñîñòîÿíèÿ q
1
.
3.4. Êîíôèãóðàöèÿ ìàøèíû Òüþðèíãà
Êîíôèãóðàöèåé (ïîëíûì ñîñòîÿíèåì èëè ìàøèííûì ñëîâîì) ìàøè-
íû Òüþðèíãà íàçûâàåòñÿ ñîâîêóïíîñòü åå ñëåäóþùèõ õàðàêòåðèñòèê:
q
q
q
!
q
"
λ
q
"
Rq
!
Lq
R L
q
α q
β q
R λ R
α
q
"
LR L
λ R
β
LR R
Ðèñ. 3.5
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
