1610906281-974acaa5ee9a7bc9236c4fe86efeeea8 (824379)
Текст из файла
Ãëàâà 1ÌèíèìàøèíûÌèíèìàøèíà (ÌÌ), èíîãäà íàçûâàåìàÿ çäåñü ïðîñòî ìàøèíîé, èìååò• áåñêîíå÷íîå ñåìåéñòâî îñíîâíûõ ðåãèñòðîâ R0 , R1 , R2 . . .,• áåñêîíå÷íîå ñåìåéñòâî âñïîìîãàòåëüíûõ ðåãèñòðîâ S0 , S1 , S2 . . .,• êîìàíäíûé ðåãèñòð (èëè ðåãèñòð êîìàíä) ÊЕ ïðîãðàììó, ïðåäñòàâëÿþùóþ ñîáîé (âîçìîæíî ïóñòîé) ñïèñîê êîìàíä, ïðîíóìåðîâàííûõ ïîñëåäîâàòåëüíûìè ÷èñëàìè, íà÷èíàÿ ñ 0:0: Êîìàíäà01: Êîìàíäà1···k: ÊîìàíäàkÂñå âûøåóïîìÿíóòûå ðåãèñòðû Ri , Si è ÊÐ ïðåäíàçíà÷åíû äëÿ õðàíåíèÿ íàòóðàëüíûõ ÷èñåë.  ëþáîé ìîìåíò âðåìåíè â êàæäîì ðåãèñòðåçàïèñàíî ðîâíî îäíî ÷èñëî.Èìååòñÿ øåñòü ëåãêî çàïîìèíàåìûõ òèïîâ êîìàíä, åñòåñòâåííî ðàçäåë¼ííûõ íà 3 ãðóïïû, îïèñàíèå êîòîðûõ ïðèâåäåíî â ñëåäóþùåé òàáëèöå.12Ãëàâà 1.G:=mG:=Hinc Gdec Hif F=0 goto mgoto mÌèíèìàøèíûÊîìàíäû ïðèñâàèâàíèÿçàïèñûâàåò â ðåãèñòð G íàòóðàëüíîå ÷èñëî m èóâåëè÷èâàåò ñîäåðæèìîå ðåãèñòðà êîìàíä íà 1(ò.å., ÌÌ ïåðåõîäèò ê èñïîëíåíèþ ñëåäóþùåéïî ñïèñêó êîìàíäû)çàïèñûâàåò â ðåãèñòð G çíà÷åíèå, ñîäåðæàùååñÿâ ðåãèñòðå H, è óâåëè÷èâàåò ñîäåðæèìîå ðåãèñòðà êîìàíä íà 1Àðèôìåòè÷åñêèå êîìàíäûóâåëè÷èâàåò ñîäåðæèìîå ðåãèñòðà G íà 1 è óâåëè÷èâàåò ñîäåðæèìîå ðåãèñòðà êîìàíä íà 1óìåíüøàåò ñîäåðæèìîå ðåãèñòðà H íà 1, åñëèîíî áîëüøå íóëÿ, è óâåëè÷èâàåò ñîäåðæèìîå ðåãèñòðà êîìàíä íà 1Êîìàíäû ïåðåõîäàåñëè ñîäåðæèìîå ðåãèñòðà F ðàâíî 0, òî çàíîñèòâ êîìàíäíûé ðåãèñòð ÷èñëî m, â ïðîòèâíîì ñëó÷àå óâåëè÷èâàåò çíà÷åíèå êîìàíäíîãî ðåãèñòðàíà 1çàíîñèò â ðåãèñòð êîìàíä ÷èñëî mÎ÷åâèäíî, ÷òî ëþáàÿ ìèíèìàøèíà ïîëíîñòüþ çàäà¼òñÿ ñâîåé ïðîãðàììîé, è ïîýòîìó èìååò ñìûñë ïðîñòî îòîæäåñòâëÿòü ìèíèìàøèíûèõ ñ ïðîãðàììàìè.Ïåðåä íà÷àëîì ðàáîòû ìèíèìàøèíû â å¼ îñíîâíûå è âñïîìîãàòåëüíûå ðåãèñòðû çàíîñÿòñÿ íåêîòîðûå èñõîäíûå äàííûå íàòóðàëüíûå ÷èñëà, à â ðåãèñòð ÊÐ çàíîñèòñÿ ÷èñëî 0.
Ìèíèìàøèíà ðàáîòàåò, ïîñëåäîâàòåëüíî èñïîëíÿÿ øàãè. Øàã ðàáîòû ìàøèíû ñîñòîèò â âûïîëíåíèèêîìàíäû, íîìåð êîòîðîé â äàííûé ìîìåíò çàïèñàí â ÊÐ â ñîîòâåòñòâèèñ âûøåîïèñàííîé èíñòðóêöèåé. Âûïîëíèâ øàã, ìèíèìàøèíà ïåðåõîäèòê ñëåäóþùåìó øàãó è ò.ä.  ñëó÷àå, êîãäà â ÊÐ îêàæåòñÿ ÷èñëî, íå ÿâëÿþùååñÿ íîìåðîì êàêîéëèáî êîìàíäû èç ïðîãðàììû, ìàøèíà çàâåðøàåòñâîþ ðàáîòó è îñòàíàâëèâàåòñÿ.Îòìåòèì, ÷òî êîìàíäû ïåðåõîäà ìîãóò îñóùåñòâëÿòü êàê ïåðåõîä êâûïîëíåíèþ êîíêðåòíûõ êîìàíä òàê è îñòàíîâêó ðàáîòû ìàøèíû â ñëó÷àå, êîãäà êîìàíäà ñ ñîîòâåòñòâóþùèì íîìåðîì îòñóòñòâóåò.Çàìåòèì, ÷òî êàæäàÿ ïðîãðàììà ìîæåò èçìåíÿòü çíà÷åíèÿ òîëüêî âòåõ ðåãèñòðàõ, êîòîðûå ÿâíî óïîìÿíóòû â å¼ òåêñòå.
Çíà÷åíèÿ â îñòàëü-3íûõ ðåãèñòðàõ îíà èçìåíèòü íå ìîæåò.Ñ êàæäîé ÌÌ P è íàòóðàëüíûì ÷èñëîì n ìîæíî ñâÿçàòü ôóíêöèþnAP : Nn → N, çíà÷åíèå êîòîðîé íà x1 , . . . , xn îïðåäåëÿåòñÿ ñëåäóþùèìîáðàçîì:çàíîñèì â ðåãèñòðû R1 , . . . , Rn ñîîòâåòñòâåííî çíà÷åíèÿ x1 ,. . ., xn , âî âñå îñòàëüíûå ðåãèñòðû çàíîñèì íóëè, â ÊÐ çàíîñèì 0 è çàïóñêàåì ïðîãðàììó P . Êîãäà ìàøèíà çàâåðøèòñâîþ ðàáîòó (îñòàíàâëèâàåòñÿ), çíà÷åíèå ôóíêöèè AnP (x1 , . . . , xn )âîçüì¼ì èç ðåãèñòðà R0 .
Åñëè ìàøèíà íèêîãäà íå çàâåðøèòñâîþ ðàáîòó, òî ýòî çíà÷åíèå ñ÷èòàåòñÿ íåîïðåäåë¼ííûì.Çàìåòèì, ÷òî ñîäåðæèìîå ðåãèñòðîâ, íå óïîìÿíóòûõ â ïðîãðàììå (çàèñêëþ÷åíèåì R0 ), íå èñïîëüçóåòñÿ ýòîé ïðîãðàììîé è íå âëèÿåò íà ðåçóëüòàò ðàáîòû ýòîé ïðîãðàììû ñîäåðæèìîå ðåãèñòðà R0 â êîíöå å¼ðàáîòû.Îïðåäåëåíèå 1.0.1 ×àñòè÷íàÿ ôóíêöèÿ èç Nn â N íàçûâàåòñÿ âû÷èñ-ëèìûîé íà ìèíèìàøèíå, åñëè îíà ñîâïàäàåò ñ ôóíêöèåé âèäà AnP , äëÿïîäõîäÿùåé ïðîãðàììû P .Ïðèâåä¼ì ïðèìåð ïðîñòîé ïðîãðàììû, âû÷èñëÿþùåé ñóììó ÷èñåë(ïðåäëàãàåì ÷èòàòåëþ ñàìîñòîÿòåëüíî óáåäèòüñÿ â ýòîì):0:1:2:3:4:R0 :=R1if R2 =0 goto 5dec R2inc R0goto 1Òàêèì îáðàçîì, ñëîæåíèå íàòóðàëüíûõ ÷èñåë ÿâëÿåòñÿ áèíàðíîé ôóíêöèåé, âû÷èñëèìîé íà ÌÌ. äàëüíåéøåì äëÿ íàñ áóäåò âàæíåå äîêàçûâàòü ñóùåñòâîâàíèå ïðîãðàìì äëÿ âû÷èñëåíèÿ îïðåäåëåííûõ ôóíêöèé, ÷åì ïîëó÷àòü èõ êîíêðåòíûé òåêñò. Äëÿ îáëåã÷åíèÿ òàêèõ äîêàçàòåëüñòâ ìû áóäåì èñïîëüçîâàòü òàê íàçûâàåìûå ðàñøèðåííûå ìèíèìàøèíû (ÐÌÌ).
Îíè îòëè÷àþòñÿ îò ìèíèìàøèí òîëüêî òåì, ÷òî â ïðîãðàììàõ äëÿ ýòèõ ìàøèí êðîìå îáû÷íûõ êîìàíä ðàçðåøåíî èñïîëüçîâàòü äîïîëíèòåëüíûå êîìàíäûâèäà H:=f (H1 ,...,Hk ), äëÿ ïðîèçâîëüíûõ (âîîáùå ãîâîðÿ, ÷àñòè÷íûõ)4Ãëàâà 1.Ìèíèìàøèíûôóíêöèé f . Èñïîëíåíèå òàêîé êîìàíäû ñîñòîèò â âû÷èñëåíèè çíà÷åíèÿf íà çíà÷åíèÿõ ðåãèñòðîâ H1 , . .
. , Hk , ïîìåùåíèè ðåçóëüòàòà â ðåãèñòð Hñ ïîñëåäóþùèì óâåëè÷åíèåì çíà÷åíèÿ ÊÐ íà 1. Çíà÷åíèÿ âñåõ îñòàëüíûõ ðåãèñòðîâ ðàñøèðåííîé ìàøèíû ïðè ýòîì íå èçìåíÿþòñÿ. Åñëè fíå îïðåäåëåíà íà äàííûõ çíà÷åíèÿõ, òî ñ÷èòàåòñÿ, ÷òî âû÷èñëåíèå çíà÷åíèÿ f ïðîäîëæàåòñÿ áåñêîíå÷íî, è ïðè ýòîì, ðàçóìååòñÿ, ðàñøèðåííàÿìàøèíà, âûïîëíÿþùàÿ ýòó êîìàíäó, íèêîãäà íå çàâåðøèò ñâîþ ðàáîòó.Ëåãêî çàìåòèòü, ÷òî ìèíèìàøèíû ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ðàñøèðåííûõ ìèíèìàøèí.Îïðåäåëåíèå 1.0.2 Äâå ðàñøèðåííûõ ìèíèìàøèíû íàçîâ¼ì ýêâèâà-ëåíòíûìè, åñëè, áóäó÷è çàïóùåíûìè ñ ëþáûìè îäèíàêîâûìè íàáîðàìèçíà÷åíèé îñíîâíûõ ðåãèñòðîâ è íóëåâûìè çíà÷åíèÿìè âñåõ âñïîìîãàòåëüíûõ ðåãèñòðîâ, îíè ëèáî îáå íèêîãäà íå çàâåðøàò ñâîþ ðàáîòó ëèáî îáå êîãäàíèáóäü çàâåðøàò ñâîþ ðàáîòó è ïîñëå ýòîãî çíà÷åíèÿ âîâñåõ îñíîâíûõ ðåãèñòðàõ ó íèõ ñîâïàäóò.Îïðåäåëåíèå ôóíêöèé, âû÷èñëèìûõ íà ÐÌÌ ôîðìóëèðóåòñÿ àíàëîãè÷íûì îáðàçîì.Ïðåäëîæåíèå 1.0.3 (Ýëèìèíàöèÿ1 äîïîëíèòåëüíûõ êîìàíä) Åñëèâñå ôóíêöèè, ó÷àñòâóþùèå â ðàñøèðåííûõ êîìàíäàõ íåêîòîðîé ðàñøèðåííîé ìèíèìàøèíû, âû÷èñëèìû íà ìèíèìàøèíàõ, òî ýòà ðàñøèðåííàÿ ìàíèìàøèíà ýêâèâàëåíòíà íåêîòîðîé îáû÷íîé ìèíèìàøèíå.Äîêàçàòåëüñòâî.
Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íî óêàçàòü ìåòîä ïðåîá-ðàçîâàíèÿ ëþáîé ïðîãðàììû äëÿ ÐÌÌ â ýêâèâàëåíòíóþ åé ïðîãðàììóäëÿ ÐÌÌ, â êîòîðîé ÷èñëî äîïîëíèòåëüíûõ êîìàíä áóäåò íà åäèíèöóìåíüøå.Äåéñòâèòåëüíî ïóñòü P ïðîãðàììà äëÿ ÐÌÌ, ñîäåðæàùàÿ äîïîëíèòåëüíûå êîìàíäû. Çàôèêñèðóåì â íåé íåêîòîðóþ äîïîëíèòåëüíóþ êîìàíäó H:=f (H1 ,...,Hk ), ãäå ôóíêöèÿ f âû÷èñëÿåòñÿ íåêîòîðîé ïðîãðàììîé Pf , èñïîëüçóþùåé ïîïàðíî ðàçëè÷íûå îñíîâíûå ðåãèñòðû R0 , R1 , . . .,Rk , è äîïîëíèòåëüíûå ðåãèñòðû S1 , .
. ., Sl . Âûáåðåì ñðåäè äîïîëíèòåëüíûõ ðåãèñòðîâ ïîïàðíî ðàçëè÷íûå ðåãèñòðû R0∗ , R1∗ , . . . , Rk∗ è S1∗ , . . . , Sl∗ ,íå óïîìèíàåìûå â ïðîãðàììàõ P è Pf . Îïðåäåëèì ïðîãðàììó Pf∗ êàêðåçóëüòàò îäíîâðåìåííîé çàìåíû â Pf âñåõ ðåãèñòðîâ R0 , R1 , . . . , Rk èS1 , . . . , Sl ñîîòâåòñòâåííî íà R0∗ , R1∗ , . . . , Rk∗ è S1∗ , . . . , Sl∗ . Íà ìåñòî çàôèêñèðîâàííîé íàìè êîìàíäû H:=f(H1 ,...,Hk ) âñòàâèì â ïðîãðàììó P ïîñëåäîâàòåëüíîñòü êîìàíä5R∗1 :=H1R∗2 :=H2...R∗k :=HkP∗fH:=R∗0 ,çàíîâî ïðîíóìåðóåì ïîëó÷èâøèéñÿ ñïèñîê íàòóðàëüíûìè ÷èñëàìè, íà÷èíàÿ ñ 0, ïîñëå ÷åãî êàê â ÷àñòè Pf∗ òàê è â îñòàâøåéñÿ ÷àñòè ïðîãðàììûP çàìåíèì âî âñåõ îïåðàòîðàõ ïåðåõîäà if .
. . goto m è goto m ÷èñëà míà äðóãèå ÷èñëà òàê, ÷òîáû îíè çàäàâàëè• ïåðåõîä íà òå æå êîìàíäû, ÷òî è ðàíüøå â ñëó÷àå, åñëè îíè çàäàâàëè ïåðåõîä íà êîíêðåòíûå êîìàíäû,• ïåðåõîä íà êîìàíäó, ñëåäóþùóþ çà âñåìè êîìàíäàìè ôðàãìåíòà P∗fâ ñëó÷àå, êîãäà êîìàíäà ïåðåõîäà ïðåäíàçíà÷åíà äëÿ âûõîäà èç P∗f ,• ïåðåõîä íà íåñóùåñòâóþùóþ êîìàíäó, åñëè êîìàíäà ïåðåõîäà ïðåäíàçíà÷åíà äëÿ çàâåðøåíèå ðàáîòû ïðîãðàììû.Íåòðóäíî óáåäèòüñÿ, ÷òî ïîëó÷åííàÿ òàêèì ñïîñîáîì ïðîãðàììà ýêâèâàëåíòíà èñõîäíîé è ïðè ýòîì ñîäåðæèò íà åäèíèöó ìåíüøå äîïîëíèòåëüíûõ êîìàíä. Òàêèì îáðàçîì, äëÿ äîêàçàòåëüñòâà ñóùåñòâîâàíèÿ ïðîãðàìì äëÿ ÌÌ,âû÷èñëÿþùèõ íåêîòîðóþ ôóíêöèþ, äîñòàòî÷íî äîêàçàòü ñóùåñòâîâàíèåïðîãðàìì äëÿ ÐÌÌ, âû÷èñëÿþùèõ òó æå ñàìóþ ôóíêöèþ, ÷òî, êàê ïðàâèëî, íàìíîãî ïðîùå.Òåîðåìà 1.0.4 Âñå ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè âû÷èñëèìû íà ÌÌ.Äîêàçàòåëüñòâî. Íàì äîñòàòî÷íî ñíà÷àëà äîêàçàòü âû÷èñëèìîñòü íàÌÌ ïðîñòåéøèõ ôóíêöèé, à ïîòîì äîêàçàòü, ÷òî ïðèìåíåíèå îïåðàòîðîâS, R è M ê âû÷èñëèìûì íà ÌÌ ôóíêöèÿì ñíîâà ïðèâîäèò ê ôóíêöèÿì,âû÷èñëèìûì íà ÌÌ.
Çäåñü ìû áóäåì ïîëüçîâàòüñÿ òîëüêî ÷òî äîêàçàííûì ðåçóëüòàòîì îá ýëèìèíàöèè äîïîëíèòåëüíûõ êîìàíä äëÿ ÐÌÌ.Ïðîñòåéøèå ôóíêöèè âû÷èñëèìû íà ÌÌ. Äåéñòâèòåëüíî, ôóíêöèÿs(x) = x + 1 âû÷èñëÿåòñÿ ïðîãðàììîé èç äâóõ êîìàíä 0: R0 :=R1 è 1: inc6Ãëàâà 1.ÌèíèìàøèíûR0 , ôóíêöèÿ 0(x) = 0 âû÷èñëÿåòñÿ ïðîãðàììîé 0: R0 :=0, à ôóíêöèÿnIm(x1 , .
. . , xn ) âû÷èñëÿåòñÿ ïðîãðàììîé 0: R0 :=Rm .Äîêàæåì âû÷èñëèìîñòü êîìïîçèöèè ôóíêöèé, âû÷èñëèìûõ íà ÌÌ,ò.å., ÷òî ïðèìåíåíèå îïåðàòîðà ñóïåðïîçèöèè S ê ôóíêöèÿì, âû÷èñëèìûì íà ÌÌ, ñíîâà äàåò ôóíêöèþ, âû÷èñëèìóþ íà ÌÌ. Ïðåäïîëîæèì,÷òî ôóíêöèè h1 (x1 , . . . , xn ), . . . , hk (x1 , . . . , xn ) è g(y1 , . . . , yk ) âû÷èñëèìûíà ÌÌ. Òîãäà èõ êîìïîçèöèÿ âû÷èñëèìà íà ÐÌÌ ïðè ïîìîùè ñëåäóþùåé ïðîãðàììû, â êîòîðîé âî âñåõ ðàñøèðåííûõ îïåðàòîðàõ ó÷àñòâóþòâû÷èñëèìûå íà ÌÌ ôóíêöèè:0:1:···k-1:k:S1 :=h1 (R1 ,...,Rn )S2 :=h2 (R1 ,...,Rn )Sk :=hk (R1 ,...,Rn )R0 :=g (S1 ,...,Sk ).Ïîêàæåì, ÷òî ôóíêöèÿ, ïîëó÷àþùàÿñÿ èç ôóíêöèé, âû÷èñëèìûõ íàÌÌ, ñ ïîìîùüþ îïåðàòîðà R ïðèìèòèâíîé ðåêóðñèè òàêæå âû÷èñëèìàíà ÌÌ.
Ïðåäïîëîæèì, ÷òî ôóíêöèÿ f (y, x1 , . . . , xn ) çàäà¼òñÿ ïðèìèòèâíîðåêóðñèâíîé ñõåìîéf (0, x1 , . . . , xn )= g(x1 , . . . , xn )f (y + 1, x1 , . . . , xn ) = h(x1 , . . . , xn , y, f (y, x1 , . . . , xn )),è ôóíêöèè g è h âû÷èñëèìû íà ÌÌ. Òîãäà, êàê íåòðóäíî óáåäèòüñÿ,ôóíêöèÿ f âû÷èñëÿåòñÿ ñëåäóþùåé ïðîãðàììîé äëÿ ÐÌÌ:0:1:2:3:4:5:6:R0 :=g (R2 ,...,Rn+1 )S0 :=0if R1 =0 goto 7R0 :=h(R2 ,...,Rn+1 ,S0 ,R0 )inc S0dec R1goto 2Ïîêàæåì, ÷òî ïðèìåíåíèå îïåðàòîðà ìèíèìèçàöèè M ê ôóíêöèè,âû÷èñëèìîé íà ÌÌ, ñíîâà ïðèâîäèò ê ôóíêöèè, âû÷èñëèìîé íà ÌÌ.Ïðåäïîëîæèì, ÷òî ôóíêöèÿ f ïîëó÷àåòñÿ ïðè ïîìîùè îïåðàòîðà ìèíèìèçàöèè èç âû÷èñëèìîé íà ÌÌ ôóíêöèè g êàêf (x1 , . . .
, xn ) = µy(g(x1 , . . . , xn , y) = 0).7Òîãäà f ìîæíî âû÷èñëèòü ïðè ïîìîùè ñëåäóþùåé ïðîãðàììû äëÿ ÐÌÌ:0:1:2:3:4:R0 :=0S0 :=g (R1 ,...,Rn ,R0 )if S0 =0 goto 5inc R0goto 1Òàêèì îáðàçîì, ìû ïîêàçàëè, ÷òî ëþáàÿ ÷.ð.ô. âû÷èñëèìà íà ÌÌ, èòåîðåìà äîêàçàíà. Òåîðåìà 1.0.5 Ëþáàÿ âû÷èñëèìàÿ íà ÌÌ ôóíêöèÿ ÿâëÿåòñÿ ÷.ð.ô.Äîêàçàòåëüñòâî. Ñíà÷àëà ìû îïðåäåëèì êîäèðîâêè íåêîòîðûõ îáúåêòîâ, îòíîñÿùèõñÿ ê ÌÌ, â òîì ÷èñëå è ñàìèõ ÌÌ è óñòàíîâèì èõíåêîòîðûå ñâîéñòâà. Ôàêòè÷åñêè, ìû äîêàæåì, ÷òî íåêîòîðûå äåéñòâèÿè ïîíÿòèÿ, îòíîñÿùèåñÿ ê ÌÌ, ìîæíî âûðàçèòü ñ ïîìîùüþ ïðèìèòèâíîðåêóðñèâíûõ ôóíêöèé, îòêóäà ïîòîì ïîëó÷èì ñàìó òåîðåìó.Êîä îáúåêòà a ëþáîé ïðèðîäû (ðåãèñòðà, êîìàíäû è ïð.) ñîîòâåòñòâóþùåå åìó íàòóðàëüíîå ÷èñëî áóäåì îáîçíà÷àòü ÷åðåç γ(a).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
