1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 10
Текст из файла (страница 10)
Ðàññìîòðèì ôóíêöèþ f , äëÿ êîòîðîé ñîîòâåòñòâóþùàÿ ïîñëåäîâàòåëüíîñòü f1 , . . . , fn = f èìååò äëèíó n. Ôóíêöèÿ f ïîëó÷àåòñÿèç ôóíêöèé ýòîé ïîñëåäîâàòåëüíîñòè ñ ìåíüøèìè íîìåðàìè ñ ïîìîùüþ3.2. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè55îäíîãî èç îïåðàòîðîâ S , R, M . Çàìåòèì, ÷òî äëÿ êàæäîé ôóíêöèè fi ,i < n ïîñëåäîâàòåëüíîñòü f1 , . . . , fi ïîäòâåðæäàåò ÷àñòè÷íóþ ðåêóðñèâíîñòü ôóíêöèè fi â ñîîòâåòñòâèè ñ îïðåäåëåíèåì ÷àñòè÷íî ðåêóðñèâíîéôóíêöèè. Ïî ïðåäïîëîæåíèþ èíäóêöèè ýòî îçíà÷àåò, ÷òî âñå ôóíêöèèfi , i < n âû÷èñëèìû íà ìàøèíå ؼíôèëäà. Èç çàìêíóòîñòè êëàññàôóíêöèé âû÷èñëèìûõ íà ìàøèíå ؼíôèëäà, îòíîñèòåëüíî îïåðàòîðîâS , R è M ñëåäóåò, ÷òî è ôóíêöèÿ f âû÷èñëèìà íà ìàøèíå ؼíôèëäà.Äîêàæåì òåïåðü èñïîëüçîâàííîå íàìè ïðåäïîëîæåíèå, à èìåííî, ÷òîêëàññ ôóíêöèé, âû÷èñëèìûõ íà ìàøèíå ؼíôèëäà, çàìêíóò îòíîñèòåëüíî îïåðàòîðîâ S, R, M.Çàìêíóòîñòü îòíîñèòåëüíî îïåðàòîðà ñóïåðïîçèöèè.
Åñëè ôóíêöèè f (y1 , . . . , ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ) âû÷èñëèìû íà ìàøèíàõ ؼíôèëäà, òî ñóïåðïîçèöèÿ f (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )) âû÷èñëÿåòñÿ ñëåäóþùåé ìàêðîïðîãðàììîé:0:g1 ([1],...,[k]) → [k+1]...n-1: gn ([1],...,[k]) → [k+m]n:f([k+1],...,[k+m]) → [0]Çàìêíóòîñòü îòíîñèòåëüíî îïåðàòîðà ïðèìèòèâíîé ðåêóðñèè. Çäåñüìû ðàññìîòðèì òîëüêî ñëó÷àé x̄ = x. Îáùèé ñëó÷àé ðàññìàòðèâàåòñÿàíàëîãè÷íî.
Åñëè ôóíêöèè g(x) è h(z, y, x) âû÷èñëèìû, òî ñëåäóþùàÿìàêðîïðîãðàììà âû÷èñëÿåò ôóíêöèþ f , îïðåäåëåííóþ ñõåìîé ïðèìèòèâíîé ðåêóðñèè·f (0, x)= g(x)f (y + 1, x) = h(f (y, x), y, x).0:1:2:3:4:5:6:7:8:g([2]) → [0][1] → [3]ZERO 1INC 0DEC 0,8h([0],[1],[2]) → [4][4] → [0]INC 1DEC 3,5×èòàòåëþ ïðåäëàãàåòñÿ ñàìîìó ïðîâåðèòü, ÷òî ýòà ïðîãðàììà ãîäèòñÿ.56Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÇàìêíóòîñòü îòíîñèòåëüíî îïåðàòîðà ìèíèìèçàöèè. Åñëè ôóíêöèÿ g(y, x1 , . . . , xk ) âû÷èñëèìà íà ìàøèíå ؼíôèëäà, òî íåòðóäíî óáåäèòüñÿ â òîì, ÷òî ñëåäóþùàÿ ìàêðîïðîãðàììà âû÷èñëÿåò ôóíêöèþf (x) = µy(g(y, x1 , .
. . , xk ) = 0) :0:1:2:3:4:5:ZERO 0INC 0DEC 0,4INC 0g([0],...,[k]) → [k+1]DEC k+1,3Òàêèì îáðàçîì, ìû ïîíÿëè, ÷òî âñÿêàÿ ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà. Îñòàåòñÿ óáåäèòüñÿ â îáðàòíîì, òî åñòü â òîì, ÷òî âñÿêàÿ ÷àñòè÷íàÿ ôóíêöèÿ, âû÷èñëèìàÿ íà ìàøèíå ؼíôèëäà ÿâëÿåòñÿ÷àñòè÷íî ðåêóðñèâíîé. Ýòà ÷àñòü äîêàçàòåëüñòâà òðåáóåò áîëüøåé ðóòèííîé ðàáîòû.
Ïðèìåðíûé ïëàí íàøèõ äåéñòâèé òàêîâ: ìû ïîñòðîèìíåêîòîðóþ êîäèðîâêó íàòóðàëüíûìè ÷èñëàìè (íóìåðàöèþ) ìàøèí è ñîñòîÿíèé ðåãèñòðîâ, ïðîöåññîâ âû÷èñëåíèé íà ìàøèíàõ è äîêàæåì, ÷òîïî íîìåðó ìàøèíû è ñîñòîÿíèþ ðåãèñòðîâ ìîæíî ñ ïîìîùüþ ÷àñòè÷íîðåêóðñèâíûõ ôóíêöèé ïåðåõîäèòü ê íîìåðó ñîñòîÿíèÿ ðåãèñòðîâ ÷åðåçîäèí øàã, îïðåäåëÿòü, ÿâëÿåòñÿ ëè äàííîå ÷èñëî êîäîì âû÷èñëåíèÿ íàäàííîé ìàøèíå è ò.ï. Èç ýòîãî â êîíöå êîíöîâ è ïîëó÷èòñÿ ÷àñòè÷íàÿðåêóðñèâíîñòü ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ ؼíôèëäà.Äëÿ íà÷àëà íàì ïîíàäîáèòñÿ ÷àñòè÷íàÿ ðåêóðñèâíîñòü íåêîòîðûõôóíêöèé. (Íà ñàìîì äåëå ìîæíî áåç îñîáîãî òðóäà äîêàçàòü äàæå ïðèìèòèâíóþ ðåêóðñèâíîñòü ýòèõ ôóíêöèé, íî çäåñü â ýòîì íåò íåîáõîäèìîñòè.)Ëåììà 3.2.6 Ñëåäóþùèå ôóíêöèè ÷àñòè÷íî ðåêóðñèâíû:1.
f (x) = a, a íàòóðàëüíîå ÷èñëî;2. x + y ;3. x × y ;4. xy ;½5. sg (x) =0,1,åñëè x = 0åñëè x =6 0;3.2. ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè½6. sg (x) =½7. x−̇1 =½8. x−̇y =1,0,57åñëè x = 0åñëè x =6 0;x − 1,0,åñëè x > 0åñëè x = 0;x − y,0,åñëè x > yåñëè x < y;9. |x − y|.Äîêàçàòåëüñòâî ëåììû. Ðåêóðñèâíîñòü ïîñòîÿííîé ôóíêöèè ñëåäóåòèç ðàâåíñòâà f (x) = s| .{z. .
s}(0(x)).a×àñòè÷íàÿ ðåêóðñèâíîñòü ôóíêöèé x+y è x×y ñëåäóåò èç ñëåäóþùèõðåêóðñèâíûõ îïðåäåëåíèé:·0+x= I11 (x)(y + 1) + x = I13 (s(y + x), y, x),·0×x= 0(x)(y + 1) × x = y × x + (0(y) + x).Ôóíêöèÿ xy ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Âîò ðåêóðñèâíîå îïðåäåëåíèå äëÿ sg :·sg (0)= 0sg (y + 1) = 1.Ôóíêöèÿ sg ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Äëÿ îñòàâøèõñÿ ôóíêöèé ëåììà ñëåäóåò èç ñïðàâåäëèâîñòè ñëåäóþùèõ îïðåäåëåíèé:·x−̇0= I11 (x)x−̇(y + 1) = I13 ((x−̇y)−̇1, y, x),|x − y| = (x−̇y) + (y −̇x).¤Îïðåäåëåíèå 3.2.7 Îòíîøåíèå R ⊆ Nk íàçûâàåòñÿ ðåêóðñèâíûì, åñ-ëè ðåêóðñèâíà åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ χR (x̄), îïðåäåëÿåìàÿ,êàê½1, åñëè x̄ ∈ PχR (x̄) =0, åñëè x̄ ∈/ P.58Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÒåïåðü íàì ïîíàäîáÿòñÿ íåêîòîðûå ñïîñîáû îïðåäåëåíèÿ íîâûõ ðåêóðñèâíûõ ôóíêöèé è îòíîøåíèé ïî óæå èìåþùèìñÿ ðåêóðñèâíûì ôóíêöèÿì è ïðåäèêàòàì.Ïðåäëîæåíèå 3.2.8 Åñëè îòíîøåíèå P ⊆ Nk ðåêóðñèâíî è ôóíêöèèf1 (ȳ), . . . , fk (ȳ) ðåêóðñèâíû, òî è îòíîøåíèå Q(ȳ), îïðåäåëåííîå, êàêQ(ȳ) ⇔ P (f1 (ȳ), . . . , fk (ȳ))òîæå ðåêóðñèâíî.Äîêàçàòåëüñòâî. Äîñòàòî÷íî çàìåòèòü, ÷òîχQ (ȳ) = χP (f1 (ȳ), .
. . , fk (ȳ)).¤Ëåììà 3.2.9 Åñëè îòíîøåíèÿ P (x̄) è Q(x̄) ðåêóðñèâíû, òî è îòíîøåíèÿ ¬P (x̄), P (x̄) & Q(x̄), P (x̄) ∨ Q(x̄), P (x̄) → Q(x̄) ðåêóðñèâíû.Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, χ¬P = 1−̇χP , χP& Q = χP · χQ ,χP ∨Q = χP + χQ −̇χP · χQ , îòêóäà ñëåäóåò ðåêóðñèâíîñòü ïåðâûõ òðåõ îòíîøåíèé. Äàëåå çàìåòèì, ÷òî P (x̄) → Q(x̄) ýêâèâàëåíòíî ¬P (x̄)∨Q(x̄), èðåêóðñèâíîñòü ïîñëåäíåãî îòíîøåíèÿ ñëåäóåò èç òîëüêî ÷òî äîêàçàííîãîñâîéñòâà. ¤Ïðåäëîæåíèå 3.2.10 Îòíîøåíèÿ =, 6=, <, >, 6, > ðåêóðñèâíû.Äîêàçàòåëüñòâî. Ñíà÷àëà çàìåòèì, ÷òî χ= (x, y) = sg |x − y|, îòêóäàñëåäóåò ðåêóðñèâíîñòü îòíîøåíèÿ =.Ðåêóðñèâíîñòü îñòàëüíûõ îòíîøåíèé ñëåäóåò èç ñëåäóþùèõ ðàâåíñòâè ýêâèâàëåíòíîñòåé: χ< (x, y) = sg (y −̇x), χ> (x, y) = sg (x−̇y), x 6 y ⇔x = y ∨ x < y, x > y ⇔ x = y ∨ x > y. ¤Ïðåäëîæåíèå 3.2.11 Åñëè g(i,Px̄) ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ,òî òàêîâà è ôóíêöèÿ f (n, x̄) =ñèâíà, òî òàêîâà æå è f .ni=0 g(i, x̄).Åñëè ôóíêöèÿ g(i, x̄) ðåêóð-3.2.
×àñòè÷íî ðåêóðñèâíûå ôóíêöèè59Äîêàçàòåëüñòâî. Ôóíêöèÿ f ìîæåò áûòü îïðåäåëåíà ñëåäóþùåé ñõå-ìîé ïðèìèòèâíîé ðåêóðñèè:·f (0, x̄)= g(0, x̄)f (n + 1, x) = f (n, x̄) + g(s(n), x̄). ¤Ïðåäëîæåíèå 3.2.12 Åñëè P (i, x̄) ðåêóðñèâíîå îòíîøåíèå, òî ðåêóðñèâíû è îòíîøåíèÿ ∃i 6 n P (i, x̄), ∀i 6 n P (i, x̄), ∃i < n P (i, x̄), ∀i <n P (i, x̄), çàâèñÿùèå îò n è i.Äîêàçàòåëüñòâî. Ëåãêî ïðîâåðÿåòñÿ, ÷òîÃχ∃i6n P (i,x̄) (i, x̄) = sgnX!χP (i, x̄) .i=0Ðåêóðñèâíîñòü îñòàëüíûõ îòíîøåíèé ñëåäóåò èç ïðåäûäóùèõ óòâåðæäåíèé è ñëåäóþùèõ î÷åâèäíûõ ýêâèâàëåíòíîñòåé:∀i 6 n P (i, x̄) ⇔ ¬∃i 6 n¬P (i, x̄).∃i < n P (i, x̄) ⇔ ∃i 6 n (P (i, x̄) & i 6= n).∀i < n P (i, x̄) ⇔ ¬∃i < n¬P (i, x̄). ¤Åñëè R(y, x̄) ðåêóðñèâíîå îòíîøåíèå, òî ìû áóäåì èñïîëüçîâàòüçàïèñü µyR(y, x̄) â êà÷åñòâå ñîêðàùåíèÿ äëÿ µy (|χR (y, x̄) − 1| = 0), ÷òîåñòåñòâåííî îçíà÷àåò ìèíèìàëüíîå y òàêîå, ÷òî R(y, x̄).Âîçìîæíîñòü èñïîëüçîâàíèÿ îãðàíè÷åííûõ êâàíòîðîâ, ïðåäîñòàâëÿåìàÿ ñëåäóþùèì ïðåäëîæåíèåì, ñóùåñòâåííî óïðîñòèò íàì äîêàçàòåëüñòâî ðåêóðñèâíîñòè îïðåäåëÿåìûõ â äàëüíåéøåì ôóíêöèé è ïðåäèêàòîâ.Ïðåäëîæåíèå 3.2.13ñèâíî.2.
Ôóíêöèÿ1. Îòíîøåíèå div (x, y) ( x äåëèò y ) ðåêóð-h ixy(íåïîëíîå ÷àñòíîå îò äåëåíèÿ x íà y . Ïðè ýòîì ïî£x¤îïðåäåëåíèþ 0 = x) ðåêóðñèâíà.3. Îòíîøåíèå Prime (x), âûäåëÿþùåå ïðîñòûå ÷èñëà, ðåêóðñèâíî.60Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÄîêàçàòåëüñòâî. Äîñòàòî÷íî çàìåòèòü, ÷òîdiv (x, y) ⇔ ∃t 6 y(x × t = y),· ¸x= µz(z = x ∨ (z + 1) × y > x),yPrime (x) ⇔ (x 6= 0) & (x 6= 1) &∀y 6 x(div (x, y) → (y = 1 ∨ y = x)).¤Ïðåäëîæåíèå 3.2.141. Ôóíêöèÿ, pi , âûäàþùàÿ iå ïðîñòîå ÷èñëîïî i (p0 = 2, p1 = 3, p2 = 5, . .
. ) ðåêóðñèâíà.2. Ôóíêöèÿ ex (i, x), ðàâíàÿ ïîêàçàòåëþ, ñ êîòîðûì pi âõîäèò â ðàçëîæåíèå ÷èñëà x íà ïðîñòûå ìíîæèòåëè, ðåêóðñèâíà. (Ìû ïîëàãàåì ïî îïðåäåëåíèþ ex (i, 0) = 0.)Äîêàçàòåëüñòâî. Âîò ðåêóðñèâíîå îïðåäåëåíèå äëÿ pi :·p0= 2pi+1 = µy(Prime (y) & y > pi ).À âîò îïðåäåëåíèå äëÿ ex :ex (i, x) = µy(¬div (py+1, x) ∨ x = 0).i(åñëè íå äîáàâèòü x = 0, òî ex (i, 0) áûëî áû íå îïðåäåëåíî). ¤Ïðåäëîæåíèå 3.2.15 (Îïðåäåëåíèå ôóíêöèè ðàçáîðîì ñëó÷àåâ)Ïóñòü P1 (x1 , .
. . , xn ), . . . Pm (x1 , . . . , xn ) ðåêóðñèâíûå îòíîøåíèÿ òàêèå, ÷òî äëÿ ëþáîãî íàáîðà íàòóðàëüíûõ ÷èñåë x1 , . . . , xn ñóùåñòâóåòðîâíî îäíî çíà÷åíèå i ∈ {1, . . . , m} òàêîå, ÷òî Pi (x1 , . . . , xn ). Ïóñòüòàêæå f1 (x1 , . . . , xn ), . . . , fm (x1 , . . . , xn ) ðåêóðñèâíûå ôóíêöèè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
