1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 8
Текст из файла (страница 8)
Óêàæåì ñíà÷àëà ìåòîä ïîñòðîåíèÿ ñåìåéñòâà ìíîæåñòâA0 , A1 , . . .  êà÷åñòâå íà÷àëüíîãî çíà÷åíèÿ ìíîæåñòâà A0 íàäî âçÿòü ìíîæåñòâî âñåõ ñëîâ, ïîëó÷àåìûõ èç α ïðèìåíåíèåì âñåìè âñåâîçìîæíûìèñïîñîáàìè âñåõ ïðîäóêöèé, è ïîñëåäîâàòåëüíî ñòðîèòü êîíå÷íûå ìíîæåñòâà A1 , A2 , . . . , A(|β|+1)·|V ∪T ||β| ïîëó÷àÿ êàæäûé ðàç ìíîæåñòâî Ai+1 ïîAi ñëåäóþùèì ñïîñîáîì:Ai+1 åñòü ìíîæåñòâî Ai ñ äîáàâëåííûìè ê íåìó ðåçóëüòàòàìèïðèìåíåíèÿ êî âñåì ýëåìåíòàì ìíîæåñòâà Ai âñåõ âîçìîæíûõïðîäóêöèé èç P âñåìè âîçìîæíûìè ñïîñîáàìè.∗ ñèëó ïðåäëîæåíèÿ 2.6.2 ñâîéñòâî α → β ýêâèâàëåíòíî β ∈ A(|β|+1)·|V ∪T ||β| .ΓÓïðàæíåíèÿ1. Ïîñòðîéòå ãðàììàòèêó Γ â àëôàâèòå A = {0, 1}, äëÿ êîòîðîéà) L(Γ) = ∅;á) L(Γ) = {a};â) L(Γ) = {Λ};ã) L(Γ) = A+ ;ä) L(Γ) = A∗ ;å) L(Γ) = {1.
. 1} 6= Λ | n ∈ N, n 6= 0};| .{z2næ) L(Γ) = {1. . 1} | n ∈ N};| .{z2nç) L(Γ) = {1. . 1} | n ∈ N};| .{z2n+1è) L(Γ) = {w 6= Λ | ÷èñëî åäèíèö â w äåëèòñÿ íà 3};ê) L(Γ) = {an bn | n ∈ N};ë) L(Γ) ðàâíî êîíå÷íîìó ìíîæåñòâó ñëîâ {w1 , . . . , wk }.ì) ìíîæåñòâî L(Γ) ðàâíî ìíîæåñòâó âñåõ àðèôìåòè÷åñêèõ âûðàæåíèé,ñîñòàâëåííûõ èç áóêâ a, b ñ ïîìîùüþ îïåðàöèé +, − è ×; ïðè ýòîì ïðåäïîëàãàåòñÿ, ÷òî ìû ðàññòàâëÿåì â âûðàæåíèÿõ àáñîëþòíî âñå ñêîáêè(ò.å., ((a + b) + c), (a × b) + (a × c));í) ìíîæåñòâî L(Γ) ðàâíî ìíîæåñòâó âñåõ ñëîâ w òàêèõ, ÷òî îíè íå èçìå-44Ãëàâà 2.
Êîíå÷íûå àâòîìàòû è ãðàììàòèêèíÿþòñÿ îò ïåðåïèñûâàíèÿ èõ çàäîì íàïåðåä.î) L(Γ) ðàâíî ìíîæåñòâó âñåõ ðåãóëÿðíûõ âûðàæåíèé.Ãëàâà 3Ôîðìàëèçàöèè ïîíÿòèÿàëãîðèòìà ýòîé ãëàâå áóäóò äàíû íåêîòîðûå ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàè ïîêàçàíà ýêâèâàëåíòíîñòü äâóõ èç íèõ, à èìåííî, ìàøèí ؼíôèëäà è÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ýêâèâàëåíòíîñòü ýòèõ äâóõ ôîðìàëèçàöèé îñòàëüíûì ôîðìàëèçàöèÿì ìîæåò áûòü äîêàçàíà â òîì æå ñòèëå.3.1 Ìàøèíû ؼíôèëäàËþáàÿ ìàøèíà ؼíôèëäà (â äàëüíåéøåì ïðîñòî ìàøèíà) èìååò áåñêîíå÷íîå ÷èñëî ðåãèñòðîâ R0 , R1 , .
. . , ïðîíóìåðîâàííûõ íàòóðàëüíûìè÷èñëàìè 0, 1, . . . Êàæäûé èç ýòèõ ðåãèñòðîâ â êàæäûé ìîìåíò âðåìåíè ñîäåðæèò ëþáîå (íî òîëüêî îäíî) íàòóðàëüíîå ÷èñëî. Êðîìå ýòîãî óìàøèíû åñòü ïðîãðàììà, à òàêæå èìååòñÿ ñ÷¼ò÷èê êîìàíä, âñåãäà ñîäåðæàùèé íåêîòîðîå íàòóðàëüíîå ÷èñëî. Êàê ñòàíåò ÿñíî èç äàëüíåéøåãî,ëþáàÿ ïðîãðàììà èñïîëüçóåò ëèøü êîíå÷íîå ÷èñëî ðåãèñòðîâ, êîòîðîåçàðàíåå íåòðóäíî îïðåäåëèòü ïî ïðîãðàììå è èñõîäíûì äàííûì.Ïðîãðàììà ìàøèíû ñîñòîèò èç êîíå÷íîãî ñïèñêà êîìàíä, ïîñëåäîâàòåëüíî ïðîíóìåðîâàííûõ íàòóðàëüíûìè ÷èñëàìè íà÷èíàÿ ñ 0.Ïåðåä çàïóñêîì ìàøèíû â ðåãèñòðû çàíîñÿòñÿ èñõîäíûå äàííûå, àâ ñ÷åò÷èê êîìàíä çàíîñèòñÿ ÷èñëî 0. Ïîñëå ýòîãî ðàáîòà ìàøèíû îñóùåñòâëÿåòñÿ ïî øàãàì.Øàã ìàøèíû ñîñòîèò â èñïîëíåíèè êîìàíäû, íîìåð êîòîðîé óêàçàíâ ñ÷åò÷èêå êîìàíä.
Åñëè òàêîãî íîìåðà êîìàíäû â ïðîãðàììå íåò, òîìàøèíà îñòàíàâëèâàåòñÿ.Ñóùåñòâóåò äâà òèïà êîìàíä:4546Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàINC I óâåëè÷èâàåò ñîäåðæèìîå Iãî ðåãèñòðà íà 1 è óâåëè÷èâàåò ñîäåðæèìîå ñ÷åò÷èêà êîìàíä íà 1. Ïîñëå ýòîãî ìàøèíà ïåðåõîäèò êñëåäóþùåìó øàãó.DEC I,n åñëè ñîäåðæèìîå Iãî ðåãèñòðà áîëüøå 0, òî óìåíüøàåò ñîäåðæèìîå Iãî ðåãèñòðà íà 1 è çàíîñèò n â ñ÷åò÷èê êîìàíä. Åñëè æåñîäåðæèìîå Iãî ðåãèñòðà ðàâíî 0, òî ýòà êîìàíäà ïðîñòî óâåëè÷èâàåò ñîäåðæèìîå ñ÷åò÷èêà êîìàíä íà 1.Çàìåòèì, ÷òî ïàðà ïîñëåäîâàòåëüíî ðàñïîëîæåííûõ â ïðîãðàììå êîìàíä INC 0 DEC 0, n, ïðîñòî çàíîñèò ÷èñëî n â ñ÷åò÷èê êîìàíä, ò.å. ïðèâîäèò ê òîìó, ÷òî ñëåäóþùàÿ èñïîëíÿåìàÿ êîìàíäà áóäåò èìåòü íîìåð n;ïðè ýòîì ñîäåðæèìîå ðåãèñòðîâ íå èçìåíÿåòñÿ.
Ýòî ÿâëÿåòñÿ àíàëîãîìêîìàíäû áåçóñëîâíîãî ïåðåõîäà GOTO n â íåêîòîðûõ ÿçûêàõ ïðîãðàììèðîâàíèÿ (èëè êîìàíäû JMP n â íåêîòîðûõ ÿçûêàõ àññåìáëåðà).Çàìåòèì òåïåðü, ÷òî åñëè Ié ðåãèñòð íå óïîìÿíóò â êîìàíäàõ ïðîãðàììû, òî â õîäå âûïîëíåíèÿ ýòîé ïðîãðàììû åãî ñîäåðæèìîå íå èçìåíèòñÿ è îíî íå îêàçûâàåò íèêàêîãî âëèÿíèÿ íè íà õîä âûïîëíåíèÿïðîãðàììû, íè íà å¼ ðåçóëüòàò.Äëÿ ïîñòðîåíèÿ òåîðèè âû÷èñëèìûõ ôóíêöèé ìû áóäåì ðàññìàòðèâàòü ÷àñòè÷íûå ôóíêöèè, òî åñòü ôóíêöèè, çíà÷åíèå êîòîðûõ ìîæåòîêàçàòüñÿ íåîïðåäåë¼ííûì ïðè íåêîòîðûõ (à èíîãäà äàæå âñåõ) çíà÷åíèÿõ àðãóìåíòîâ.
Ðàññìîòðåíèå ÷àñòè÷íûõ ôóíêöèé ïîçâîëÿåò äîñòàòî÷íîåñòåñòâåííî ïîñòðîèòü òåîðèþ âû÷èñëèìûõ ôóíêöèé. Ïðè ðàññìîòðåíèè òîëüêî âñþäó îïðåäåëåííûõ ôóíêöèé õîðîøóþ òåîðèþ ïîñòðîèòüíå óäàåòñÿ1 .Îïðåäåëåíèå 3.1.1 Ïóñòü P ïðîãðàììà, k > 0. Îïðåäåëèì ÷àñòè÷-íóþ k àðíóþ ôóíêöèþ APk ñëåäóþùèì îáðàçîì. Ïóñòü APk (x1 , . . . , xk )áóäåò çíà÷åíèåì, íàõîäÿùèìñÿ â íóëåâîì ðåãèñòðå ìàøèíû â ìîìåíòîñòàíîâêè ïðè óñëîâèè, ÷òî îíà áûëà çàïóùåíà ñ ïðîãðàììîé P è çíà÷åíèÿìè x1 , . . . , xk â ðåãèñòðàõ 1, .
. . , k ñîîòâåòñòâåííî è íóëåâûìè çíà÷åíèÿìè â îñòàëüíûõ ðåãèñòðàõ. Åñëè ìàøèíà íèêîãäà íå îñòàíàâëèâàåòñÿ, ìû ñ÷èòàåì çíà÷åíèå APk (x1 , . . . , xk ) íåîïðåäåëåííûì.Ïóñòü f è g äâå ÷àñòè÷íûå ôóíêöèè. ×åðåç f (x̄) ' g(x̄) ìû áóäåìîáîçíà÷àòü ôàêò, ÷òî ïðè ëþáûõ íàáîðàõ çíà÷åíèé àðãóìåíòîâ x̄ ëèáîçíà÷åíèÿ f (x̄) è g(x̄) îäíîâðåìåííî íå îïðåäåëåíû, ëèáî îäíîâðåìåííîîïðåäåëåíû è ðàâíû ìåæäó ñîáîé.1Ýòî íåñêîëüêî ìåíÿåò îòíîøåíèå ê âñòðå÷àþùåìóñÿ íà ïðàêòèêå çàâèñàíèþïðîãðàìì.3.1. Ìàøèíû ؼíôèëäà47Îïðåäåëåíèå 3.1.2 Íàçîâåì kàðíóþ ÷àñòè÷íóþ ôóíêöèþ f : Nk →N âû÷èñëèìîé íà ìàøèíå ؼíôèëäà, åñëè ñóùåñòâóåò ïðîãðàììà Pòàêàÿ, ÷òîAPk (x1 , . . . , xk ) ' f (x1 , .
. . , xk )äëÿ âñåõ x1 , . . . , xk ∈ N, èíà÷å ãîâîðÿ, åñëè APk è f ðàâíû êàê ôóíêöèè.Çàìåòèì, ÷òî îäíà è òà æå ïðîãðàììà ìîæåò âû÷èñëÿòü ôóíêöèè îòîäíîãî, äâóõ è ò.ä. àðãóìåíòîâ.Ïðèìåð. Ïðîãðàììà0 : DEC1 : DEC2 : DEC3 : INCâû÷èñëÿåò1,21,41,00îñòàòîê îò äåëåíèÿ íà 2.Óïðàæíåíèå. Ïðîñ÷èòàéòå ýòó ïðîãðàììó âðó÷íóþ è óáåäèòåñü â ýòîì.Çàìåòèì òàêæå, ÷òî âñå âû÷èñëèìûå ôóíêöèè ÿâëÿþòñÿ èíòóèòèâíîâû÷èñëèìûìè. Îáðàòíîå óòâåðæäåíèå î òîì, ÷òî âñå èíòóèòèâíî âû÷èñëèìûå ôóíêöèè âû÷èñëèìû íà ìàøèíàõ ؼíôèëäà, ñîäåðæèòñÿ âòåçèñå ×¼ð÷à, îáñóæäàåìîì â êîíöå ýòîé ãëàâû, íî ïîêà ÷òî èñòèííîñòüýòîãî óòâåðæäåíèÿ íåî÷åâèäíà. Íî äóìàåòñÿ, ÷òî èçó÷èâ ïðèìåðû âû÷èñëèìûõ ôóíêöèé è ìåòîäû äîêàçàòåëüñòâà âû÷èñëèìîñòè íèæå, ÷èòàòåëü ïðèîáðåòåò óâåðåííîñòü â ñïðàâåäëèâîñòè è ýòîãî óòâåðæäåíèÿ.ÌàêðîñûÌàøèíû ؼíôèëäà, êàê è äðóãèå òåîðåòè÷åñêèå ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîñòè, ñîçäàíû âîâñå íå äëÿ òîãî, ÷òîáû ïèñàòü íà ïðåäîñòàâëÿåìûõ èìè àëãîðèòìè÷åñêèõ ÿçûêàõ ïðîãðàììû, ïðåäíàçíà÷åííûåäëÿ ðåøåíèÿ êàêèõòî ïðàêòè÷åñêè âàæíûõ çàäà÷.
Ýòî áûëî áû êðàéíåíåóäîáíî è íåïðàêòè÷íî. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîñòè ïðåäíàçíà÷åíû äëÿ òîãî, ÷òîáû èçó÷àòü îñíîâíûå ñâîéñòâà ïðîöåññà âû÷èñëåíèÿ è ñâîéñòâà âû÷èñëèìûõ ôóíêöèé è îòíîøåíèé. Ïîýòîìó äëÿ íàñçäåñü áóäåò ãîðàçäî áîëåå âàæíûì äîêàçàòü ñóùåñòâîâàíèå ïðîãðàììûñ çàäàííûìè ñâîéñòâàìè, ÷åì íàïèñàòü ñàìó ïðîãðàììó.Äëÿ áîëåå óäîáíîãî è íàãëÿäíîãî äîêàçàòåëüñòâà ñóùåñòâîâàíèÿ òåõèëè èíûõ ïðîãðàìì, ìû ðàñøèðèì ÿçûê ìàøèí ñ ïîìîùüþ òàê íàçûâàåìûõ ìàêðîñîâ. Ìàêðîñû ýòî êèðïè÷èêè, èç êîòîðûõ ìû áóäåì ñîáè-48Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàðàòü ïðîãðàììû. Êàæäîé îáû÷íîé ïðîãðàììå P ìû ñîïîñòàâèì åå ìàêðîñ îïåðàòîð P ∗ , è ðàñøèðèì âîçìîæíîñòè ìàøèíû òàê, ÷òîáû îíàìîãëà èñïîëíÿòü ìàêðîñû â êà÷åñòâå êîìàíä. Ïîëó÷åííóþ ìàøèíó íàçîâåì ìàêðîìàøèíîé. Ïîíÿòèå ïðîãðàììû ïðè ýòîì îñòàåòñÿ ïðåæíèì,ðàñøèðÿåòñÿ òîëüêî ñåìåéñòâî âîçìîæíûõ êîìàíä. Ïðîãðàììû, ñîäåðæàùèå ìàêðîñû, ìû áóäåì íàçûâàòü ìàêðîïðîãðàììàìè.Èñïîëíåíèå ìàêðîñà P ∗ , íàõîäÿùåãîñÿ â ìàêðîïðîãðàììå ïîä íîìåðîì m, ñîñòîèò â òîì, ÷òî1. â ìàøèíó âìåñòî èìåþùåéñÿ â äàííûé ìîìåíò ïðîãðàììû ââîäèòñÿ ïðîãðàììà P ;2. ýòà ïðîãðàììà P èñïîëíÿåòñÿ ñ òåìè äàííûìè â ðåãèñòðàõ, êîòîðûåòàì ñîäåðæàëèñü íà ýòîò ìîìåíò;3.
çàòåì â ìàøèíó âîçâðàùàåòñÿ ñòàðàÿ ïðîãðàììà è â ñ÷åò÷èê êîìàíä çàíîñèòñÿ m + 1.Íà ýòîì èñïîëíåíèå ìàêðîñà çàêàí÷èâàåòñÿ, ò.å. äàëåå èñïîëíÿåòñÿ êîìàíäà èëè ìàêðîñ, ñëåäóþùàÿ íåïîñðåäñòâåííî çà òîëüêî ÷òî èñïîëíåííûì ìàêðîñîì â îñíîâíîé ïðîãðàììå è ò.ä.Îïðåäåëåíèå 3.1.3 Ïðîãðàììû P è Q äëÿ ìàêðîìàøèíû íàçûâàþòñÿýêâèâàëåíòíûìè, åñëè çàïóñêè ìàêðîìàøèíû ñ ýòèìè ïðîãðàììàìè íàëþáûõ íà÷àëüíûõ ñîäåðæèìûõ ðåãèñòðîâ ëèáî ïðèâåäóò ê îñòàíîâêåîáåèõ ìàøèí ñ îäèíàêîâûìè ñîäåðæèìûìè ðåãèñòðîâ, ëèáî îáå ïðîãðàììû íèêîãäà íå çàêîí÷àò ñâîþ ðàáîòó.Òåîðåìà 3.1.4 (îá ýëèìèíàöèè ìàêðîñîâ) Âñÿêàÿ ïðîãðàììà ñ ìàêðîñàìè ýêâèâàëåíòíà íåêîòîðîé ïðîãðàììå, íå ñîäåðæàùåé ìàêðîñîâ.Äîêàçàòåëüñòâî. Äîñòàòî÷íî ïîêàçàòü, êàê ìîæíî ïî ïðîèçâîëüíîéìàêðîïðîãðàììå P0 ïîñòðîèòü ýêâèâàëåíòíóþ åé ïðîãðàììó, ñîäåðæàùóþ íà îäèí ìàêðîñ ìåíüøå, ÷åì èñõîäíàÿ ïðîãðàììà.
Ïîâòîðÿÿ ýòóïðîöåäóðó, â êîíöå êîíöîâ ìû ïîëó÷èì ïðîãðàììó, ýêâèâàëåíòíóþ äàííîé, è óæå íå ñîäåðæàùóþ íè îäíîãî ìàêðîñà.Ïóñòü P ∗ íåêîòîðûé ìàêðîñ â ïðîãðàììå P0 . Ñíà÷àëà çàìåíèì âïðîãðàììå P0 íåêîòîðîå âõîæäåíèå ìàêðîñà P ∗ íà ñïèñîê êîìàíä ïðîãðàììû P . Çàíîâî ïåðåíóìåðóåì âñå êîìàíäû ïîëó÷åííîé ïðîãðàììû(êàê îáû÷íî, íà÷èíàÿ ñ 0). Ïîòîì çàìåíèì âñå êîìàíäû DEC I,n, îñóùåñòâëÿþùèå ïåðåõîä íà èñïîëíåíèå íîâûõ êîìàíä ñ íîìåðîì n, íàêîìàíäû DEC I,m, òàêèì îáðàçîì, ÷òîáû ïåðåõîä îñóùåñòâëÿëñÿ íà òå3.1. Ìàøèíû ؼíôèëäà49æå êîìàíäû, íà êîòîðûå îí îñóùåñòâëÿëñÿ ðàíåå â ìàêðîïðîãðàììå (åñëè êîìàíäà óæå ñîäåðæàëàñü â ìàêðîïðîãðàììå) ëèáî â ìàêðîñå (åñëèêîìàíäà ñîäåðæàëàñü â ìàêðîñå).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
