1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 10
Текст из файла (страница 10)
Ñîâîêóïíîñòü ôóíêöèé, âîçíèêàþùèõ â ðåçóëüòàòå ïîäîáíîãî àëãåáðàè÷åñêîãî ïîðîæäåíèÿ, íàçûâàåòñÿ êëàññîì ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. ðàìêàõ äàííîãî ïàðàãðàôà ðàññìàòðèâàþòñÿ òîëüêî ÷àñòè÷íûå ôóíêöèè íàω , ò. å. âñåâîçìîæíûå ôóíêöèè âèäà f : X → ω , ãäå ìíîæåñòâî X ⊆ ω k ÿâëÿåòñÿîáëàñòüþ îïðåäåëåíèÿ ôóíêöèè, à ÷èñëî k ∈ ω å¼ ìåñòíîñòüþ. Ëþáóþ 0-ìåñòíóþâñþäó îïðåäåë¼ííóþ ôóíêöèþ f = a ìû îòîæäåñòâëÿåì ñ êîíñòàíòîé a ∈ ω . Íèãäå íåîïðåäåë¼ííàÿ ôóíêöèÿ åäèíñòâåííà è èìååò âèä f = ∅, ïðè÷åì ëþáîå íàòóðàëüíîå÷èñëî ÿâëÿåòñÿ ìåñòíîñòüþ íèãäå íå îïðåäåë¼ííîé ôóíêöèè.Åñëè f n-ìåñòíàÿ, à g m-ìåñòíàÿ ÷àñòè÷íàÿ ôóíêöèÿ, òî äëÿ ëþáûõ çíà÷åíèéx1 , . .
. , xn , y1 , . . . , ym ∈ ω ìû ïèøåì f (x1 , . . . , xn ) = g(y1 , . . . , ym ) òîãäà è òîëüêî òîãäà,êîãäà ëèáî ýòè çíà÷åíèÿ îäíîâðåìåííî íå îïðåäåëåíû, ëèáî îíè îáà îïðåäåëåíû èñîâïàäàþò.Ïðîñòåéøèìèôóíêöèÿìè íàçûâàþòñÿ íóëüìåñòíàÿ ôóíêöèÿ 0,âñþäó îïðåäåë¼ííàÿ îäíîìåñòíàÿ ôóíêöèÿ s(x) = x + 1 è âñþäó îïðåäåë¼ííûå nnìåñòíûå ôóíêöèè Im(x1 , .
. . , xn ) = xm äëÿ âñåõ m, n òàêèõ, ÷òî 1 6 m 6 n.Îïðåäåëåíèå.41 12. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèèîïåðàòîðàÃîâîðÿò, ÷òî ôóíêöèÿ f (x1 , . . . , xn ) ïîëó÷àåòñÿ ñ ïîìîùüþS èç ôóíêöèé h(y1 , . . . , ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ), åñëè äëÿëþáûõ x1 , . . . , xn âûïîëíÿåòñÿ:Îïðåäåëåíèå.ñóïåðïîçèöèèf (x1 , . . .
, xn ) = h(g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )).Ñ íåôîðìàëüíîé òî÷êè çðåíèÿ îïåðàòîð ñóïåðïîçèöèè ñîîòâåòñòâóåòïðèíöèïó ïîñëåäîâàòåëüíîãî çàïóñêà âû÷èñëèòåëüíûõ óñòðîéñòâ, êîãäà ðåçóëüòàòûâû÷èñëåíèé îäíèõ óñòðîéñòâ ñëóæàò âõîäíûìè äàííûìè äëÿ äðóãèõ. Åñëè f ïîëó÷åíà ñ ïîìîùüþ ñóïåðïîçèöèè èç h, g1 , . . . , gm , òî âû÷èñëåíèå çíà÷åíèÿ f (x1 , . . . , xn )ïðîèñõîäèò ñëåäóþùèì îáðàçîì. Ñíà÷àëà íà âõîäíûõ äàííûõ x = hx1 , .
. . , xn i âû÷èñëÿþòñÿ çíà÷åíèÿ y1 = g1 (x), . . . , ym = gm (x). Åñëè õîòÿ áû îäíî èç ýòèõ çíà÷åíèé íåîïðåäåëåíî, òî çíà÷åíèå f (x) òîæå íå îïðåäåëåíî. Åñëè æå âñå y1 , . . . , ym îïðåäåëåíû,òî çàòåì îíè ïîäàþòñÿ íà âõîä ôóíêöèè h. Åñëè âûõîäíîå çíà÷åíèå h(y1 , . . .
, ym ) íåîïðåäåëåíî, òî f (x) ñ÷èòàåòñÿ íåîïðåäåë¼ííûì, èíà÷å f (x) = h(y1 , . . . , ym ) îïðåäåëåíî è ÿâëÿåòñÿ îêîí÷àòåëüíûì âûõîäíûì çíà÷åíèåì.Çàìå÷àíèå.Ãîâîðÿò, ÷òî ôóíêöèÿ f (x1 , . . . , xn , y) ïîëó÷àåòñÿ ñ ïîìîùüþ îïåðàòîðà ïðèìèòèâíîé ðåêóðñèè R èç ôóíêöèé g(x1, . . . , xn) è h(x1, . . . , xn, y, z), åñëè äëÿÎïðåäåëåíèå.ëþáûõ x1 , .
. . , xn , y âûïîëíÿåòñÿ ñõåìà ïðèìèòèâíîé ðåêóðñèè:(f (x1 , . . . , xn , 0) = g(x1 , . . . , xn )f (x1 , . . . , xn , y + 1) = h(x1 , . . . , xn , y, f (x1 , . . . , xn , y))Îïåðàòîð ïðèìèòèâíîé ðåêóðñèè ôîðìàëèçóåò öèêëè÷åñêóþ ñòðóêòóðó, âû÷èñëÿþùóþ ôóíêöèè, çàäàííûå ðåêóððåíòíûìè ñîîòíîøåíèÿìè (èëè ïî èíäóêöèè). Åñëè f ïîëó÷åíà ñ ïîìîùüþ ïðèìèòèâíîé ðåêóðñèè èç g è h, òî âû÷èñëåíèåçíà÷åíèÿ f (x, y) ïðîèñõîäèò ñëåäóþùèì îáðàçîì. Ñíà÷àëà íà âõîäíûõ äàííûõ x âû÷èñëÿåòñÿ çíà÷åíèå g(x), êîòîðîå ñîâïàäàåò ñ f (x, 0). Åñëè ýòî çíà÷åíèå íå îïðåäåëåíî, òî f (x, y) òîæå íå îïðåäåëåíî, èíà÷å, ïîäàâ x, 0 è f (x, 0) íà âõîä ôóíêöèè h, ìûâû÷èñëÿåì h(x, 0, f (x, 0)), êîòîðîå ñîâïàäàåò ñ f (x, 1).
Åñëè ïîñëåäíåå çíà÷åíèå íåîïðåäåëåíî, òî f (x, y) íå îïðåäåëåíî, èíà÷å ìû ïîäàåì x, 1 è f (x, 1) íà âõîä ôóíêöèèh, è òàê äàëåå. Äàííûå âû÷èñëåíèÿ ïðîäîëæàþòñÿ äî òåõ ïîð, ïîêà ìû íå äîñòèãíåìçíà÷åíèÿ f (x, y). Åñëè ïðè ýòîì íà ïðîìåæóòî÷íûõ øàãàõ õîòÿ áû îäíî âû÷èñëÿåìîåçíà÷åíèå ôóíêöèè h íå îïðåäåëåíî, òî f (x, y) ñ÷èòàåòñÿ íåîïðåäåë¼ííûì.Çàìå÷àíèå.îïåðà-Ãîâîðÿò, ÷òî ôóíêöèÿ f (x1 , . . . , xn ) ïîëó÷àåòñÿ ñ ïîìîùüþM èç ôóíêöèè g(x1 , . . . , xn , y) è îáîçíà÷àåòñÿ f (x1 , . . . , xn ) =µy[g(x1 , .
. . , xn , y) = 0], åñëè äëÿ ëþáûõ x1 , . . . , xn âûïîëíÿåòñÿ:Îïðåäåëåíèå.òîðà ìèíèìèçàöèèf (x1 , . . . , xn ) =y,íå îïðåäåëåíî,åñëè g(x1 , . . . , xn , 0), . . . , g(x1 , . . . , xn , y − 1)îïðåäåëåíû è íå ðàâíû 0, à çíà÷åíèåg(x1 , . . . , xn , y) îïðåäåëåíî è ðàâíî 0,â ïðîòèâíîì ñëó÷àå.Îïåðàòîð ìèíèìèçàöèè ïîñëåäîâàòåëüíî ïåðåáèðàåò ÷èñëà èç íàòóðàëüíîãî ðÿäà è ïðîâåðÿåò, óäîâëåòâîðÿåò ëè òåêóùåå ÷èñëî ôèêñèðîâàííîìó ýôôåêòèâíîìó óñëîâèþ. Ýôôåêòèâíîå óñëîâèå çàïèñûâàåòñÿ â âèäå óðàâíåíèÿ g(x, y) = 0.Âû÷èñëåíèå çíà÷åíèÿ f (x) ïðîèñõîäèò ñëåäóþùèì îáðàçîì.
Ñíà÷àëà íà âõîäíûõÇàìå÷àíèå.42Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèäàííûõ x, 0 âû÷èñëÿåòñÿ çíà÷åíèå g(x, 0). Åñëè ýòî çíà÷åíèå íå îïðåäåëåíî, òî f (x)òîæå íå îïðåäåëåíî. Èíà÷å åñëè g(x, 0) = 0, òî âû÷èñëåíèÿ çàêàí÷èâàþòñÿ ÷èñëî 0áóäåò ïîäàíî íà âûõîä. Åñëè æå g(x, 0) 6= 0, òî íà âõîäíûõ äàííûõ x, 1 âû÷èñëÿåòñÿçíà÷åíèå g(x, 1). Åñëè ýòî çíà÷åíèå íå îïðåäåëåíî, òî f (x) òîæå íå îïðåäåëåíî. Èíà÷ååñëè g(x, 1) = 0, òî âû÷èñëåíèÿ çàêàí÷èâàþòñÿ ÷èñëî 1 áóäåò ïîäàíî íà âûõîä.
Åñëè æå g(x, 1) 6= 0, òî äàííûé ïðîöåññ ïðîäîëæàåòñÿ.  ðåçóëüòàòå ìû ëèáî âû÷èñëèìíàèìåíüøåå ðåøåíèå óðàâíåíèÿ g(x, y) = 0, ëèáî íè÷åãî íå âû÷èñëèì. Ïîñëåäíååâîçìîæíî ïî äâóì ïðè÷èíàì: ëèáî íåêîòîðîå âû÷èñëÿåìîå çíà÷åíèå ôóíêöèè g îêàæåòñÿ íåîïðåäåë¼ííûì, ëèáî g(x, y) îïðåäåëåíî äëÿ âñåõ y , íî íå ðàâíî íóëþ.÷àñòè÷íî ðåêóðñèâíîé×àñòè÷íàÿ ôóíêöèÿ f (x1 , . . . , xn ) íàçûâàåòñÿ, åñëè ñóùåñòâóåò êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ôóíêöèéf0 , .
. . , fm = f òàêàÿ, ÷òî äëÿ ëþáîãî i 6 m ôóíêöèÿ fi ëèáî ïðîñòåéøàÿ, ëèáîïîëó÷àåòñÿ èç íåêîòîðûõ ïðåäûäóùèõ ñ ïîìîùüþ îäíîãî èç îïåðàòîðîâ S, R èëè M(îïåðàòîðîâ S èëè R).Îïðåäåëåíèå.(ïðèìèòèâíî ðåêóðñèâíîé)Îïðåäåëåíèå.êóðñèâíûìè.Âñþäó îïðåäåë¼ííûå ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè íàçûâàòñÿðå-Áóäåì èñïîëüçîâàòü ñîêðàùåíèÿ: ÷.ð.ô. äëÿ ÷àñòè÷íî ðåêóðñèâíûõôóíêöèé, ï.ð.ô.
äëÿ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé, ð.ô. äëÿ ðåêóðñèâíûõôóíêöèé.Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî åñëè ôóíêöèÿ f ïîëó÷àåòñÿ èç íåêîòîðûõ ÷.ð.ô.(ï.ð.ô.) ñ ïîìîùüþ îïåðàòîðà S, R èëè M (S èëè R), òî f òîæå ÿâëÿåòñÿ ÷.ð.ô.(ï.ð.ô.).Êðîìå ýòîãî, î÷åâèäíî, ìåæäó ââåä¼ííûìè êëàññàìè ôóíêöèé èìåþò ìåñòî ñëåäóþùèå òåîðåòèêî-ìíîæåñòâåííûå âêëþ÷åíèÿ:Çàìå÷àíèå.ÏÐÔ ⊆ ÐÔ ⊆ ×ÐÔ.×àñòî â ÷èñëî ïðîñòåéøèõ ôóíêöèé âêëþ÷àþò òàêæå îäíîìåñòíóþâñþäó îïðåäåë¼ííóþ ôóíêöèþ o(x) = 0. Çàìåòèì, ÷òî êëàññ ÷àñòè÷íî ðåêóðñèâíûõôóíêöèé ïðè ýòîì íå èçìåíÿåòñÿ.
Ýòî ñëåäóåò èç òîãî, ÷òî o(x) ìîæíî ïîëó÷èòü èç 0ìåñòíîé ôóíêöèè 0 è 2-ìåñòíîé ôóíêöèè I22 (x, y) ñ ïîìîùüþ îïåðàòîðà ïðèìèòèâíîéðåêóðñèè.Çàìå÷àíèå.Òåîðåìà 16(î âû÷èñëèìîñòè ÷.ð.ô. íà ìàøèíàõ Òüþðèíãà).Ëþáàÿ ÷àñòè÷íî ðå-êóðñèâíàÿ ôóíêöèÿ ÿâëÿåòñÿ âû÷èñëèìîé ïî Òüþðèíãó.Äîêàçàòåëüñòâî. Ïóñòü f ÷.ð.ô. Ñëåäîâàòåëüíî, ïî îïðåäåëåíèþ ñóùåñòâóåò êî-íå÷íàÿ ïîñëåäîâàòåëüíîñòü ôóíêöèé f0 , . . .
, fk = f òàêàÿ, ÷òî äëÿ ëþáîãî i 6 kôóíêöèÿ fi ëèáî ïðîñòåéøàÿ, ëèáî ïîëó÷àåòñÿ èç íåêîòîðûõ ïðåäûäóùèõ ñ ïîìîùüþ îïåðàòîðà S, R èëè M . Èíäóêöèåé ïî ÷èñëó k ∈ ω äîêàæåì, ÷òî f âû÷èñëèìàíà íåêîòîðîé ìàøèíå Òüþðèíãà.Åñëè k = 0, òî f ÿâëÿåòñÿ ïðîñòåéøåé, ò. å. ëèáî êîíñòàíòîé 0, ëèáî ôóíêöèåéns(x), ëèáî ôóíêöèåé âèäà Im(x1 , . . .
, xn ).Íóëüìåñòíàÿ êîíñòàíòà 0 âû÷èñëÿåòñÿ, íàïðèìåð, ïðîãðàììîé, ñîñòîÿùåé èç îäíîé êîìàíäû q1 0 → q0 0.Îäíîìåñòíàÿ ôóíêöèé s(x) âû÷èñëÿåòñÿ ñ ïîìîùüþ ñëåäóþùåé ïðîãðàììû:q1 0 → q2 0Rq2 1 → q2 1Rq2 0 → q3 1Rq3 0 → q4 0Lq4 1 → q4 1Lq4 0 → q0 043 12. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèènÌàøèíà, âû÷èñëÿþùàÿ ôóíêöèþ Im(x1 , . . . , xn ), ðàáîòàåò ïî ñëåäóþùåé ñõåìå:qα 01xm 0 .
. . 01xn 01x1 0 . . . 01xm−1 0 =⇒q1 01x1 0 . . . 01xm 0 . . . 01xn 0 =⇒+m−1(Á )n−1Ön=⇒ 01xm 0 . . . 01xn 01x1 0 . . . qβ 01xm−1 0(Á+ )n−1q0 01xm 0 . . . 0.=⇒(ηÁ− )n−1nÒàêèì îáðàçîì, ôóíêöèÿ Imâû÷èñëÿåòñÿ ñ ïîìîùüþ ñëåäóþùåé êîìïîçèöèè áàçîâûõ ìàøèí:(Ön )m−1 ◦ (Á+ )n−1 ◦ (Î ◦ Á− )n−1 .Ïóñòü k > 0. Òîãäà f ïîëó÷åíà èç íåêîòîðûõ ÷.ð.ô. ñ ïîìîùüþ îäíîãî èç òð¼õîïåðàòîðîâ.
Ðàññìîòðèì ñîîòâåòñòâóþùèå òðè ñëó÷àÿ.(1) Åñëè f (x1 , . . . , xn ) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà ñóïåðïîçèöèè èç ÷àñòè÷íûõôóíêöèé h(y1 , . . . , ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ), òî â ñèëó èíäóêöèîííîãîïðåäïîëîæåíèÿ ôóíêöèè h, g1 , . . . , gm âû÷èñëèìû íà ìàøèíàõ Òüþðèíãà H , G1 , . . .
,Gm ñîîòâåòñòâåííî. Òîãäà ñëåäóþùàÿ ìàøèíà Òüþðèíãà âû÷èñëÿåò ôóíêöèþ f :Ên ◦(Á+ )n ◦G1 ◦(Á− )n ◦(Ön+1 )n ◦Á+ ◦ . . . ◦ Ên ◦(Á+ )n ◦Gm−1 ◦(Á− )n ◦(Ön+1 )n ◦Á+ ◦◦Gm ◦(Á− )m−1 ◦H.(2) Åñëè f (x1 , . . . , xn , y) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà ïðèìèòèâíîé ðåêóðñèèèç ÷àñòè÷íûõ ôóíêöèé g(x1 , . . . , xn ) è h(x1 , . . . , xn , y, z), òî â ñèëó èíäóêöèîííîãîïðåäïîëîæåíèÿ ôóíêöèè g è h âû÷èñëèìû íà íåêîòîðûõ ìàøèíàõ Òüþðèíãà G è Hñîîòâåòñòâåííî.
Îïðåäåëèì ìàøèíó F , âû÷èñëÿþùóþ ôóíêöèþ f .Èñïîëüçóÿ áàçîâûå ìàøèíû, ìîæíî ïîñòðîèòü òàêèå ìàøèíû Òüþðèíãà T1 , T2 ,T3 , T4 , ÷òî ñõåìà ðàáîòû F âûãëÿäèò ñëåäóþùèì îáðàçîì:q1 01x1 0 . . . 01xn 01y 0 =⇒ 01x1 0 . . . 01xn 001y qα 01x1 0 . . . 01xn 0 =⇒T1Gx1xnyg(x)=⇒ 01 0 . . . 01 001 qβ 01G0 . .
. 0.Çàìåòèì, ÷òî ïðè i = 0 èìååò ìåñòî ðàâåíñòâî01x1 0 . . . 01xn 001y qβ 01g(x) 0 . . . 0 = 01x1 0 . . . 01xn 01i 01y−i qβ 01f (x,i) 0 . . . 0.Äàëåå, äëÿ ïðîèçâîëüíîãî i â ñîñòîÿíèè qβ ïðîâåðÿåì, åñòü ëè åù¼ åäèíèöû âìàññèâå 1y−i . Åñëè åäèíèöû åù¼ åñòü, òî ïåðåõîäèì â ñîñòîÿíèå qγ , åñëè íåò âñîñòîÿíèå qδ , ò.å. ïðîèñõîäèò ñëåäóþùåå ðàçâåòâëåíèå:01x1 0 . . . 01xn 01i 01y−i qβ 01f (x,i) 0 . . . 0 =⇒T2(01x1 0 . . . 01xn 01i 01y−i qγ 01f (x,i) 0 . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
