1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 11
Текст из файла (страница 11)
0, åñëè y − i > 0,=⇒T201x1 0 . . . 01xn 01i 01y−i qδ 01f (x,i) 0 . . . 0, åñëè y − i = 0. ñîñòîÿíèè qγ , èñïîëüçóÿ ìàøèíó H , ïåðåõîäèì ê ñëåäóþùåé èòåðàöèè â öèêëå:q1 01x1 0 . . . 01xn 01i 01y−i qγ 01f (x,i) 0 . . . 0 =⇒T3x1xni+1=⇒ 01 0 . . . 01 01T3x1y−(i+1)01xnqε 01 0 .
. . 01 01 01f (x,i) 0 . . . 0 =⇒xniHi+1=⇒ 01 0 . . . 01 01Hx1y−(i+1)01f (x,i+1)qβ 010 . . . 0.44Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè ñîñòîÿíèè qδ âûõîäèì èç öèêëà:01x1 0 . . . 01xn 01y 0qδ 01f (x,y) 0 . . . 0 =⇒ q0 01f (x,y) 0 . . . 0.T4Òàêèì îáðàçîì, F = T1 ◦ G ◦ T2 [qγ → T3 ◦ H|qδ → T4 ].(3) Åñëè ôóíêöèÿ f (x1 , . . . , xn ) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà ìèìèìèçàöèè èç÷àñòè÷íîé ôóíêöèè g(x1 , . . . , xn , y), òî â ñèëó èíäóêöèîííîãî ïðåäïîëîæåíèÿ, ñóùåñòâóåò ìàøèíà Òüþðèíãà G, âû÷èñëÿþùàÿ g . Îïðåäåëèì ìàøèíó F , âû÷èñëÿþùóþôóíêöèþ f .Èñïîëüçóÿ áàçîâûå ìàøèíû, ìîæíî ïîñòðîèòü òàêèå ìàøèíû Òüþðèíãà T1 , T2 ,T3 , T4 , ÷òî ñõåìà ðàáîòû F âûãëÿäèò ñëåäóþùèì îáðàçîì:q1 01x1 0 . . . 01xn 0 =⇒ 01x1 0 .
. . 01xn 0qα 01x1 0 . . . 01xn 00.T1Çàìåòèì, ÷òî ïðè i = 0 èìååò ìåñòî ðàâåíñòâî01x1 0 . . . 01xn 0qα 01x1 0 . . . 01xn 00 = 01x1 0 . . . 01xn 01i qα 01x1 0 . . . 01xn 01i 0.Äàëåå, äëÿ ïðîèçâîëüíîãî i â ñîñòîÿíèè qα çàïóñêàåì ìàøèíó G:01x1 0 . . . 01xn 01i qα 01x1 0 . . . 01xn 01i 0 =⇒ 01x1 0 . . . 01xn 01i qβ 01g(x,i) 0 . . . 0.GÅñëè ìàøèíà G îñòàíîâèëàñü, òî â ñîñòîÿíèè qβ ïðîâåðÿåì, âûïîëíÿåòñÿ ëè òîæäåñòâî g(x1 , . .
. , xn , i) = 0. Åñëè g(x1 , . . . , xn , i) > 0, òî ïåðåõîäèì â ñîñòîÿíèå qγ .Åñëè æå g(x1 , . . . , xn , i) = 0, òî ïåðåõîäèì â ñîñòîÿíèå qδ , ò.å. ïðîèñõîäèò ñëåäóþùååðàçâåòâëåíèå:(01x1 0 . . . 01xn 01i qγ 01g(x,i) 0 . . . 0, åñëè g(x, i)>0,x1xnig(x,i)0 . . . 0 =⇒01 0 . . . 01 01 qβ 01T201x1 0 . . . 01xn 01i qδ 01g(x,i) 0 . . . 0, åñëè g(x, i)=0. ñîñòîÿíèè qγ ïåðåõîäèì ê ñëåäóþùåé èòåðàöèè â öèêëå:01x1 0 . . . 01xn 01i qγ 01g(x,i) 0 . . . 0 =⇒ 01x1 0 . .
. 01xn 01i+1 qα 01x1 0 . . . 01xn 01i+1 0.T3 ñîñòîÿíèè qδ âûõîäèì èç öèêëà:01x1 0 . . . 01xn 01i qδ 00 . . . 0 =⇒ q0 01i 0 . . . 0.T4Òàêèì îáðàçîì, F = T1 ◦ G ◦ T2 [qγ → T3 |qδ → T4 ].Òåîðåìà äîêàçàíà. 13.Ðåêóðñèâíîñòü íåêîòîðûõ ôóíêöèé è îòíîøåíèéÍàøåé äàëüíåéøåé öåëüþ ÿâëÿåòñÿ äîêàçàòåëüñòâî óòâåðæäåíèÿ, îáðàòíîãî òåîðåìå16. Äëÿ ýòîãî íàì ïîòðåáóåòñÿ öåëàÿ ñåðèÿ ïðåäâàðèòåëüíûõ ôàêòîâ è íîâûõ ïîíÿòèé.
Âñþäó äàëåå ÷åðåç x ìû îáîçíà÷àåì êîðòåæ hx1 , . . . , xn i, ïðè n = 0 ýòîò êîðòåæñ÷èòàåòñÿ ïóñòûì. 13. Ðåêóðñèâíîñòü íåêîòîðûõ ôóíêöèé è îòíîøåíèé45Âñå íóëüìåñòíûå âñþäó îïðåäåëåííûå ôóíêöèè ÿâëÿþòñÿ ïðèìèòèâíîðåêóðñèâíûìè.Äîêàçàòåëüñòâî.
Ïóñòü a ∈ ω ïðîèçâîëüíàÿ êîíñòàíòà. Âîçìîæíû äâà ñëó÷àÿ.Ëåììà 17.Åñëè a = 0, òî ýòî ïî îïðåäåëåíèþ ïðîñòåéøàÿ ôóíêöèÿ, è çíà÷èò îíà ÿâëÿåòñÿï.ð.ô. Åñëè æå a > 0, òî a = s(s . . . s(0) . . .), ò. å. a ïîëó÷åíà èç ïðîñòåéøèõ ôóíêöèé| {z }a0 è s(x) ñ ïîìîùüþ a-êðàòíîãî ïðèìåíåíèÿ îïåðàòîðà S .Ëåììà 18.Ñëåäóþùèå ôóíêöèè ÿâëÿþòñÿ ïðèìèòèâíî ðåêóðñèâíûìè:à) f (x, y) = x + y ;á) f (x, y) = x · y ;â) f (x, y) =(xy (çäåñü 00 = 1);0, x = 0;ã) sg(x) =1, x > 0;(1, x = 0;ä) sg(x) =0, x > 0;(0,x = 0;å) f (x) = x−1=x − 1, x > 0;(0,x 6 y;æ) f (x, y) = x−y=x − y, x > y;ç) f (x, y) = |x − y|Äîêàçàòåëüñòâî. à) Äëÿ ôóíêöèè f (x, y)= x + y èìååò ìåñòî ñëåäóþùàÿ ñõåìàïðèìèòèâíîé ðåêóðñèè:(f (x, 0) = x,f (x, y + 1) = (x + y) + 1 = s(f (x, y)) = s(I33 (x, y, f (x, y))),ò.
å. f (x, y) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà R èç ï.ð.ô. g(x) = x = I11 (x) è ï.ð.ô.h(x, y, z) = s(I33 (x, y, z)), êîòîðàÿ, â ñâîþ î÷åðåäü, ïîëó÷åíà èç ïðîñòåéøèõ ôóíêöèés è I33 ñ ïîìîùüþ îïåðàòîðà S .á) Äëÿ ôóíêöèè f (x, y) = x · y èìååò ìåñòî ñëåäóþùàÿ ñõåìà ïðèìèòèâíîé ðåêóðñèè:(f (x, 0) = 0,f (x, y + 1) = xy + x = ϕ(xy, x) = ϕ(I33 (x, y, f (x, y)), I13 (x, y, f (x, y))),ãäå ϕ(u, v) = u + v ï.ð.ô. èç ïðåäûäóùåãî ïóíêòà, ò.
å. f (x, y) ïîëó÷åíà ñ ïîìîùüþîïåðàòîðà R èç ï.ð.ô. g(x) = 0 = o(x) è ï.ð.ô. h(x, y, z)=ϕ(I33 (x, y, z), I13 (x, y, z)),êîòîðàÿ, â ñâîþ î÷åðåäü, ïîëó÷åíà èç ï.ð.ô. ϕ, I33 , I13 ñ ïîìîùüþ îïåðàòîðà S .â) Äîêàçûâàåòñÿ àíàëîãè÷íî ïóòåì âûïèñûâàíèÿ ñîîòâåòñòâóþùåé ñõåìû ïðèìèòèâíîé ðåêóðñèè.ã) Âûïèñûâàåì ñõåìó ïðèìèòèâíîé ðåêóðñèè:(sg(0) = 0,sg(x + 1) = 1 = s(0) = s(o(I12 (x, sg(x)))).46Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÄðóãèìè ñëîâàìè, sg(x) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà R èç 0-ìåñòíîé ôóíêöèè 0,êîòîðàÿ ÿâëÿåòñÿ ïðîñòåéøåé, è 2-ìåñòíîé ôóíêöèè s(o(I12 (x, y))), êîòîðàÿ ÿâëÿåòñÿï.ð.ô., ïîñêîëüêó ïîëó÷åíà ñóïåðïîçèöèÿìè èç ï.ð.ô.ä) Âûïèñûâàåì ñõåìó ïðèìèòèâíîé ðåêóðñèè:(sg(0) = 1,sg(x + 1) = 0 = o(I12 (x, sg(x))).Òàêèì îáðàçîì, sg(x) ïîëó÷åíà ñ ïîìîùüþ îïåðàòîðà R èç 0-ìåñòíîé ôóíêöèè 1,êîòîðàÿ ÿâëÿåòñÿ ï.ð.ô.
â ñèëó ïðåäûäóùåé ëåììû, è 2-ìåñòíîé ôóíêöèè o(I12 (x, y)),êîòîðàÿ ÿâëÿåòñÿ ï.ð.ô., òàê êàê ïîëó÷åíà ñóïåðïîçèöèÿìè èç ï.ð.ô.å) Äîêàçûâàåòñÿ àíàëîãè÷íî.æ) Îáîçíà÷èì f (x, y) = x−y . Òîãäà èìååò ìåñòî ñõåìà ïðèìèòèâíîé ðåêóðñèè:(f (x, 0) = x = I11 (x),f (x, y + 1) = x−(y + 1) = (x−y)−1 = ψ(f (x, y)),ãäå ψ(u) = u−1 ï.ð.ô. èç ïðåäûäóùåãî ïóíêòà. Âûøå ìû âîñïîëüçîâàëèñü òîæäåñòâîì x−(y + 1) = (x−y)−1, êîòîðîå âåðíî äëÿ ëþáûõ x, y ∈ ω .ç) Çàìåòèì, ÷òî |x − y| = (x−y) + (y−x) ñóïåðïîçèöèÿ ïðèìèòèâíî ðåêóðñèâíûõôóíêöèé.Åñëè ôóíêöèÿg(x, y) ÿâëÿåòñÿ ÷.ð.ô. (ï.ð.ô.), òî ôóíêöèè f (x, y) =yQg(x, i) è h(x, y) =g(x, i) òîæå ÿâëÿþòñÿ ÷.ð.ô. (ï.ð.ô.).Ëåììà 19.yPi=0i=0Äîêàçàòåëüñòâî. ×àñòè÷íàÿ (ïðèìèòèâíàÿ) ðåêóðñèâíîñòü ôóíêöèè f âûòåêàåò èçïóíêòà (à) ëåììû 18 è ñëåäóþùåé ñõåìû ïðèìèòèâíîé ðåêóðñèè:(f (x, 0) = g(x, 0),f (x, y + 1) = f (x, y) + g(x, y + 1).Óòâåðæäåíèå äëÿ ôóíêöèè h äîêàçûâàåòñÿ àíàëîãè÷íî ñ èñïîëüçîâàíèåì ïóíêòà (á)ëåììû 18.îãðàíè÷åííîé ìè-Ãîâîðÿò, ÷òî ôóíêöèÿ f (x) ïîëó÷àåòñÿ ñ ïîìîùüþèç âñþäó îïðåäåë¼ííûõ ôóíêöèé g(x, y) è h(x), è îáîçíà÷àåòñÿ f (x) =µy 6 h(x)[g(x, y) = 0], åñëè äëÿ ëþáûõ çíà÷åíèé x âûïîëíÿåòñÿ:(y,åñëè g(x, i) 6= 0 äëÿ âñåõ i < y, g(x, y) = 0, è y 6 h(x),f (x) =h(x) + 1, â ïðîòèâíîì ñëó÷àå.Îïðåäåëåíèå.íèìèçàöèèÅñëè ôóíêöèè g è h ïðèìèòèâíî ðåêóðñèâíû è ôóíêöèÿ ïîëó÷åíà èç è ñ ïîìîùüþ îãðàíè÷åííîé ìèíèìèçàöèè, òî f òîæå ïðèìèòèâíî ðåêóðñèâíà.Äîêàçàòåëüñòâî.
Äîêàæåì, ÷òî äëÿ ëþáûõ x1, . . . , xn ñïðàâåäëèâî òîæäåñòâîÏðåäëîæåíèå 20(îá îãðàíè÷åííîé ìèíèìèçàöèè).fg hf (x) =h(x)Xi=0sgiYj=0g(x, j) . (∗) 13. Ðåêóðñèâíîñòü íåêîòîðûõ ôóíêöèé è îòíîøåíèé47QÅñëè f (x) = y 6 h(x), òî äëÿ âñåõ i < y ñïðàâåäëèâî ij=0 g(x, j) > 0 è çíà÷èòQQsg ij=0 g(x, j) = 1, à äëÿ âñåõ i > y èìååò ìåñòî ij=0 g(x, j) = 0. Ñëåäîâàòåëüíî, âïðàâîé ÷àñòè òîæäåñòâà (∗) åäèíèöàñóììèðóåòñÿ y ðàç, ò.å. ïðàâàÿ ÷àñòü ðàâíà y .QiÅñëè æå f (x) = h(x) + 1, òî j=0 g(x, j) > 0 äëÿ âñåõ 0 6 i 6 h(x). Ñëåäîâàòåëüíî,â ïðàâîé ÷àñòè òîæäåñòâà (∗) åäèíèöà ñóììèðóåòñÿ h(x) + 1 ðàç, ò.å. ïðàâàÿ ÷àñòüòîæå ðàâíà h(x) + 1.Òàêèì îáðàçîì, ïðèìèòèâíàÿ ðåêóðñèâíîñòü ôóíêöèè f ñëåäóåò èç ëåìì 18, 19 èòîæäåñòâà (∗).Ðàñïðîñòðàíèì ïîíÿòèå ðåêóðñèâíîñòè íà êëàññ âñåõ îòíîøåíèé, çàäàííûõ íà ω .Äëÿ ýòîãî äîñòàòî÷íî ñâÿçàòü ñ êàæäûì îòíîøåíèåì íåêîòîðóþ ÷àñòè÷íóþ ôóíêöèþ, êîòîðàÿ îäíîçíà÷íî åãî çàäà¼ò, è íàçâàòü îòíîøåíèå ðåêóðñèâíûì, åñëè òàêîâîéÿâëÿåòñÿ äàííàÿ ôóíêöèÿ.Îïðåäåëåíèå.ðåêóðñèâíûì (ïðèìèòèâ-Îòíîøåíèå (ïðåäèêàò) R ⊆ ω n íàçûâàåòñÿ, åñëè åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ(1, åñëè hx1 , .
. . , xn i ∈ R,XR (x1 , . . . , xn ) =0, åñëè hx1 , . . . , xn i ∈/Ríî ðåêóðñèâíûì)ÿâëÿåòñÿ ðåêóðñèâíîé (ïðèìèòèâíî ðåêóðñèâíîé).Íàïîìíèì, ÷òî âìåñòî hx1 , . . . , xn i ∈ R èíîãäà ïèøóò R(x1 , . . . , xn ) è ãîâîðÿò, ÷òîïðåäèêàò R èñòèííåí íà ýëåìåíòàõ x1 , . . . , xn . Åñëè æå hx1 , . . . , xn i ∈/ R, òî ïèøóò¬R(x1 , .
. . , xn ) è ãîâîðÿò, ÷òî ïðåäèêàò R ëîæåí íà ýëåìåíòàõ x1 , . . . , xn .Îïðåäåëåíèå.øåíèé:Äëÿ P, Q ⊆ ω n ââåä¼ì ñëåäóþùèå îáîçíà÷åíèÿ äëÿ n-ìåñòíûõ îòíî-P & Q = {x ∈ ω n | P (x) èñòèííî, è Q(x) èñòèííî},P ∨ Q = {x ∈ ω n | P (x) èñòèííî, èëè Q(x) èñòèííî},P → Q = {x ∈ ω n | åñëè P (x) èñòèííî, òî Q(x) èñòèííî},¬P = {x ∈ ω n | P (x) ëîæíî}.Êðîìå ýòîãî, äëÿ R ⊆ ω n+1 ââåä¼ì ñëåäóþùèå îáîçíà÷åíèÿ äëÿ (n + 1)-ìåñòíûõîòíîøåíèé:∃i 6 y R(x, i) = {hx, yi ∈ ω n+1∀i 6 y R(x, i) = {hx, yi ∈ ω n+1∃i < y R(x, i) = {hx, yi ∈ ω n+1∀i < y R(x, i) = {hx, yi ∈ ω n+1||||ñóùåñòâóåò i 6 y òàêîé, ÷òî R(x, i) èñòèííî},äëÿ âñåõ i 6 y îòíîøåíèå R(x, i) èñòèííî},ñóùåñòâóåò i < y òàêîé, ÷òî R(x, i) èñòèííî},äëÿ âñåõ i < y îòíîøåíèå R(x, i) èñòèííî}.Ñ òåîðåòèêî-ìíîæåñòâåííîé òî÷êè çðåíèÿ îòíîøåíèå P &Q ñîâïàäàåò ñïåðåñå÷åíèåì P ∩ Q, îòíîøåíèå P ∨ Q ñîâïàäàåò ñ îáúåäèíåíèåì P ∪ Q, à îòíîøåíèå¬P ñîâïàäàåò ñ äîïîëíåíèåì ω n \ P . Êðîìå ýòîãî, èìååò ìåñòî òîæäåñòâî P → Q =¬P ∨ Q.Çàìå÷àíèå.Åñëè îòíîøåíèÿ P (x) è Q(x) ðåêóðñèâíû (ïðèìèòèâíî ðåêóðñèâíû), òî îòíîøåíèÿ P (x)&Q(x), P (x) ∨ Q(x), ¬P (x), P (x) → Q(x) òîæå ðåêóðñèâíû (ïðèìèòèâíî ðåêóðñèâíû).Ïðåäëîæåíèå 21.48Ãëàâà III.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
