Ãëàâíàÿ > Ðàçíîå > Ýíöèêëîïåäèÿ êèáåðíåòèêè. Ò.1
<< Ïðåäûäóùèé ïàðàãðàô
Ñëåäóþùèé ïàðàãðàô >>
<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Ìàêåòû ñòðàíèö

ÀÂÒÎÌÀÒÛ ÁÅÑÊÎÍÅ×ÍÛÅ

— àâòîìàòû, ì-âî ñîñòîÿíèé êîòîðûõ ÿâëÿåòñÿ áåñêîíå÷íûì. Ôîðìàëüíî À. -ýòî ïÿòåðêà , ãäå X è Ó — ñîîòâåòñòâåííî âõîäíîé è âûõîäíîé àëôàâèòû (îíè ìîãóò áûòü êàê êîíå÷íûìè, òàê è áåñêîíå÷íûìè), À — ìí-âî ñîñòîÿíèé àâòîìàòà (áåñêîíå÷íîå), - ô-öèÿ ïåðåõîäîâ è ê: Ó — ô-öèÿ âûõîäîâ àâòîìàòà. ×àùå âñåãî ðàññìàòðèâàþòñÿ À. á. ñ êîíå÷íûìè âõîäíûì è âûõîäíûì àëôàâèòàìè è ñ÷åòíûì ìí-âîì âíóòð. ñîñòîÿíèé. Äëÿ êëàññà âñåõ À. á. åùå íå óäàëîñü ïîëó÷èòü çíà÷èòåëüíûõ ðåçóëüòàòîâ, ÷òî îáúÿñíÿåòñÿ ÷ðåçìåðíîé îáùíîñòüþ ïîíÿòèÿ À. á. Òàêèå ðåçóëüòàòû èìåþòñÿ äëÿ îòäåëüíûõ ñïåöèàëüíî âûäåëåííûõ êëàññîâ À. á. Âûäåëåíèå ýòèõ êëàññîâ À. á. èäåò, â îñíîâíîì, ïî äâóì íàïðàâëåíèÿì: à) àâòîìàò ðàññìàòðèâàåòñÿ êàê àáñòðàêòíûé àâòîìàò, ò. å. ïÿòåðêà , ãäå ìí-âî À ÿâëÿåòñÿ íåêîòîðîé ìàòåì. ñòðóêòóðîé (ïî Í. Áóðáàêè), íàïð., ïðîñòðàíñòâîì ëèíåéíûì, òîïîëîãè÷åñêèì, ìåòðè÷åñêèì, ãðóïïîé è ò. ï., à ô-öèè è ê ÿâëÿþòñÿ íåêîòîðûìè åñòåñòâåííî îïðåäåëÿåìûìè â ýòèõ òåðìèíàõ ô-öèÿìè èëè îïåðàòîðàìè, íàïð., îïåðàòîðàìè ëèíåéíûìè; á) àâòîìàò çàäàåòñÿ â ñòðóêòóðíîì âèäå, ò. å. êàê àâòîìàò, ðåàëèçîâàííûé â òîé èëè èíîé ñåòè ëîãè÷åñêîé. Ñòðóêòóðà ëîãè÷. ñåòè è åå ýëåìåíòû îïðåäåëÿþò ñòðóêòóðó ìí-âà À è îïåðàöèé 8 è 1. Òàêîå âûäåëåíèå êëàññîâ À. á. ÿâëÿåòñÿ ïðåîáëàäàþùèì â èññëåäîâàíèÿõ ïî òåîðèè À. á. À. á., çàäàííûå â ñòðóêòóðíîì âèäå, ÷àñòî íàç. àáñòðàêòíûìè ìàøèíàìè (íàïð., Òüþðèíãà ìàøèíà). Èçó÷àþò èõ â ñâÿçè ñ âîçìîæíîñòüþ âûïîëíåíèÿ íà íèõ òåõ èëè èíûõ êëàññîâ àëãîðèòìîâ. Ñ÷èòàþò, ÷òî ñàìî ïîíÿòèå àëãîðèòìà ìîæåò áûòü óòî÷íåíî òîëüêî íà îñíîâå ïîíÿòèÿ À. á. (ñì. Àâòîìàòû ðàñòóùèå). Õîòÿ âñå ðåàëüíûå äèñêðåòíûå óñòð-âà, ïðåäíàçíà÷åííûå äëÿ ïåðåðàáîòêè èíôîðìàöèè, ìîãóò èìåòü òîëüêî êîíå÷íîå ÷èñëî âíóòð. ñîñòîÿíèé, ò. å. èõ àáñòðàêòíûìè ìîäåëÿìè ÿâëÿþòñÿ àâòîìàòû êîíå÷íûå, òåì íå ìåíåå áûâàåò óäîáíî ðàññìàòðèâàòü îäèí À. á. êàê ìîäåëü öåëîãî êëàññà òàêèõ óñòðîéñòâ. Ýòî ïîçâîëÿåò âûÿâèòü îáùèå çàêîíîìåðíîñòè, èìåþùèå ìåñòî äëÿ âñåõ òàêèõ óñòð-â, è çà÷àñòóþ èìååò áîëüøîå ïðèêëàäíîå çíà÷åíèå. Ïðèìåðîì ìîãóò ñëóæèòü àâòîìàòû ðåãèñòðîâûå.

À- á. øèðîêî èçó÷àþò â òåîð. êèáåðíåòèêå, â àëãîðèòìîâ òåîðèè, ëèíãâèñòèêå ìàòåìàòè÷åñêîé è äð.

Ëèò.: Ãëóøêîâ Â. Ì. Òåîðèÿ àâòîìàòîâ è âîïðîñû ïðîåêòèðîâàíèÿ ñòðóêòóð öèôðîâûõ ìàøèí. «Êèáåðíåòèêà», 1965, Ml; Ìàëüöåâ À. È. Àëãîðèòìû è ðåêóðñèâíûå ôóíêöèè. Ì., 1965 [áèáëèîãð. ñ. 375—381]; Arbib Ì. A. Automata theory and control theory - a rapprochement. «Automatica», 1966, v. 3; Hîpñãîft J. E., Oilman J. D. An approach to a unified theory of automata. «The bell system technical journal», 1967, v. 46, ¹ 8.

Ì. È. Êðàòêà.

<< Ïðåäûäóùèé ïàðàãðàô Ñëåäóþùèé ïàðàãðàô >>
Îãëàâëåíèå