С.С. Марченков - Избранные главы дискретной математики (1124120), страница 24
Текст из файла (страница 24)
Ñíà÷àëà îïðåäåëèì ïðèìèòèâíî ðåêóðñèâíóþ ôóíêöèþ, êîäèðóþùóþ ïàðû.  êà÷åñòâå112òàêîé ôóíêöèè âîçüìåì ôóíêöèþc(x, y) = (x + y)2 + x.Íåñëîæíî óáåäèòüñÿ, ÷òî ôóíêöèÿ c èíúåêòèâíà. Âìåñòå ñ òåì ôóíêöèÿc ïðèíèìàåò äàëåêî íå âñå çíà÷åíèÿ èç N . Èìåííî, ïðè ëþáûõ x, y â ååîáëàñòü çíà÷åíèé íå âõîäÿò ÷èñëà(x + y)2 + x + 1, . . .
, (x + y)2 + 2x + 2y.Òåì íå ìåíåå ïî êîäó v = c(x, y) ïàðû (x, y) äîâîëüíî ïðîñòî âû÷èñëèòü ýëåìåíòû x è y . Ýòî äîñòèãàåòñÿ ñ ïîìîùüþ ïðèìèòèâíî ðåêóðñèâíûõ ôóíêöèé l(v) è r(v):√l(v) = v −· [ v]2 ,√r(v) = [ v] −· l(v).Êîäèðîâàíèå òðîåê ìîæíî îñóùåñòâèòü ñ ïîìîùüþ ôóíêöèèc3 (x, y, z) = c(c(x, y), z).¾Îáðàòíûìè¿ ôóíêöèÿìè, äîñòàâëÿþùèìè ïî êîäó v = c3 (x, y, z) êîìïîíåíòû x, y, z , áóäóò ñóïåðïîçèöèè ôóíêöèé l è r: ñîîòâåòñòâåííî l(l(v)),r(l(v)) è r(v).Âîîáùå, ïðè ëþáîì n > 3 êîäèðîâàíèå n-îê ìîæíî âûïîëíèòü ñ ïîìîùüþ ôóíêöèè cn (x1 , . . . , xn ), ãäåc2 (x1 , x2 ) = c(x1 , x2 ), cn+1 (x1 , .
. . , xn+1 ) = c(cn (x1 , . . . , xn ), xn+1 ).Åñëè v = cn (x1 , . . . , xn ), òîx1 = l(. . . l(v) . . .), x2 = r(l(. . . l(v) . . .)), . . . , xn−1 = r(l(v)), xn = r(v).| {z }| {z }n−1n−2Äëÿ êîäèðîâàíèÿ ïîñëåäîâàòåëüíîñòè (4.24) îäíèì ÷èñëîì d òàêæåìîæíî èñïîëüçîâàòü ïîäõîäÿùóþ ôóíêöèþ cn .
×òîáû ïðè äåêîäèðîâàíèè èçáåæàòü ìíîãîêðàòíûõ ñóïåðïîçèöèé ôóíêöèè l, îïðåäåëèì ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè l0 è l1 :l0 (v, 0) = v,l0 (v, i + 1) = l(l0 (v, i)),l1 (v, i) = r(l0 (v, i)).Åñëè òåïåðü v = cn+1 (an , . . . , a0 ), òî ïðè ëþáîì i < n áóäåì èìåòül1 (v, i) = ai .113ÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî ðåçóëüòàò ïðèìåíåíèÿ îïåðàöèè ìèíèìèçàöèè êâñþäó îïðåäåëåííîé ôóíêöèè åñòü ôóíêöèÿ, îïðåäåëåííàÿ õîòÿ áû âîäíîé òî÷êå.26.
Ïðèìåíèòü îïåðàöèþ ìèíèìèçàöèè ê ôóíêöèÿì x + y, x · y, x − y(çíà÷åíèå ýòîé ôóíêöèè íå îïðåäåëåíî, åñëè x < y ) è x/y (çíà÷åíèå ýòîéôóíêöèè ñ÷èòàåì íåîïðåäåëåííûì, åñëè ëèáî y = 0, ëèáî y 6= 0 è x íåÿâëÿåòñÿ êðàòíûì y ).27. Ïîäîáðàòü òàêèå ôóíêöèè g1 (x, y), g2 (x, y), ÷òîáû ïðèìåíåíèå êíèì îïåðàöèè ìèíèìèçàöèè äàâàëî ôóíêöèè x + y è x · y .28. Ïóñòü a1 , .
. . , as ðàçëè÷íûå ÷èñëà èç N è25.f (x) =1,åñëè x ∈ {a1 , . . . , as },íå îïðåäåëåíî â ïðîòèâíîì ñëó÷àå.Äîêàçàòü, ÷òî ôóíêöèÿ f (x) ÷àñòè÷íî ðåêóðñèâíà.29. Äîêàçàòü ÷àñòè÷íóþ ðåêóðñèâíîñòü ôóíêöèè g(x), åñëèg(x) =0,åñëè ñóùåñòâóåò òàêîå i, ÷òî l1 (x, i) = 1,íå îïðåäåëåíî â ïðîòèâíîì ñëó÷àå.Äîâåñòè äî êîíöà äîêàçàòåëüñòâî ÷àñòè÷íîé ðåêóðñèâíîñòè ôóíêöèè F (x, y).31. Ðàçðàáîòàòü òàêóþ ïðèìèòèâíî ðåêóðñèâíóþ íóìåðàöèþ ïàð, ÷òîáû êàæäîå ÷èñëî èç N áûëî íîìåðîì ðîâíî îäíîé ïàðû.30. 10. ×àñòè÷íàÿ ðåêóðñèâíîñòü âû÷èñëèìûõ ôóíêöèé.Ôîðìóëà Êëèíè 4 ìû äîêàçàëè, ÷òî âñÿêàÿ ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà íà ìàøèíå Òüþðèíãà.  ýòîì ïàðàãðàôå ìû óñòàíîâèì, ÷òîFâû÷ ⊆ F÷ð .Íà÷íåì ñ òîãî, ÷òî îïðåäåëèì ïðèìèòèâíî ðåêóðñèâíóþ ôóíêöèþ θn ,êîòîðàÿ ïîçâîëÿåò íóìåðîâàòü îñíîâíîé êîä n-êè ÷èñåë íà ëåíòå ìàøèíû Òüþðèíãà.
Èòàê, ïóñòü θn (x1 , . . . , xn ) åñòü ÷èñëî, äâîè÷íàÿ çàïèñüêîòîðîãî ïðåäñòàâëÿåò ñîáîé îñíîâíîé êîä íàáîðà (x1 , . . . , xn ) (êðàéíèéëåâûé è êðàéíèé ïðàâûé ñèìâîëû ýòîé çàïèñè ñóòü 1). Äëÿ ôóíêöèè θ1èìååì ñëåäóþùóþ ïðèìèòèâíóþ ðåêóðñèþ:θ1 (0) = 1,θ1 (x + 1) = 2θ1 (x) + 1.114Ôóíêöèÿ θn îïðåäåëÿåòñÿ ÷åðåç ôóíêöèþ θn−1 ñîãëàñíî ñëåäóþùåé ïðèìèòèâíîé ðåêóðñèè:θn (x1 , . . .
, xn−1 , 0) = 4θn−1 (x1 , . . . , xn−1 ) + 1,θn (x1 , . . . , xn−1 , xn + 1) = 2θn (x1 , . . . , xn ) + 1.Äëÿ ëþáîé âû÷èñëèìîé (íà ìàøèíåÒüþðèíãà) ôóíêöèè f (x1, . . . , xn) íàéäóòñÿ òàêèå ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè G(x1, . . . , xn, y) è Hf (x1, . . . , xn, y), ÷òî èìååò ìåñòîïðåäñòàâëåíèåÒåîðåìà 4.6(ôîðìóëà Êëèíè)f (x1 , . . . , xn ) = G(x1 , . . . , xn , (µy)(Hf (x1 , . . . , xn , y) = 0)).Ïóñòü ìàøèíà Òüþðèíãà M ïðàâèëüíî âû÷èñëÿåòôóíêöèþ f . Áóäåì ïðåäïîëàãàòü, ÷òî ïðîãðàììà ìàøèíû M ïðåîáðàçîâàíà òàêèì îáðàçîì, ÷òî ïðè ïîïàäàíèè â çàêëþ÷èòåëüíîå ñîñòîÿíèåq0 ìàøèíà M îñòàåòñÿ â ýòîì ñîñòîÿíèè, íå ñäâèãàåò ãîëîâêó íà ëåíòå èíå ìåíÿåò ñèìâîëà, îáîçðåâàåìîãî ãîëîâêîé (ìû òàê óæå ïîñòóïàëè ïðèäîêàçàòåëüñòâå òåîðåìû Êóêà â 7).Ïîëîæèì x = (x1 , .
. . , xn ). Ðàññìîòðèì ïðîèçâîëüíûé ìîìåíò âðåìåíè t â âû÷èñëåíèè çíà÷åíèÿ f (x) íà ìàøèíå M. Ïóñòü ìàøèíà M â ýòîòìîìåíò íàõîäèòñÿ â ñîñòîÿíèè qi , ñëåâà îò ãîëîâêè ðàñïîëàãàåòñÿ ÷àñòüëåíòû Lt , ñïðàâà ÷àñòü Rt (ãîëîâêà íàõîäèòñÿ â ïåðâîé êëåòêå ÷àñòèRt ). Îáîçíà÷èì ÷åðåç l(x, t) ÷èñëî, äâîè÷íàÿ çàïèñü êîòîðîãî ïðåäñòàâëåíà â ÷àñòè Lt (åñëè â Lt íåò åäèíèö, òî ïîëàãàåì l(x, t) = 0).
Àíàëîãè÷íîåîáîçíà÷åíèå r(x, t) ââîäèì äëÿ ÷èñëà, ïðåäñòàâëåííîãî â ÷àñòè Rt , îäíàêî çäåñü ïî òåõíè÷åñêèì ïðè÷èíàì íàì óäîáíî ÷èòàòü äâîè÷íóþ çàïèñüñëåâà íàïðàâî (ìëàäøèé ðàçðÿä äâîè÷íîé çàïèñè ÷èñëà r(x, t) ðàñïîëîæåí â ñàìîé ëåâîé êëåòêå ÷àñòè Rt ). Ïîëîæèì òàêæå q(x, t) = i. ìîìåíò âðåìåíè t = 0 áóäåì èìåòüÄîêàçàòåëüñòâî.l(x, 0) = 0,r(x, 0) = θn (xn , . . . , x1 ),q(x, 0) = 1.Òðîéêó ÷èñåë l(x, t), r(x, t), q(x, t) çàïèøåì â âèäå îäíîãî ÷èñëàCode(x, t) = c3 (l(x, t), r(x, t), q(x, t)),êîòîðîå áóäåì ñ÷èòàòü êîäîì êîíôèãóðàöèè ìàøèíû M â ìîìåíò âðåìåíè t.Îáîçíà÷èì ÷åðåç ρ(x) ôóíêöèþ, êîòîðàÿ äëÿ ÷èñëà x âèäà 2y − 1, ãäåy > 0, ðàâíà y − 1. Òîãäà ôóíêöèþ f ìîæíî ïðåäñòàâèòü â âèäåf (x1 , .
. . , xn ) = ρ(r(l(Code(x, (µy)(r(Code(x, t)) = 0))))).115Èç ýòîé ôîðìóëû ñëåäóåò, ÷òî òåîðåìà áóäåò äîêàçàíà, åñëè ìû óñòàíîâèì ïðèìèòèâíóþ ðåêóðñèâíîñòü ôóíêöèé Code è ρ.· . Ôóíê êà÷åñòâå ôóíêöèè ρ(x) ìîæíî âçÿòü ôóíêöèþ [log2 (x+1)] −1öèþ Code îïðåäåëèì ïðèìèòèâíîé ðåêóðñèåé ïî t. ÈìååìCode(x, t) = c3 (0, θn (xn . . . , x1 ), 1).×òîáû âûðàçèòü çíà÷åíèå Code(x, t + 1) ÷åðåç çíà÷åíèå Code(x, t), îïðåäåëèì ñíà÷àëà âåëè÷èíû l(x, t), r(x, t) è q(x, t):l(x, t) = l(l(Code(x, t))), r(x, t) = r(l(Code(x, t))), q(x, t) = l(Code(x, t)).Çàòåì íàéäåì çíà÷åíèå ïåðâîãî ðàçðÿäà â äâîè÷íîì ïðåäñòàâëåíèè ÷èñëàr(x, t).
Ýòî áóäåòν(x, t) = rm(r(x, t), 2).Åñëèa = ν(x, t),i = q(x, t),òî íàõîäèì â ïðîãðàììå ìàøèíû M êîìàíäóaqi → bDqj ,ãäå D ∈ {L, R, S}. Äàëåå â ñîîòâåòñòâèè ñî çíà÷åíèÿìè b, D, j îïðåäåëÿåì çíà÷åíèÿ l(x, t+1), r(x, t+1) è q(x, t+1). Î÷åâèäíî, ÷òî q(x, t+1) = j .Åñëè D = S , òî l(x, t + 1) = l(x, t) èr(x, t + 1) = (r(x, t) −· ν(x, t)) + b.Ïóñòü D = L.
Òîãäàl(x, t + 1) =hl(x,t)2i,r(x, t + 1) = 2((r(x, t) −· ν(x, t)) + b) + rm(l(x, t), 2).Àíàëîãè÷íî, åñëè D = R, òîl(x, t + 1) = 2l(x, t) + b,ihr(x,t)r(x, t + 1) =.2Òàêèì îáðàçîì, âåëè÷èíó Code(x, t+1) ìîæíî îïðåäåëèòü ïî ôîðìóëåCode(x, t + 1) =Psg|a − ν(x, t)| · sg|i − l(Code(x, t))|··c3 (l(x, t+1), r(x, t+1), q(x, t+1)),116ãäå (êîíå÷íàÿ) ñóììà ðàñïðîñòðàíÿåòñÿ ïî âñåì íàáîðàì (a, i), à âåëè÷èíû l(x, t + 1), r(x, t + 1) è q(x, t + 1) îïðåäåëÿþòñÿ, êàê óêàçàíî âûøå.Òåîðåìà äîêàçàíà.Èç òåîðåì 4.1 è 4.6 âûòåêàåò âàæíîå ñëåäñòâèå.Òåîðåìà 4.7.Êëàññû Fâû÷ è F÷ð ñîâïàäàþò.ÓÏÐÀÆÍÅÍÈßÈñïîëüçóÿ èäåþ äîêàçàòåëüñòâà òåîðåìû 10.6, ïîêàçàòü, ÷òî õàðàêòåðèñòè÷åñêèå ôóíêöèè (àðèôìåòè÷åñêèõ) îòíîøåíèé èç êëàññà Pÿâëÿþòñÿ ïðèìèòèâíî ðåêóðñèâíûìè.
Ïîëó÷èòü àíàëîãè÷íûé ðåçóëüòàòäëÿ îòíîøåíèé êëàññà NP.33. Ñ èñïîëüçîâàíèåì òåîðåìû 10.6 äîêàçàòü, ÷òî ëþáîå íåïóñòîå ìíîæåñòâî ÷èñåë, ïåðå÷èñëèìîå (âîçìîæíî, ñ ïîâòîðåíèÿìè) ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèåé, ïåðå÷èñëèìî òàêæå ïîäõîäÿùåé ïðèìèòèâíî ðåêóðñèâíîé ôóíêöèåé.32.Îòâåòû, ðåøåíèÿ, óêàçàíèÿÃëàâà 1.Pnn−ii n k. Èñïîëüçóåòñÿ ïðèíöèï âêëþ÷åíèÿ-èñêÎòâåò:i=0 (−1) i knëþ÷åíèÿ. Ïåðâîå ñëàãàåìîå ñóììû (ïîëàãàåì (−1)0 = 1) åñòü k k ÷èñëîn−1(n)âñåõ ôóíêöèé â Pk .
Èç íåãî âû÷èòàåòñÿ n ÷èñåë âèäà k k , êàæäîå èç(n)íèõ åñòü êîëè÷åñòâî ôóíêöèé èç Pk , íå çàâèñÿùèõ ñóùåñòâåííî îò ôèêñèðîâàííîé ïåðåìåííîé.Ïîñêîëüêó ýòè ìíîæåñòâà ïåðåñåêàþòñÿ, äàëåån−2íåîáõîäèìî äîáàâèòü n2 ñëàãàåìûõ âèäà k k , êîòîðûå ¾îòâå÷àþò¿ çàìíîæåñòâà ôóíêöèé, íå çàâèñÿùèõ ñóùåñòâåííî îò ôèêñèðîâàííûõ äâóõïåðåìåííûõ, è ò.ä.2. Èìååì k−1 = J1 (1), 0 = J1 (k−1).
Ôóíêöèÿ f1 (x) = max(1, x, J1 (x),. . . , Jk−2 (x)) ðàâíà 1 ïðè x = 0 è ðàâíà k − 1 ïðè x 6= 0. Ïîýòîìó J0 (x) =J1 (f1 (x)). Àíàëîãè÷íî îïðåäåëÿåì f2 (x) = max(J0 (x), . . . , Jk−2 (x)) è ïîëó÷àåì Jk−1 (x) = J0 (f2 (x)).···3. Èìååì 0 = x −x,min(x, y) = x −(x−y). Èç êîíñòàíòû 0 ñ ïîìîùüþ·ôóíêöèè x̄ ïîëó÷àåì îñòàëüíûå êîíñòàíòû. Äàëåå, ∼ x = (k − 1) −x, max(x, y) =∼ min(∼ x, ∼ y). Ôóíêöèÿ f (x) = 1 −· (1 −· x) ðàâíà 0 ïðèx = 0 è ðàâíà 1 ïðè x 6= 0. Ïîýòîìó ôóíêöèþ J0 (x) ìîæíî ïîëó÷èòü· ) k − 1 ðàç èçïîñëåäîâàòåëüíûì âû÷èòàíèåì (ïîñðåäñòâîì ôóíêöèè −êîíñòàíòû k − 1 ôóíêöèè f (x). Òåïåðü ïðè i 6= 0 ïîëó÷àåì Ji (x) =J0 (x + k − i).1.117Èìååì 0 = min(x, x + 1, .
. . , x + k − 1). Ñ ïîìîùüþ ôóíêöèè x̄ èçêîíñòàíòû 0 ïîëó÷àåì îñòàëüíûå êîíñòàíòû. Ôóíêöèÿ f0 (x) = min(x +1, . . . , x + k − 1) + k − 1 ðàâíà 0 ïðè x = 0 è ðàâíà k − 1 ïðè x 6= 0.Ïðè 1 6 i 6 k − 1 îáðàçóåì ôóíêöèè fi (x) = f0 (x + k − i), îáëàäàþùèå àíàëîãè÷íûìè ñâîéñòâàìè. Ïîýòîìó ïðè ëþáîì l ∈ Ek áóäåì èìåòüJl (x) = mini6=l (fi (x)). Ïðè l 6= 0 ôóíêöèÿ fi,l (x) = min(l, fi (x)) ðàâíà 0 ïðè x = i è ðàâíà l ïðè x 6= i, à ôóíêöèÿ gi,l,s (x) = fi,l (x) + s ñîîòâåòñòâåííî s è l + s (mod k). Âûáèðàÿ l = k − 1 − s, ïîëó÷àåì ôóíêöèþ hi,s (x), êîòîðàÿ ðàâíà s ïðè x = i è ðàâíà k − 1 ïðèx 6= i. Òåïåðü èìååì ∼ x = min(h0,k−1 (x), h1,k−2 (x), . . .
, hk−1,0 (x)). Íàêîíåö, max(x, y) =∼ min(∼ x, ∼ y).5. Äàííóþ ñèñòåìó ñâåäåì ê ñèñòåìå {j0 (x), x+y}. Çàìåòèì, ÷òî ñóììàk−1 ñëàãàåìûõ Ji (x) äàåò ôóíêöèþ ji (x). Èç ôóíêöèé 1 è x+y ïîëó÷àåìôóíêöèþ x + i. Ïðè i 6= 0 èìååì j0 (x) = ji (x + i).26. Èìååì (k − 1) = 1. Ôóíêöèÿ fi,s (x) = s · (k − 1) · Ji (x) ðàâíà sïðè x = i è ðàâíà 0 ïðè x 6= i. Èç ôóíêöèé fi,s ñ ïîìîùüþ ôóíêöèè maxìîæíî ¾ñîáðàòü¿ ëþáóþ îäíîìåñòíóþ ôóíêöèþ, â ÷àñòíîñòè, ôóíêöèþ∼ x.7.
Ïîêàæåì ñíà÷àëà, êàê ìîæíî ïîëó÷èòü ëþáóþ ôóíêöèþ f (x1 , . . . ,xn ) èç Pk , êîòîðàÿ ïðèíèìàåò ëèøü çíà÷åíèÿ 0,1. Ôóíêöèÿ ji1 (x1 ) · . . . ·jin (xn ) (ïîëó÷àåìàÿ ñóïåðïîçèöèÿìè ôóíêöèé çàäàííîé ñèñòåìû) ïðèíèìàåò çíà÷åíèå 1 íà íàáîðå (i1 , . . . , in ) è çíà÷åíèå 0 íà îñòàëüíûõ íàáîðàõ. Ôóíêöèÿ d(x1 , x2 ) = j0 (j0 (x1 ) · j0 (x2 )) íà ìíîæåñòâå E22 ñîâïàäàåò ñ äèçúþíêöèåé. Ïîýòîìó ôóíêöèþ f ìîæíî ¾ñîáðàòü¿ èç ôóíêöèéâèäà ji1 (x1 ) · . . . · jin (xn ) ñ ïîìîùüþ ôóíêöèè d. Ïðåäïîëîæèì äàëåå,÷òî ôóíêöèÿ f ïðèíèìàåò ëèøü çíà÷åíèÿ èç E3 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
