1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 17
Текст из файла (страница 17)
Åñëè S = ∅, òî óòâåðæäåíèå ñëåäóåò èç îïðåäåëåíèÿ. Ïóñòüòåïåðü S 6= ∅. Äëÿ íåêîòîðûõ e è âû÷èñëèìîãî îòíîøåíèÿ ââèäó òåîðåìû î íîðìàëüíîé ôîðìå Êëèíè, äëÿ íåêîòîðîãî e ∈ N è íåêîòîðîãîâû÷èñëèìîãî îòíîøåíèÿ T (e, x, t) è âûïîëíåíî f (x) ' U (µt (T (e, x, t))).Ïðè ýòîì, ïîñêîëüêó â òåîðåìå î íîðìàëüíîé ôîðìå t êîä âû÷èñëåíèÿíà ìàøèíå ñ íîìåðîì e ñî âõîäíûìè äàííûìè x, äëÿ ëþáîãî x îòíîøåíèåT (e, x, t) âûïîëíåíî äëÿ íå áîëåå, ÷åì îäíîãî çíà÷åíèÿ t. Çàôèêñèðóåìíåêîòîðûé ýëåìåíò a0 ∈ S è ïîëîæèì½U ((t)1 ), åñëè T (e, (t)0 , (t)1 )g(t) =a0 ,â ïðîòèâíîì ñëó÷àå.Ëåãêî ïðîâåðèòü, ÷òî ôóíêöèÿ g ãîäèòñÿ.
¤4.4. Ïåðå÷èñëèìûå ìíîæåñòâà95Ïðèìåð. Ìíîæåñòâî S = {hx, y, zi | æx (y) = z} âû÷èñëèìî ïåðå÷èñëè-ìî.  ñàìîì äåëå,v ∈ S ⇔ seq (v) & lh (v) = 2 & ∃t (T1 ((v)0 , (v)1 , t) & U (t) = (v)2 ),îòêóäàv ∈ S ⇔ ∃t (seq (v) & lh (v) = 2 & (T1 ((v)0 , (v)1 , t) & U (t) = (v)2 )),è óòâåðæäåíèå ñëåäóåò èç òåîðåìû.Íà îñíîâàíèè äàííîé òåîðåìû ìîæíî îïðåäåëèòü åñòåñòâåííóþ òàêíàçûâàåìóþ íóìåðàöèþ Êëèíè âñåõ â.ï. ìíîæåñòâ: Wn = dom (æn ), n ∈N. (Ìîæíî áûëî áû òàêæå îïðåäåëèòü íóìåðàöèþ è ÷åðåç îáëàñòè çíà÷åíèé ôóíêöèé: πn = range (æn ), n ∈ N. Ýòà íóìåðàöèÿ îêàçûâàåòñÿ âî÷åíü ñèëüíîì ñìûñëå ýêâèâàëåíòíà íóìåðàöèè Wn , äåòàëè ñì.
â [2].)Íóìåðàöèÿ Êëèíè îáëàäàåò î÷åíü âàæíûì ñâîéñòâîì, ñâÿçàííûì ñïîíÿòèåì âû÷èñëèìîé íóìåðàöèè ñåìåéñòâà ìíîæåñòâ íàòóðàëüíûõ ÷èñåë.Îïðåäåëåíèå 4.4.4 Íóìåðàöèþ ν ïðîèçâîëüíîãî ñåìåéñòâà ìíîæåñòâíàòóðàëüíûõ ÷èñåë íàçîâåì âû÷èñëèìîé, åñëè ìíîæåñòâî {hx, yi | x ∈ν(y)} âû÷èñëèìî ïåðå÷èñëèìî.
Áóäåì ãîâîðèòü, ÷òî ïîñëåäîâàòåëüíîñòüìíîæåñòâ (An )n∈N âû÷èñëèìà, åñëè âû÷èñëèìà íóìåðàöèÿ ν(n) = An .Çàìåòèì,÷òî åñëè îòíîøåíèå x ∈ ν(y) çàïèñûâàåòñÿ â ôîðìå ∃t R(x, y, t),ãäå R ðåêóðñèâíîå îòíîøåíèå. Òîãäà íóìåðàöèÿ ν âû÷èñëèìà. Äåéñòâèòåëüíî,r ∈ {hx, yi | x ∈ ν(y)} ⇔ seq (r) & lh (r) = 2 & ∃t R((r)0 , (r)1 , t),îòêóäà è ñëåäóåò ýòî çàìå÷àíèå.Óïðàæíåíèÿ.1. Äîêàçàòü, ÷òî ëþáîé ýëåìåíò ν(n) âû÷èñëèìîé íóìåðàöèè ìíîæåñòâ íàòóðàëüíûõ ÷èñåë ÿâëÿåòñÿ â.ï. ìíîæåñòâîì.2. Äîêàçàòü, ÷òî íóìåðàöèÿ Êëèíè â.ï.
ìíîæåñòâ âû÷èñëèìà.Óêàçàíèå. Ýòî ñëåäóåò èç ëåãêî ïðîâåðÿåìîé ýêâèâàëåíòíîñòè:x ∈ Wy ⇔ ∃t T1 (y, x, t).96Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÑëåäóþùåå óòâåðæäåíèå îçíà÷àåò, ÷òî íóìåðàöèÿ Êëèíè ÿâëÿåòñÿíàèáîëüøåé âû÷èñëèìîé íóìåðàöèåé ñðåäè âñåõ âû÷èñëèìûõ íóìåðàöèé.Ïðåäëîæåíèå 4.4.5 Ëþáàÿ âû÷èñëèìàÿ íóìåðàöèÿ ñåìåéñòâà ìíîæåñòâíàòóðàëüíûõ ÷èñåë ñâîäèòñÿ ê íóìåðàöèè Êëèíè.Äîêàçàòåëüñòâî. Ïóñòü ν âû÷èñëèìàÿ íóìåðàöèÿ ñåìåéñòâà ìíîæåñòâ íàòóðàëüíûõ ÷èñåë. Ýòî îçíà÷àåò, ÷òî ìíîæåñòâî S = {hx, yi | x ∈ν(y)} âû÷èñëèìî ïåðå÷èñëèìî.
Äàëåå çàäàäèì ôóíêöèþ g(t, x) ñëåäóþùèìè óñëîâèÿìè½0,åñëè t ∈ ν(x)g(x, t) =íå îïðåäåëåíà â ïðîòèâíîì ñëó÷àå.Ýòà ôóíêöèÿ ÿâëÿåòñÿ ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèåé.  ýòîì ìîæíîóáåäèòüñÿ ïî òåçèñó ×åð÷à. Ìîæíî ïðåäëîæèòü ñëåäóþùèé èíòóèòèâíûé àëãîðèòì äëÿ âû÷èñëåíèÿ g(x, t).Çàïóñòèì ïðîöåäóðó ïåðå÷èñëåíèÿ ìíîæåñòâà S è áóäåìæäàòü ìîìåíòà, êîãäà â ïåðå÷èñëåíèè ýòîãî ìíîæåñòâàïîÿâèòñÿ ýëåìåíò ht, xi. Êîãäà ýòî ïðîèçîéäåò, âûäàäèì 0â êà÷åñòâå îòâåòà.Ïîñêîëüêó íóìåðàöèÿ æ ïðèåìëåìà, íàéäåòñÿ âû÷èñëèìàÿ âñþäó îïðåäåëåííàÿ ôóíêöèÿ h òàêàÿ, ÷òî g(x, t) 'æh(x) (t).
Èìååì:t ∈ ν(x) ⇔ g(x, t) ↓⇔ æh(x) (t) ↓⇔ t ∈ Wh(x) .Îòñþäà ν(x) = Wh(x) , ò.å., ν 6 W . ¤Åùå îäíèì ñâîéñòâîì íóìåðàöèè Êëèíè ÿâëÿåòñÿ äîêàçûâàåìûé íèæå ôàêò, ÷òî ïî çàäàííûì íîìåðàì ìíîæåñòâ â ýòîé íóìåðàöèè ìîæíîýôôåêòèâíî ïåðåõîäèòü ê íîìåðàì îáúåäèíåíèé è ïåðåñå÷åíèé. Èç ýòîãî, â ÷àñòíîñòè, ñëåäóåò çàìêíóòîñòü êëàññà â.ï. ìíîæåñòâ îòíîñèòåëüíîïåðåñå÷åíèÿ è îáúåäèíåíèÿ.Ïðåäëîæåíèå 4.4.6 Ñóùåñòâóþò âû÷èñëèìûå âñþäó îïðåäåëåííûå ôóíêöèè u(x, y) è v(x, y) òàêèå, ÷òî äëÿ ëþáûõ x, y ∈ N âûïîëíåíî Wu(x,y) =Wx ∪ Wy è Wv(x,y) = Wx ∩ Wy .Äîêàçàòåëüñòâî.
Íóìåðàöèÿ ν(z) = W(z)0 ∪ W(z)1 âû÷èñëèìà, òàê êàên ∈ ν(z) ⇔ n ∈ W(z)0 ∨ n ∈ W(z)1 ⇔4.4. Ïåðå÷èñëèìûå ìíîæåñòâà97⇔ ∃t T ((z)0 , n, t) ∨ ∃t T ((z)1 , n, t) ⇔⇔ ∃t (T ((z)0 , n, t) ∨ T ((z)1 , n, t)).Òåïåðü ν(z) = Wh(z) , äëÿ ïîäõîäÿùåé âñþäó îïðåäåëåííîé âû÷èñëèìîéôóíêöèè h. ÄàëååWx ∪ Wy = W(hx,yi)0 ∪ W(hx,yi)1 = ν(hx, yi) = Wh(hx,yi) .Äîêàçàòåëüñòâî äëÿ ïåðåñå÷åíèÿ ïðîâîäèòñÿ àíàëîãè÷íî. Äîñòàòî÷íîòîëüêî çàìåòèòü, ÷òî íóìåðàöèÿ ν(z) = W(z)0 ∩W(z)1 âû÷èñëèìà, òàê êàên ∈ ν(z) ⇔ n ∈ W(z)0 & n ∈ W(z)1 ⇔⇔ ∃t T ((z)0 , n, t) & ∃t T ((z)1 , n, t) ⇔⇔ ∃t∃t0 (T ((z)0 , n, (t)0 ) & T ((z)1 , n, (t0 )1 )).Äàëåå äîêàçàòåëüñòâî àíàëîãè÷íî.
¤Âîçíèêàåò åñòåñòâåííûé âîïðîñ: çàìêíóò ëè êëàññ â.ï. ìíîæåñòâ îòíîñèòåëüíî äîïîëíåíèÿ? Âîîáùå ãîâîðÿ, íåò. Íàïðèìåð, ðàññìîòðåííîåíà ñòð. 83 íåâû÷èñëèìîå ìíîæåñòâî K ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì, òàê êàê x ∈ K ⇔ {x}(x) ↓⇔ ∃t T1 (x, x, t).Åñëè áû åãî äîïîëíåíèå áûëî âû÷èñëèìî ïåðå÷èñëèìûì, òî ñàìîìíîæåñòâî áûëî áû âû÷èñëèìûì, ÷òî âûòåêàåò èç ñëåäóþùåé òåîðåìû:Òåîðåìà 4.4.7 (Òåîðåìà Ïîñòà) Ïðîèçâîëüíîå ìíîæåñòâî íàòóðàëü-íûõ ÷èñåë âû÷èñëèìî òîãäà è òîëüêî òîãäà, êîãäà îíî âû÷èñëèìî ïåðå÷èñëèìî è åãî äîïîëíåíèå âû÷èñëèìî ïåðå÷èñëèìî.Äîêàçàòåëüñòâî.
Âû÷èñëèìàÿ ïåðå÷èñëèìîñòü ëþáîãî âû÷èñëèìîãîìíîæåñòâà à òàêæå åãî äîïîëíåíèÿ ñëåäóåò èç ïðåäëîæåíèÿ 4.4.2.Ïðåäïîëîæèì, ÷òî ìíîæåñòâà A ⊆ N è N \ A âû÷èñëèìî ïåðå÷èñëèìû. Íåôîðìàëüíî ìîæíî îïèñàòü àëãîðèòì ðàñïîçíàâàíèÿ ýëåìåíòîâìíîæåñòâà A ñëåäóþùèì îáðàçîì:îäíîâðåìåííî ïåðå÷èñëÿåì ìíîæåñòâî A è åãî äîïîëíåíèå;÷èñëî x, êîòîðîå íàñ èíòåðåñóåò, îáÿçàòåëüíî ïîÿâèòñÿ â îäíîì èç ýòèõ ïåðå÷èñëåíèé, ÷òî è äàñò íàì îòâåò íà âîïðîñ x ∈ A?.Áîëåå ôîðìàëüíîå äîêàçàòåëüñòâî âûãëÿäèò òàê. Ñëó÷àé, êîãäà õîòÿáû îäíî èç ýòèõ ìíîæåñòâ ïóñòî, òðèâèàëåí.
Ïîýòîìó ìîæíî ñ÷èòàòü,÷òî îáà îíè ÿâëÿþòñÿ îáëàñòÿìè çíà÷åíèé âû÷èñëèìûõ âñþäó îïðåäåëåííûõ ôóíêöèé: A = range (f ), N \ A = range (g). Îïðåäåëèì âñþäóîïðåäåëåííóþ âû÷èñëèìóþ ôóíêöèþ h(x) = µt(x = f (t) ∨ x = g(t)).Íåòðóäíî óáåäèòüñÿ, ÷òî x ∈ A ⇔ x = f (h(x)).98Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÎïðåäåëåíèå 4.4.8 Ãðàôèêîì ôóíêöèè f : Nk → N íàçûâàåòñÿ ìíîæåñòâî Γ(f ) = {hx1 , . . . , xk , yi | f (x1 , .
. . , xk ) = y}.Òåîðåìà 4.4.9 (Òåîðåìà î ãðàôèêå) Ïðîèçâîëüíàÿ ôóíêöèÿ f : Nk →N ÿâëÿåòñÿ ÷àñòè÷íîé âû÷èñëèìîé òîãäà è òîëüêî òîãäà, êîãäà å¼ ãðàôèê âû÷èñëèìî ïåðå÷èñëèìîå ìíîæåñòâî.Äîêàçàòåëüñòâî. Åñëè f ÷àñòè÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ, òî ïî òåîðåìå î íîðìàëüíîé ôîðìå äëÿ ïîäõîäÿùåãî e ∈ N âûïîëíåíîf (x1 , . . . , xk ) ' U (µt (Tk (e, x1 , . . .
, xk , t))).Èìååìhx1 , . . . , xk , yi ∈ Γ(f ) ⇔ f (x) = y⇔ ∃t[y = U (t) & Tk (e, x1 , . . . , xk , t) & ∀t0 < t¬Tk (e, x1 , . . . , xk , t0 )].Ïî òåîðåìå îá ýêâèâàëåíòíûõ îïðåäåëåíèÿõ â.ï. ìíîæåñòâ, ìíîæåñòâîΓ(f ) âû÷èñëèìî ïåðå÷èñëèìî.Ïóñòü òåïåðü ãðàôèê Γ(f ) ôóíêöèè f : Nk → N âû÷èñëèìî ïåðå÷èñëèì.
Åñëè Γ(f ) = ∅, òî f = ∅ è ïîýòîìó f ÷àñòè÷íàÿ âû÷èñëèìàÿôóíêöèÿ. Åñëè Γ(f ) 6= ∅, òî ñóùåñòâóåò âñþäó îïðåäåëåííàÿ âû÷èñëèìàÿ ôóíêöèÿ g òàêàÿ, ÷òî Γ(f ) = range (g). Ôóíêöèþ f òåïåðü ìîæíîîïðåäåëèòü òàê:f (x1 , . . . , xk ) = (µt((g(t))0 = x1 & . . .
& (g(t))k−1 = xk ))k .Îòñþäà ñëåäóåò, ÷òî f ÷àñòè÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ. ¤Ñëåäñòâèå 4.4.10 Ïóñòü A1 ,. . . ,Ak ïîïàðíî íåïåðåñåêàþùèåñÿ â.ï.ìíîæåñòâà è f1 (x),. . . ,fk (x) ïðîèçâîëüíûå ÷àñòè÷íûå âû÷èñëèìûåôóíêöèè. Òîãäà ôóíêöèÿ g , îïðåäåëåííàÿ, êàêf1 (x), f2 (x),...g(x) = fk (x),íåîïðåäåëåíî,åñëè x ∈ A1åñëè x ∈ A2åñëè x ∈ Ak ,â îñòàëüíûõ ñëó÷àÿõ,ÿâëÿåòñÿ ÷àñòè÷íîé ðåêóðñèâíîé ôóíêöèåé.4.4. Ïåðå÷èñëèìûå ìíîæåñòâà99Äîêàçàòåëüñòâî.
Èìååì:g(x) = y ⇔ (y = f1 (x) & x ∈ A1 ) ∨ . . . (y = fk (x) & x ∈ Ak ).Ïîñêîëüêó îòíîøåíèÿ {hx, yi | y = fk (x)} è x ∈ Ak ïåðå÷èñëèìû, ïîñëåäíþþ êîíúþíêöèþ ìîæíî ïðåäñòàâèòü â âèäå(∃t1 R1 (x, y, t1 ) & ∃t01 Q1 (x)) ∨ . . . (∃tk R1 (x, y, tk ) & ∃t0k Qk (x)),äëÿ ïîäõîäÿùèõ âû÷èñëèìûõ îòíîøåíèé Ri (x, y, ti ), Qi (x), i = 1, . . . , k .Îíà ëîãè÷åñêè ýêâèâàëåíòíà ñëåäóþùåìó:∃t1 ∃t01 .
. . ∃tk ∃t0k (R1 (x, y, t1 ) & Q1 (x)) ∨ . . . (R1 (x, y, tk ) & Qk (x)).Ýòî âëå÷åò âû÷èñëèìóþ ïåðå÷èñëèìîñòü ãðàôèêà ôóíêöèè g . Ïî òåîðåìå î ãðàôèêå, g ÷àñòè÷íî âû÷èñëèìàÿ ôóíêöèÿ. ¤100Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÃëàâà 5Ââåäåíèå â ñëîæíîñòüàëãîðèòìîâ5.1 Çà÷åì íóæíî èçó÷àòü ñëîæíîñòü àëãîðèòìîâ?Êàçàëîñü áû, íåçà÷åì. Íå÷åãî ëåíèòüñÿ, ñ÷èòàòü íàäî! Ñîâðåìåííûå êîìïüþòåðû îáëàäàþò êîëîññàëüíûì áûñòðîäåéñòâèåì, ïîçâîëÿþùèì èñïîëíÿòü êîëîññàëüíîå êîëè÷åñòâî îïåðàöèé çà ñåêóíäû. Íî íà ïðàêòèêå÷àñòî ñëó÷àåòñÿ, ÷òî ÷èñëî øàãîâ àëãîðèòìà, íà âõîä êîòîðîãî ïîäàþòñÿ äàííûå íåêîòîðîé äëèíû n, ñ ðîñòîì n ðàñòåò íàñòîëüêî áûñòðî, ÷òîýòîò àëãîðèòì ôàêòè÷åñêè ñòàíîâèòñÿ íåïðèãîäíûì äëÿ ñ÷åòà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
