1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 9
Текст из файла (страница 9)
Åñëè æå â êîìàíäå âèäà DEC I,n èçP ÷èñëî n íå ñîäåðæèòñÿ ñðåäè íîìåðîâ êîìàíä ïðîãðàììû P (òî åñòüýòà êîìàíäà ïðåäíàçíà÷åíà äëÿ çàâåðøåíèÿ ðàáîòû P ïðè óñëîâèè, ÷òîñîäåðæèìîå Iãî ðåãèñòðà áîëüøå íóëÿ), òî çàìåíèì åå íà êîìàíäó âèäà DEC I,m, ãäå m íîìåð êîìàíäû ïîëó÷èâøåéñÿ ìàêðîïðîãðàììû,íåïîñðåäñòâåííî ñëåäóþùåé çà ñïèñêîì êîìàíä ìàêðîñà P ∗ .Çàïóñòèâ ïîëó÷åííóþ â ðåçóëüòàòå ìàêðîïðîãðàììó ïàðàëëåëüíî ñèñõîäíîé ìàêðîïðîãðàììîé, íåòðóäíî óáåäèòüñÿ, ÷òî ïîëó÷åííàÿ ïðîãðàììà ïðèâîäèò ê òåì æå ðåçóëüòàòàì, ÷òî è èñõîäíàÿ.
¤Ïðèìåð. Ðàññìîòðèì ñëåäóþùóþ ïðîãðàììó P , â ðåçóëüòàòå ðàáîòûêîòîðîé â 1ì ðåãèñòðå îáðàçóåòñÿ ñóììà çíà÷åíèé 1ãî è 2ãî ðåãèñòðà, ñîäåðæèìîå 2ãî ðåãèñòðà îáíóëÿåòñÿ, à ñîäåðæèìûå îñòàëüíûõðåãèñòðîâ íå èçìåíÿþòñÿ:0: INC 0 (ïåðåõîä íà 3: )1: DEC 0,32: INC 13: DEC 2,2Ðàññìîòðèì òåïåðü ìàêðîïðîãðàììó P0 , â ðåçóëüòàòå ðàáîòû êîòîðîé â 1ì ðåãèñòðå îñòàíåòñÿ ñóììà ñîäåðæèìûõ 1ãî è 2ãî ðåãèñòðîâ,óâåëè÷åííàÿ íà 1:0 : INC 11 : P∗ ðåçóëüòàòå ïðèìåíåíèÿ ïðåîáðàçîâàíèÿ, îïèñàííîãî â äîêàçàòåëüñòâå òåîðåìû, ìû ïîëó÷èì ñëåäóþùóþ ïðîãðàììó (â íåé íàêëîííûìøðèôòîì âûäåëåíû êîìàíäû, ïîäñòàâëåííûå âìåñòî êîìàíä ìàêðîñà P ,è ïîä÷åðêíóòû íîìåðà, èçìåíåííûå ïîñëå ýòîãî):0 : INC 11 : INC 02 : DEC 0,43 : INC 14 : DEC 2,3Îïðåäåëèì òåïåðü íåêîòîðûå ìàêðîñû, èãðàþùèå â äàëüíåéøåì âàæíóþ ðîëü.• Ìàêðîñ äëÿ ïðîãðàììû O:DEC I,0 îáíóëèò ñîäåðæèìîå I ãî ðåãèñòðà.
Îáîçíà÷èì ýòîò ìàêðîñ ZERO I.50Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìà• Ñëåäóþùèé ìàêðîñ, îáîçíà÷àåìûé [i]→[j],(k) äëÿ i 6= k 6= j ,êîïèðóåò ñîäåðæèìîå iãî ðåãèñòðà â j é ðåãèñòð, èñïîëüçóÿ k éðåãèñòð â êà÷åñòâå âñïîìîãàòåëüíîãî. Ñîäåðæèìîå iãî ðåãèñòðàïðè i 6= j íå èçìåíÿåòñÿ.Âîò ìàêðîïðîãðàììà, ïðåîáðàçîâàâ êîòîðóþ â ñîîòâåòñòâèè ñ òåîðåìîé îá ýëèìèíàöèè ìàêðîñîâ, ìû ïîëó÷èì ïðîãðàììó äëÿ ìàêðîñà[i]→[j] ïðè i 6= j :¾0 : ZERO j1 : ZERO k(îáíóëèëè jé è ké ðåãèñòðû)2 : INC 03 : DEC 0,6¾(ïåðåõîä íà 6þ êîìàíäó)4 : INC j (åñëè â iîì ðåãèñòðå åùå íå 0, òî5 : INC k óâåëè÷èì jé è ké ðåãèñòðû)6 : DEC i,4¾7 : INC 0(ïåðåõîä íà 10-þ êîìàíäó)8 : DEC 0,10¾9 : INC i(êîïèðóåì èç kãî â ié ðåãèñòð)10 : DEC k,9Åñëè i = j , òî ìîæíî âçÿòü ëþáóþ ïðîãðàììó, íè÷åãî íå èçìåíÿþùóþ, íàïðèìåð 0:INC 0; 1:DEC 0,2.• Ïóñòü F k àðíàÿ âû÷èñëèìàÿ ôóíêöèÿ è ïðîãðàììà P åå âû÷èñëÿåò.
Ïî ïðîãðàììå P ìîæíî îïðåäåëèòü ìàêðîñ, îáîçíà÷àåìûéF([i1 ],...,[ik ])→[j],s,(u0 ,...,um ),êîòîðûé âû÷èñëÿåò çíà÷åíèå ôóíêöèè F îò ñîäåðæèìûõ ðåãèñòðîâRi1 , . . . , Rik , çàïèñûâàåò åãî â j é ðåãèñòð è ïðè ýòîì íå èçìåíÿåòçíà÷åíèé îñòàëüíûõ ðåãèñòðîâ äî sãî âêëþ÷èòåëüíî. Ïàðàìåòðûu0 , . . . , um íîñÿò âñïîìîãàòåëüíûé õàðàêòåð è îïðåäåëÿþòñÿ äàëååâìåñòå ñ èõ ÷èñëîì m.Âîçüìåì â êà÷åñòâå m ëþáîå ÷èñëî, ïðåâîñõîäÿùåå ÷èñëà i1 , . .
. , ik , s,à òàêæå ïðåâîñõîäÿùåå ìàêñèìàëüíîå çíà÷åíèå ðåãèñòðà, óïîìÿíóòîå âïðîãðàììå P . Âîò ìàêðîïðîãðàììà, ðåøàþùàÿ íàøó çàäà÷ó (íîìåðàñòðîê îïóùåíû):3.2. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè51[0] → [m+1],(m) (ñîõðàíèì âñå çíà÷åíèÿ ðåãèñòðîâ...îò 0ãî äî (m − 1)ãî â ðåãèñòðàõ[m-1] → [m+m],(m)m + 1, . . . , m + m)[m+1+i1 ] → [1],(m) ···[m+1+ik ] → [k],(m) (ïîäãîòîâèì âñ¼ äëÿ âû÷èñëåíèÿ F )ZERO 0ZERO k+1···ZERO m-1P∗(âû÷èñëÿåì F )[m+2] → [1],(m)(âåðíóëè ñòàðûå çíà÷åíèÿ â ðåãè... ñòðû ñ 1ãî ïî m-1é)[m+m] → [m-1],(m)[0] → [j],(m)(ðåçóëüòàò çàíîñèì â jé ðåãèñòð)ñëåäóþùàÿ êîìàíäà âñòàâëÿåòñÿ â ïðîãðàììó, åñëè j 6= 0:[m+1] → [0](åñëè j 6= 0, òî âîññòàíîâèì R0 ).Âñïîìîãàòåëüíûå ïàðàìåòðû u0 , . .
. , um ýòî íîìåðà ðåãèñòðîâ ñ mãî ïî 2mé.  äàëüíåéøåì ìû áóäåì îïóñêàòü ýòè ïàðàìåòðû â è ïèñàòüïðîñòî F([i1 ],...,[ik ]) → [j], èëè [i] → [j], ïîñêîëüêó âñåãäà ìîæíî ñ÷èòàòü, ÷òî ýòè ïàðàìåòðû çàðàíåå âûáðàíû äîñòàòî÷íî áîëüøèìèòàêèì îáðàçîì, ÷òîáû íå âëèÿòü íà ðàáîòó ìàêðîïðîãðàììû.3.2 ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè×àñòè÷íî ðåêóðñèâíûå ôóíêöèè ýòî åù¼ îäíà ôîðìàëèçàöèÿ ïîíÿòèÿâû÷èñëèìîñòè, ïðåäëîæåííàÿ À.×¼ð÷åì. Ìû ïðîäîëæèì èçó÷åíèå ýòîéôîðìàëèçàöèè ïàðàëëåëüíî ñ óæå íà÷àòûì èçó÷åíèåì ìàøèí ؼíôèëäà.
Íàøà áëèæàéøàÿ çàäà÷à ñîñòîèò â òîì, ÷òîáû äîêàçàòü ýêâèâàëåíòíîñòü ýòîãî ïîäõîäà è ìàøèí ؼíôèëäà, è ïîæàëóé ýòî ãëàâíîå ïîïóòíî ïîëó÷èòü äâå ôóíäàìåíòàëüíûå òåîðåìû òåîðèè àëãîðèòìîâ, òåîðåìó î íîðìàëüíîé ôîðìå è smnòåîðåìó.Ñíà÷àëà ìû îïðåäåëèì òàê íàçûâàåìûå ïðîñòåéøèå ôóíêöèè, â èíòóèòèâíîé âû÷èñëèìîñòè êîòîðûõ òðóäíî óñîìíèòüñÿ, à ïîòîì îïðåäå-52Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàëèì òðè îïåðàòîðà íàä ôóíêöèÿìè, ïðèìåíåíèå êîòîðûõ ê âû÷èñëèìûìôóíêöèÿì ñíîâà äàåò âû÷èñëèìûå ôóíêöèè. Íàèìåíüøèé êëàññ ôóíêöèé, ñîäåðæàùèé ïðîñòåéøèå ôóíêöèè è çàìêíóòûé îòíîñèòåëüíî ýòèõîïåðàòîðîâ è áóäåò êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.n (x , . . . , x ) =Îïðåäåëåíèå 3.2.1 Ôóíêöèè 0(x) = 0, s(x) = x + 1 è Im1nxm , äëÿ âñåõ m, n ∈ N òàêèõ, ÷òî 1 6 m 6 n, íàçûâàþòñÿ ïðîñòåéøèìè.Ýòè ôóíêöèè âû÷èñëÿþòñÿ íà ìàøèíàõ ؼíôèëäà ñ ïîìîùüþ ñëåäóþùèõ ìàêðîïðîãðàìì: 0(x) âû÷èñëÿåòñÿ ñ ïîìîùüþ 0:ZERO 0; s(x)n (x , .
. . , x ) âû÷èñâû÷èñëÿåòñÿ ñ ïîìîùüþ 0:INC 1, 1:[1]→[0]; è Im1nëÿåòñÿ ñ ïîìîùüþ 0:[m]→[0].Òåïåðü îïðåäåëèì òðè îñíîâíûõ îïåðàòîðà äëÿ ïîëó÷åíèÿ íîâûõ âû÷èñëèìûõ ôóíêöèé èç óæå èìåþùèõñÿ.Îïðåäåëåíèå 3.2.2 Îïåðàòîðû S, R, M îïðåäåëÿþòñÿ ñëåäóþùèì îá-ðàçîì:Îïåðàòîð ñóïåðïîçèöèè S . Ïóñòü ó íàñ èìåþòñÿ ÷àñòè÷íûå ôóíê-öèè f (y1 , . . .
, ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ). Ðåçóëüòàòîì ïðèìåíåíèÿ îïåðàòîðà ñóïåðïîçèöèè ê ýòèì ôóíêöèÿì ìû íàçîâ¼ìôóíêöèþ h(x1 , . . . , xn ), çíà÷åíèå êîòîðîé âû÷èñëÿåòñÿ, êàêh(x1 , . . . , xn ) = f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )),ò.å. ñíà÷àëà âû÷èñëÿþòñÿ çíà÷åíèÿ ôóíêöèé z1 = g1 (x1 , .
. . , xn ),. . . , zm = gm (x1 , . . . , xn ), à ïîòîì ñ èñïîëüçîâàíèåì ýòèõ çíà÷åíèéóæå âû÷èñëÿåòñÿ h(x1 , . . . , xn ) = f (z1 , . . . , zm ). Åñëè õîòÿ áû îäíîèç ïðîìåæóòî÷íûõ çíà÷åíèé íå âû÷èñëèòñÿ, òî ðåçóëüòàò âû÷èñëåíèÿ áóäåò íåîïðåäåëåííûì.Îïåðàòîð ïðèìèòèâíîé ðåêóðñèè R Ïóñòü èìåþòñÿ ÷àñòè÷íûå ôóíêöèè h(z, y, x̄) è g(x̄), (x̄ = x1 , . . . , xn ). Ðåçóëüòàòîì ïðèìåíåíèÿîïåðàòîðà ïðèìèòèâíîé ðåêóðñèè ê ýòèì ôóíêöèÿì ìû íàçîâåìôóíêöèþ f , êîòîðàÿ îïðåäåëÿåòñÿ ñëåäóþùåé ñõåìîé:·f (0, x̄)= g(x̄)f (y + 1, x̄) = h(f (y, x̄), y, x̄). ÷àñòíîì ñëó÷àå, êîãäà íàáîð ïåðåìåííûõ x̄ ïóñò, ñõåìà âûðîæäàåòñÿ â·f (0)= af (y + 1) = h(f (y), y),3.2.
×àñòè÷íî ðåêóðñèâíûå ôóíêöèè53ãäå a íåêîòîðàÿ êîíñòàíòà. Âû÷èñëåíèå çíà÷åíèÿ f (n, x̄) ñîñòîèòâ ïîñëåäîâàòåëüíîì îïðåäåëåíèè f (0, x̄), f (1, x̄), . . . , f (n, x̄) ÷åðåçóæå âû÷èñëåííûå ïðåäûäóùèå çíà÷åíèÿ. Åñëè îäíî èç ýòèõ çíà÷åíèé îêàæåòñÿ íåîïðåäåëåííûì, òî è f (n, x̄) òîæå áóäåò íåîïðåäåëåíî.Îïåðàòîð ìèíèìèçàöèè M (µîïåðàòîð) Ïóñòü çàäàíà íåêîòîðàÿ ÷àñòè÷íàÿ ôóíêöèÿ g(z, x̄).  ðåçóëüòàòå ïðèìåíåíèÿ îïåðàòîðà ìèíèìèçàöèè ìû ïîëó÷àåì íîâóþ ôóíêöèþ, êîòîðàÿ âû÷èñëÿåòñÿñëåäóþùèì îáðàçîì: f (x̄) = y òîãäà è òîëüêî òîãäà, êîãäà³´ ³´∀i < y g(i, x̄) îïðåäåëåíî è íå ðàâíî 0 & g(y, x̄) = 0 .Ìû èñïîëüçóåì äëÿ µîïåðàòîðà ñëåäóþùóþ çàïèñü:f (x̄) ' µy(g(y, x̄) = 0).Ïðîöåññ âû÷èñëåíèÿ òàêîé ôóíêöèè ñîñòîèò â ïîñëåäîâàòåëüíîìâû÷èñëåíèè çíà÷åíèé g(0, x̄), g(1, x̄), . .
. äî òåõ ïîð, ïîêà ìû íå ïîëó÷èì g(n, x̄) = 0 äëÿ íåêîòîðîãî n. Ýòî n è íàäî âûäàòü â êà÷åñòâåîòâåòà. Åñëè ýòîò ïðîöåññ íèêîãäà íå çàêîí÷èòñÿ, òî çíà÷åíèå f (x̄)áóäåò íå îïðåäåëåíî. Åñëè â ïðîöåññå âû÷èñëåíèÿ íàì ïîíàäîáèòñÿ âû÷èñëèòü êàêîåëèáî çíà÷åíèå g(i, x̄), è îíî íå âû÷èñëèòñÿ, òîïðîöåññ âû÷èñëåíèÿ íèêîãäà íå çàêîí÷èòñÿ, è çíà÷åíèå f (x̄) òàêæåáóäåò íå îïðåäåëåíî.ßñíî, ÷òî åñëè èñõîäíûå ôóíêöèè èíòóèòèâíî âû÷èñëèìû, òî è ðåçóëüòàòû ïðèìåíåíèÿ ê íèì âûøåóêàçàííûõ îïåðàòîðîâ òîæå áóäóò èíòóèòèâíî âû÷èñëèìûìè.Ïðèìåð.
Ïóñòü çíà÷åíèå ôóíêöèè g(y, x) íå îïðåäåëåíî ïðè y = 0 è ëþ-áîì x, à ïðè âñåõ îñòàëüíûõ çíà÷åíèÿõ ïåðåìåííûõ îíî ðàâíî 0. Òîãäà,àêêóðàòíî âûïîëíÿÿ ïðîöåññ âû÷èñëåíèÿ ôóíêöèè h(x) = µy(g(y, x) =0) ïðè x = 0, ïîëó÷èì, ÷òî çíà÷åíèå g(0) íå îïðåäåëåíî. Ïîýòîìó òðàäèöèîííîå ïðî÷òåíèå çàïèñè µy(g(y, x) = 0), êàê ìèíèìàëüíîå y òàêîå,÷òî g(y, x) = 0, ñîäåðæèò â ñåáå îïàñíîñòü íåïðàâèëüíîãî ïîíèìàíèÿîïðåäåëåíèÿ îïåðàòîðà ìèíèìèçàöèè.Îïðåäåëåíèå 3.2.3 ×àñòè÷íàÿ ôóíêöèÿ f : Nk → N íàçûâàåòñÿ ÷à-ñòè÷íî ðåêóðñèâíîé (ïðèìèòèâíî ðåêóðñèâíîé), åñëè ñóùåñòâóåò êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ÷àñòè÷íûõ ôóíêöèé f1 , .
. . , fn = f òàêàÿ,54Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìà÷òî âñÿêàÿ ôóíêöèÿ â ýòîé ïîñëåäîâàòåëüíîñòè ëèáî ïðîñòåéøàÿ, ëèáî ïîëó÷àåòñÿ èç ôóíêöèé ñ ìåíüøèìè íîìåðàìè ñ ïîìîùüþ îäíîãî èçîïåðàòîðîâ S,R,M (îïåðàòîðîâ S,R)Çàìå÷àíèå. Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ïðèìèòèâíî ðåêóðñèâíûåôóíêöèè âñþäó îïðåäåëåíû.Îïðåäåëåíèå 3.2.4 Ôóíêöèÿ íàçûâàåòñÿ îáùåðåêóðñèâíîé (èëè ïðîñòî ðåêóðñèâíîé), åñëè îíà ÷àñòè÷íî ðåêóðñèâíà è âñþäó îïðåäåëåíà.Çàìå÷àíèå. Ïåðâîíà÷àëüíî äàííûå èññëåäîâàòåëÿìè îïðåäåëåíèÿ îá-ùåðåêóðñèâíîé è ðåêóðñèâíîé ôóíêöèé ðàçëè÷àëèñü, íî âïîñëåäñòâèèáûëî äîêàçàíî.
÷òî êëàññû ýòèõ ôóíêöèé ñîâïàäàþò, ïîýòîìó ìû èñïîëüçóåì îáà òåðìèíà êàê ñèíîíèìû. Äåòàëè ìîæíî óçíàòü, íàïðèìåð,â [2].Ìû èñïîëüçóåì ñëåäóþùèå ñîêðàùåíèÿ: ÷.ð.ô. äëÿ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé, ð.ô. (î.ð.ô.) äëÿ ðåêóðñèâíûõ (îáùåðåêóðñèâíûõ) ôóíêöèé, ï.ð.ô. äëÿ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé.Òåïåðü ìû ïîòðàòèì íåêîòîðîå âðåìÿ íà íå î÷åíü ñëîæíîå ïî ñâîåéèäåå, íî äîñòàòî÷íî ãðîìîçäêîå äîêàçàòåëüñòâî ñëåäóþùåé òåîðåìû:Òåîðåìà 3.2.5 Êëàññ ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ ؼíôèëäà ñîâïàäàåò ñ êëàññîì ÷.ð.ô.Ñíà÷àëà äîêàæåì, ÷òî âñÿêàÿ ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà íà ìàøèíå ؼíôèëäà.Ìû óæå çíàåì, ÷òî ïðîñòåéøèå ôóíêöèè âû÷èñëèìû íà ìàøèíàõؼíôèëäà. Ïðåäïîëîæèì, ÷òî ìû óæå äîêàçàëè çàìêíóòîñòü êëàññàôóíêöèé, âû÷èñëèìûõ íà ìàøèíå ؼíôèëäà, îòíîñèòåëüíî îïåðàòîðîâ S, R, M. Îòñþäà áóäåò ñëåäîâàòü, ÷òî âñÿêàÿ ÷àñòè÷íî ðåêóðñèâíàÿôóíêöèÿ âû÷èñëèìà íà ìàøèíå ؼíôèëäà.Äîêàæåì ýòî èíäóêöèåé ïî ÷èñëó n â îïðåäåëåíèè ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè.
Äåéñòâèòåëüíî, åñëè n = 1, òî åäèíñòâåííî âîçìîæíûéñëó÷àé ýòî f = f1 ïðîñòåéøàÿ ôóíêöèÿ. Òàêèå ôóíêöèè, êàê îòìå÷åíî âûøå, âû÷èñëèìû íà ìàøèíå ؼíôèëäà. Áàçà èíäóêöèè äîêàçàíà. Ïðåäïîëîæèì, ÷òî óòâåðæäåíèå äîêàçàíî äëÿ âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé f , äëÿ êîòîðûõ ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü êàê âîïðåäåëåíèè ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé f1 , . . . , fk = f , äëÿ êîòîðîé k < n.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
