1610906281-01dbea734f4ec795a743bdccea0de373 (Частично рекурсивные функции)

1×àñòè÷íî ðåêóðñèâíûå ôóíêöèè×àñòè÷íî ðåêóðñèâíûå ôóíêöèè îäíà èç ñàìûõ ïîïóëÿðíûõ ôîðìàëèçàöèé ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè.Îïðåäåëåíèå ýòîãî êëàññà ïîñòðîåíî ñëåäóþùèì îáðàçîì. Ñíà÷àëàìû îïðåäåëèì òàê íàçûâàåìûå ïðîñòåéøèå ôóíêöèè, â èíòóèòèâíîéâû÷èñëèìîñòè êîòîðûõ òðóäíî óñîìíèòüñÿ, à ïîòîì îïðåäåëèì òðè îïåðàòîðà íàä ôóíêöèÿìè, ïðèìåíåíèå êîòîðûõ ê âû÷èñëèìûì ôóíêöèÿìñíîâà äàåò âû÷èñëèìûå ôóíêöèè.

Íàèìåíüøèé êëàññ ôóíêöèé, ñîäåðæàùèé ïðîñòåéøèå ôóíêöèè è çàìêíóòûé îòíîñèòåëüíî ýòèõ îïåðàòîðîâ èáóäåò êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.Îïðåäåëåíèå 1.1xm ,äëÿ âñåõn (x , . . . , x ) =0(x) = 0, s(x) = x + 1 è Im1nm, n ∈ N òàêèõ, ÷òî 1 6 m 6 n, íàçûâàþòñÿ ïðîñòåéøèÔóíêöèèìè.Òåïåðü îïðåäåëèì òðè îñíîâíûõ îïåðàòîðà äëÿ ïîëó÷åíèÿ íîâûõ âû÷èñëèìûõ ôóíêöèé èç óæå èìåþùèõñÿ.Îïðåäåëåíèå 1.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̄).1 ÷àñòíîì ñëó÷àå, êîãäà íàáîð ïåðåìåííûõx̄ïóñò, ñõåìà âûðîæ-äàåòñÿ âãäåaf (0)= af (y + 1) = h(f (y), y),f (n, x̄) ñîñòîèòf (0, x̄), f (1, x̄), . . . , f (n, x̄) ÷åðåç íåêîòîðàÿ êîíñòàíòà. Âû÷èñëåíèå çíà÷åíèÿâ ïîñëåäîâàòåëüíîì îïðåäåëåíèèóæå âû÷èñëåííûå ïðåäûäóùèå çíà÷åíèÿ. Åñëè îäíî èç ýòèõ çíà÷åíèé îêàæåòñÿ íåîïðåäåëåííûì, òî èf (n, x̄)òîæå áóäåò íåîïðå-äåëåíî.Îïåðàòîð ìèíèìèçàöèè M (µîïåðàòîð)ñòè÷íàÿ ôóíêöèÿg(z, x̄).Ïóñòü çàäàíà íåêîòîðàÿ ÷à- ðåçóëüòàòå ïðèìåíåíèÿ îïåðàòîðà ìè-íèìèçàöèè ìû ïîëó÷àåì íîâóþ ôóíêöèþ, êîòîðàÿ âû÷èñëÿåòñÿñëåäóþùèì îáðàçîì:∀i < y g(i, x̄)f (x̄) = yòîãäà è òîëüêî òîãäà, êîãäàîïðåäåëåíî è íå ðàâíîÌû èñïîëüçóåì äëÿµîïåðàòîðà0 ∧ g(y, x̄) = 0 .ñëåäóþùóþ çàïèñü:f (x̄) ' µy(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.

Òîãäà,àêêóðàòíî âûïîëíÿÿ ïðîöåññ âû÷èñëåíèÿ ôóíêöèè2h(x) = µy(g(y, x) =0)ïðèx = 0,÷òîg(0) íå îïðåäåëåíî! Ïîýòîìó òðàµy(g(y, x) = 0), êàê ¾ìèíèìàëüíîå y òàêîå,ïîëó÷èì, ÷òî çíà÷åíèåäèöèîííîå ïðî÷òåíèå çàïèñèg(y, x) = 0¿,ñîäåðæèò â ñåáå îïàñíîñòü íåïðàâèëüíîãî ïîíèìàíèÿîïðåäåëåíèÿ îïåðàòîðà ìèíèìèçàöèè.Îïðåäåëåíèå 1.3×àñòè÷íàÿ ôóíêöèÿf : Nk → Níàçûâàåòñÿ ÷à-ñòè÷íî ðåêóðñèâíîé (ïðèìèòèâíî ðåêóðñèâíîé),åñëè ñóùåñòâóåò êî-íå÷íàÿ ïîñëåäîâàòåëüíîñòü ÷àñòè÷íûõ ôóíêöèéf1 , . .

. , fn = fòàêàÿ,÷òî âñÿêàÿ ôóíêöèÿ â ýòîé ïîñëåäîâàòåëüíîñòè ëèáî ïðîñòåéøàÿ, ëèáî ïîëó÷àåòñÿ èç ôóíêöèé ñ ìåíüøèìè íîìåðàìè ñ ïîìîùüþ îäíîãî èçîïåðàòîðîâ S,R,M (îïåðàòîðîâ S,R)Çàìå÷àíèå.Èç îïðåäåëåíèÿ ëåãêî ñëåäóåò, ÷òî âñå ïðèìèòèâíî ðåêóð-ñèâíûå ôóíêöèè âñþäó îïðåäåëåíû.Îïðåäåëåíèå 1.4Ôóíêöèÿ íàçûâàåòñÿ îáùåðåêóðñèâíîé (èëè ïðîñòîðåêóðñèâíîé), åñëè îíà ÷àñòè÷íî ðåêóðñèâíà è âñþäó îïðåäåëåíà.Çàìå÷àíèå.Ïåðâîíà÷àëüíî äàííûå èññëåäîâàòåëÿìè îïðåäåëåíèÿ îá-ùåðåêóðñèâíîé è ðåêóðñèâíîé ôóíêöèé ðàçëè÷àëèñü, íî âïîñëåäñòâèèáûëî äîêàçàíî.

÷òî êëàññû ýòèõ ôóíêöèé ñîâïàäàþò, ïîýòîìó ñåãîäíÿîáà òåðìèíà èñïîëüçóþòñÿ êàê ñèíîíèìû.Ìû èñïîëüçóåì ñëåäóþùèå ñîêðàùåíèÿ: ÷.ð.ô. äëÿ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé, ð.ô. (î.ð.ô.) äëÿ ðåêóðñèâíûõ (îáùåðåêóðñèâíûõ) ôóíêöèé, ï.ð.ô. äëÿ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé.Ëåììà 1.5Ñëåäóþùèå ôóíêöèè ïðèìèòèâíî ðåêóðñèâíû:1.f (x) = a, a2.x + y;3.x × y;4.xy ;sg (x) =6.sg (x) =7.x−̇1 =5.

íàòóðàëüíîå ÷èñëî;0,1,åñëè1,0,åñëèx − 1,0,åñëèåñëèx=0x 6= 0;x=0x 6= 0;åñëèåñëèx>0x = 0;38.x−̇y =9.|x − y|.x − y,0,åñëèåñëèx>yx < y;Äîêàçàòåëüñòâî ëåììû. Ðåêóðñèâíîñòü ïîñòîÿííîé ôóíêöèè ñëåäóåòèç ðàâåíñòâàf (x) = s| .{z. .

s}(0(x)).a×àñòè÷íàÿ ðåêóðñèâíîñòü ôóíêöèéx+y è x×y ñëåäóåò èç ñëåäóþùèõðåêóðñèâíûõ îïðåäåëåíèé:Ôóíêöèÿxy0+x= I11 (x)(y + 1) + x = I13 (s(y + x), y, x),0×x= 0(x)(y + 1) × x = y × x + (0(y) + x).ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Âîò ðåêóðñèâíîå îïðåäåëåíèå äëÿÔóíêöèÿsgsg :sg (0)= 0sg (y + 1) = 1.ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Äëÿ îñòàâøèõñÿ ôóíêöèé ëåììà ñëåäóåò èç ñïðàâåäëèâîñòè ñëåäóþùèõ îïðåäåëåíèé:x−̇0= I11 (x)x−̇(y + 1) = I13 ((x−̇y)−̇1, y, x),|x − y| = (x−̇y) + (y −̇x).Îïðåäåëåíèå 1.6ÎòíîøåíèåR ⊆ Nkíàçûâàåòñÿ ïðèìèòèâíî ðåêóð-ñèâíûì (ðåêóðñèâíûì), åñëè ïððèìèòèâíî ðåêóðñèâíà (ðåêóðñèâíà) åãîχR (x̄), îïðåäåëÿåìàÿ,1, åñëè x̄ ∈ RχR (x̄) =0, åñëè x̄ ∈/ R.õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿêàêÒåïåðü íàì ïîíàäîáÿòñÿ íåêîòîðûå ñïîñîáû îïðåäåëåíèÿ íîâûõ ðåêóðñèâíûõ ôóíêöèé è îòíîøåíèé ïî óæå èìåþùèìñÿ ðåêóðñèâíûì ôóíêöèÿì è îòíîøåíèÿì.4Ïðåäëîæåíèå 1.7è ôóíêöèèQ(ȳ),f1 (ȳ),P ⊆ NkÅñëè îòíîøåíèå...,fk (ȳ)(ïðèìèòèâíî) ðåêóðñèâíî(ïðèìèòèâíî) ðåêóðñèâíû, òî è îòíîøåíèåîïðåäåëåííîå, êàêQ(ȳ) ⇔ P (f1 (ȳ), .

. . , fk (ȳ))òîæå (ïðèìèòèâíî) ðåêóðñèâíî.Äîêàçàòåëüñòâî.Äîñòàòî÷íî çàìåòèòü, ÷òîχQ (ȳ) = χP (f1 (ȳ), . . . , fk (ȳ)).Òåïåðü íàì ïîíàäîáèòñÿ íåáîëüøîé ýêñêóðñ â ìàòåìàòè÷åñêóþ ëîãèêó. Ñíà÷àëà ïîçíàêîìèìñÿ ñ ïîíÿòèåì âûñêàçûâàíèÿ. Ïðåäëîæåíèÿ,îòíîñèòåëüíî êîòîðûõ â ïðèíöèïå èìååò ñìûñë ãîâîðèòü, ÷òî îíè ëèáî èñòèííû ëèáî ëîæíû, íàçûâàþòñÿ âûñêàçûâàíèÿìè. Òàê íàïðèìåð,¾2× 2 = 4¿, ¾7 × 8 = 972¿,¾Â Ëîíäîíå ñåé÷àñ ñîëíå÷íî¿ âûñêàçûâàíè-ÿìè ÿâëÿþòñÿ, ïðè÷¼ì íåçàâèñèìî îò ïîãîäû â Ëîíäîíå, à åñåíèíñêàÿñòðî÷êà ¾Äàé, Äæèì, íà ñ÷àñòüå ëàïó ìíå!¿ âûñêàçûâàíèåì íå ÿâëÿåòñÿ. êëàññè÷åñêîé ëîãèêå îáû÷íî ðàññìàòðèâàþòñÿ äâà çíà÷åíèÿ èñòèííîñòè: È (èñòèíà) è Ë (ëîæü). Ìû áóäåì îáîçíà÷àòü ýòèìè áóêâàìèñîîòâåòñòâåííî èñòèííîñòü èëè ëîæíîñòü âûñêàçûâàíèÿ.Èç âûñêàçûâàíèé ìîæíî ñòðîèòü áîëåå ñëîæíûå âûñêàçûâàíèÿ ñ ïîìîùüþ ëîãè÷åñêèõ ñâÿçîê→∧(È, êîíúþíêöèÿ),¬(ÅÑËÈ .

. . , ÒÎ . . . , èìïëèêàöèÿ),∨(ÈËÈ, äèçúþíêöèÿ),(ÍÅÂÅÐÍÎ, ×ÒÎ , . . . , îòðèöà-íèå).Ïðè ýòîì çíà÷åíèÿ èñòèííîñòè ñëîæíûõ âûñêàçûâàíèé âû÷èñëÿþòñÿïî çíà÷åíèÿì èõ êîìïîíåíòîâÇàïèñüP (x̄),AèBñîãëàñíî ñëåäóþùåé òàáëèöå:ABA∧BA∨BA→B¬AÈÈÈÈÈËÈËËÈËËËÈËÈÈÈËËËËÈÈîçíà÷àþùàÿ, ÷òî êîðòåæ ýëåìåíòîâx̄ïðèíàäëåæèòP,ìîæíî ðàññìàòðèâàòü, êàê âûñêàçûâàíèå, åñëè èçâåñòíû çíà÷åíèÿ ýëå-x̄, ò.å. êàê âûñêàçûâàíèå, çàâèñÿùåå îò ýòèõ ýëåìåíòîâ.

Îáðàòíî,x̄, ìîæíî ðàññìàòðèêàê îòíîøåíèå, ñîñòîÿùåå èç âñåõ êîðòåæåé x̄, äåëàþùèõ ýòî âû-ìåíòîâêàæäîå âûñêàçûâàíèå, çàâèñÿùåå îò ïåðåìåííûõâàòüñêàçûâàíèå èñòèííûì.5Çàìåòèì, ÷òî âûñêàçûâàíèÿA → Bè¬A ∨ Bâñåãäà ïðèíèìàþòîäíè è òå æå çíà÷åíèÿ èñòèííîñòè, ÷òî ëåãêî ïðîâåðÿåòñÿ ïåðåáîðîìâñåâîçìîæíûõ íàáîðîâ çíà÷åíèÿ èñòèííîñòè äëÿËåììà 1.8AèB.P (x̄) è Q(x̄) (ïðèìèòèâíî) ðåêóðñèâíû,¬P (x̄), P (x̄) ∧ Q(x̄), P (x̄) ∨ Q(x̄), P (x̄) → Q(x̄) (ïðè-Åñëè îòíîøåíèÿòî è îòíîøåíèÿìèòèâíî) ðåêóðñèâíû.Äîêàçàòåëüñòâî. Äåéñòâèòåëüíî, χ¬P = 1−̇χP , χPχP + χQ −̇χP · χQ ,âûõ òðåõ îòíîøåíèé. Äàëåå çàìåòèì, ÷òî¬P (x̄) ∨ Q(x̄),∧ Q= χP ·χQ , χP ∨Q =îòêóäà ñëåäóåò (ïðèìèòèâíàÿ) ðåêóðñèâíîñòü ïåð-P (x̄) → Q(x̄)ýêâèâàëåíòíîè (ïðèìèòèâíàÿ) ðåêóðñèâíîñòü ïîñëåäíåãî îòíîøåíèÿñëåäóåò èç òîëüêî ÷òî äîêàçàííîãî ñâîéñòâà.Ïðåäëîæåíèå 1.9Äîêàçàòåëüñòâî.Îòíîøåíèÿ=, 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.