Составители:
13
2. ÀËÃÎÐÈÒÌÈ×ÅÑÊÀß ÏÎËÍÎÒÀ
È ÐÅÀËÈÇÀÖÈß ÂËÎÆÅÍÍÛÕ ÖÈÊËÎÂ
2.1. Ïðîáëåìà àëãîðèòìè÷åñêîé ïîëíîòû AC
Íåîáõîäèìûì óñëîâèåì ïðèìåíåíèÿ ëþáîãî ôîðìàëèçìà, èñïîëüçó-
åìîãî äëÿ ðåøåíèÿ çàäà÷ ìîäåëèðîâàíèÿ è âû÷èñëåíèé ÿâëÿåòñÿ óñëî-
âèå àëãîðèòìè÷åñêîé ïîëíîòû. Èçâåñòíî, ÷òî ïîíÿòèå àëãîðèòìà íå
ôîðìàëèçîâàíî è èìååò îïèñàòåëüíûé õàðàêòåð. Ïîä àëãîðèòìîì â èí-
òóèòèâíîì ñìûñëå ïîíèìàåòñÿ òî÷íîå ïðåäïèñàíèå èëè íàáîð îáùåïî-
íÿòíûõ ïðàâèë, âåäóùèõ îò âàðüèðóåìûõ èñõîäíûõ äàííûõ ê èñêîìî-
ìó ðåçóëüòàòó [9]. Ïîïûòêè óòî÷íèòü ïîíÿòèå àëãîðèòìà ïðèâåëè ê
ðàçðàáîòêå ôîðìàëüíûõ ìîäåëåé, ê êîòîðûì îòíîñÿòñÿ ìàøèíû Òüþ-
ðèíãà, ïðèìèòèâíî-ðåêóðñèâíûå ôóíêöèè, íîðìàëüíûé àëãîðèòì Ìàð-
êîâà, ëîãè÷åñêèå ñõåìû ñòðóêòóðíîãî ïðîãðàììèðîâàíèÿ Ãëóøêîâà-
Äåéêñòðû [9–12]. Ýêâèâàëåíòíîñòü ôîðìàëüíûõ ìîäåëåé àëãîðèòìîâ
îòíîñèòåëüíî ðåøàåìûõ çàäà÷ ìîæåò áûòü ñòðîãî äîêàçàíà [4, 12], îä-
íàêî îáùèé êëàññ çàäà÷, ðåøàåìûõ ëþáîé èç ôîðìàëüíûõ ìîäåëåé, ñòðî-
ãî îïðåäåëåí áûòü íå ìîæåò. Îöåíêè âû÷èñëèòåëüíûõ âîçìîæíîñòåé
ìîäåëåé àëãîðèòìîâ îñíîâûâàþòñÿ íà ãèïîòåçàõ, èçâåñòíûõ êàê òåçèñ
×åð÷à, òåçèñ Òüþðèíãà, ïðèíöèï íîðìàëèçàöèè àëôàâèòíîãî àëãîðèò-
ìà â ñîîòâåòñòâèè ñ êîòîðûìè êëàññ çàäà÷, ðåøàåìûõ ëþáîé èç ôîð-
ìàëüíûõ ìîäåëåé, âêëþ÷àåò âñå çàäà÷è, êîòîðûå ìîãóò áûòü ðåøåíû
“èíòóèòèâíî àëãîðèòìè÷åñêèìè” ìåòîäàìè. Ýòî óòâåðæäåíèå ÿâëÿåòñÿ
îáùåïðèçíàííûì, õîòÿ è íå ìîæåò áûòü ñòðîãî äîêàçàíî [4].
Èñõîäÿ èç ìîäåëè íîðìàëüíîãî àëãîðèòìà Â.Ì.Ãëóøêîâ ââåë ïî-
íÿòèå àâòîìàòíîãî îòîáðàæåíèÿ [10] è ïîêàçàë, ÷òî ëþáîå îäíîçíà÷-
íîå àëôàâèòíîå îòîáðàæåíèå ìîæåò áûòü ïðèâåäåíî ê àâòîìàòíîìó
âèäó, ò.å. äëÿ ëþáîãî îäíîçíà÷íîãî àëôàâèòíîãî îïåðàòîðà ìîæåò
áûòü ïîñòðîåí èíäóöèðóþùèé åãî àâòîìàò. Ëåãêî ïîêàçàòü [4], ÷òî ñ
ïîìîùüþ îïåðàòîðîâ àëãîðèòìè÷åñêîãî áàçèñà AC ìîãóò áûòü ðåàëè-
çîâàíû ëîãè÷åñêèå îïåðàöèè, îáðàçóþùèå ïîëíóþ ñèñòåìó (ðèñ. 3).  ñî-
âîêóïíîñòè ñ îïåðàòîðîì çàäåðæêè ýòî ïîçâîëÿåò ïîñòðîèòü ëþáîé
êîíå÷íûé àâòîìàò.
Ñðàâíèì AC ñ äðóãèì ýôôåêòèâíûì ÿçûêîì ïðåäñòàâëåíèÿ âû÷èñ-
ëèòåëüíûõ àëãîðèòìîâ – ÿçûêîì ãðàôè÷åñêèõ ñõåì [11]. Óíèâåðñàëü-
íîñòü ÿçûêà ãðàôè÷åñêèõ ñõåì ïîäòâåðæäàåòñÿ òåì, ÷òî íà íåì ìîãóò
áûòü ïðåäñòàâëåíû ìàøèíà Òüþðèíãà, ìàøèíà ñ íåîãðàíè÷åííûìè ðå-
ãèñòðàìè, íîðìàëüíûé àëãîðèòì Ìàðêîâà [11], ò. å. îáúåêòû, êîòîðûå
èñïîëüçóþòñÿ â êà÷åñòâå ôîðìàëüíûõ ìîäåëåé àëãîðèòìîâ. Íà ÿçûêå
ãðàôè÷åñêèõ ñõåì ñóùåñòâóþò òðè áàçîâûå ëîãè÷åñêèå ñòðóêòóðû, ñ ïî-
Страницы
- « первая
- ‹ предыдущая
- …
- 11
- 12
- 13
- 14
- 15
- …
- следующая ›
- последняя »
