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

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

13
3. ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀ
 1937 ãîäó àíãëèéñêèé ìàòåìàòèê À.Ì. Òüþðèíã, êîòîðûé áûë ïîñ-
ëåäîâàòåëåì òåîðèè î òîì, ÷òî ìàøèíà ñïîñîáíà ìûñëèòü è ñ åå ïîìî-
ùüþ ìîæíî ñìîäåëèðîâàòü ïñèõè÷åñêóþ äåÿòåëüíîñòü ÷åëîâåêà, ïðåä-
ëîæèë îáùóþ è âìåñòå ñ òåì î÷åíü ïðîñòóþ êîíöåïöèþ âû÷èñëèòåëü-
íîé ìàøèíû. Â ñâîåì òðóäå Òüþðèíã èñõîäèë èç òîãî, ÷òî ïðåäëàãàå-
ìàÿ èì âû÷èñëèòåëüíàÿ ìàøèíà óïîäîáëÿåòñÿ âû÷èñëèòåëþ, êîòîðûé
âûïîëíÿåò îïåðàöèè â òî÷íîì ñîîòâåòñòâèè ñ íåêîòîðûì ñòðîãèì îïè-
ñàíèåì. Ðàáîòà ìàøèíû Òüþðèíãà íàïîìèíàåò äåéñòâèÿ âû÷èñëèòåëÿ,
êîòîðûé, áóäó÷è íå â ñîñòîÿíèè ñðàçó îáîçðåòü âñþ, ÷àñòî î÷åíü ãðî-
ìîçäêóþ ñèñòåìó äàííûõ è ïðåäïèñàíèé, ïðîèçâîäèò êàæäûé ðàç ëèøü
êàêîå-ëèáî ýëåìåíòàðíîå äåéñòâèå, ïðè÷åì òîëüêî íàä íåêîòîðîé âîñ-
ïðèíèìàåìîé èì ÷àñòüþ äàííûõ (èëè ïðîìåæóòî÷íûõ ðåçóëüòàòîâ).
Íà ñëåäóþùåì ýòàïå îí ëèáî ïðîäîëæàåò âîñïðèíèìàòü òó æå ÷àñòü
äàííûõ, ëèáî ïåðåõîäèò ê äðóãîé ÷àñòè, íàõîäÿùåéñÿ ðÿäîì ñ íåé.
3.1. Ñòðóêòóðà ìàøèíû
Ìàøèíó Òüþðèíãà ìîæíî ïðåäñòàâèòü ñîñòîÿùåé èç íåñêîëüêèõ îñ-
íîâíûõ áëîêîâ.
1. Óïðàâëÿþùåå óñòðîéñòâî (ÓÓ), êîòîðîå ìîæåò áûòü íàñòðîåíî
íà âûïîëíåíèå îäíîé èç ìíîæåñòâà âîçìîæíûõ îïåðàöèé èëè, êàê ïðè-
íÿòî ãîâîðèòü, ìîæåò íàõîäèòüñÿ â îäíîì èç ñîñòîÿíèé, îáðàçóþùèõ
êîíå÷íîå ìíîæåñòâî Q = {q
1
, q
2
, ..., q
n
}.
Ñðåäè ñîñòîÿíèé ÓÓ ìîãóò áûòü âûäåëåíû íà÷àëüíîå ñîñòîÿíèå q
1
è êîíå÷íîå (ïàññèâíîå) ñîñòîÿíèå q
z
⊂ {q
1
, ..., q
n
}. Â q
1
ìàøèíà Òüþðèí-
ãà íàõîäèòñÿ ïåðåä íà÷àëîì ðàáîòû, à, ïîïàâ â q
z
,
îíà îñòàíàâëèâàåòñÿ.
Î÷åâèäíî, âñå ñîñòîÿíèÿ èç ìíîæåñòâà Q, îòëè÷íûå îò q
z
, ÿâëÿþòñÿ
àêòèâíûìè.
Ðàáîòà ìàøèíû Òüþðèíãà ïðîèñõîäèò â äèñêðåòíîì âðåìåíè, êîãäà
ñîñòîÿíèÿ ìàøèíû ðàññìàòðèâàþòñÿ íà êîíå÷íîì ìíîæåñòâå âðåìåí-
íûõ îòñ÷åòîâ, íàçûâàåìûõ òàêòàìè ìàøèííîãî âðåìåíè è îáîçíà÷àå-
ìûõ t
1
, t
2
, ..., t
p
, ... .
2. Ëåíòà, ðàçáèòàÿ íà ÿ÷åéêè, â êàæäîé èç êîòîðûõ ìîæåò áûòü çàïè-
ñàí îäèí èç ñèìâîëîâ êîíå÷íîãî âíåøíåãî àëôàâèòà S = {s
1
, s
2
, ..., s
m
}.
Ñèìâîëàìè ýòîãî àëôàâèòà êîäèðóþòñÿ êàê ñâåäåíèÿ, ïîäàâàåìûå â
ìàøèíó, òàê è òå ñâåäåíèÿ, êîòîðûå â íåé âûðàáàòûâàþòñÿ. Ñðåäè çíà-
êîâ âíåøíåãî àëôàâèòà èìååòñÿ ïóñòîé ñèìâîë (ïðîáåë) λ. Ïîñûëêà

Страницы