1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 16
Текст из файла (страница 16)
. . , xn ) ÿâëÿåòñÿ âû÷èñëèìîé.Îïðåäåëåíèå.Ïóñòü S ïðîèçâîëüíîå ñåìåéñòâî îäíîìåñòíûõ÷.â.ô., òàêîå, ÷òîè íå ñîâïàäàåò ñ ñåìåéñòâîì âñåõ îäíîìåñòíûõ ÷.â.ô.Òîãäà ìíîæåñòâîâñåõ êëèíèåâñêèõ íîìåðîâ ôóíêöèé, ïðèíàäëåæàùèõ ñåìåéñòâó , íåâû÷èñëèìî.Äîêàçàòåëüñòâî. Äîïóñòèì, íàïðîòèâ, ìíîæåñòâî A = {x ∈ ω | ϕx ∈ S} âû÷èñëèìî,Òåîðåìà 46(òåîðåìà Ðàéñà).S 6= ∅ S{x ∈ ω | ϕx ∈ S}Sò. å.
âû÷èñëèìîé ÿâëÿåòñÿ åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ(1, åñëè x ∈ A,XA (x) =0, åñëè x ∈/ A.Òàê êàê S 6= ∅ è S 6= {f | f 1-ìåñòíàÿ ÷.â.ô.}, òî íàéäóòñÿ a, b ∈ ω òàêèå, ÷òîϕa ∈ S è ϕb ∈/ S . Îïðåäåëèì ôóíêöèþ(b, åñëè x ∈ A,f (x) =a, åñëè x ∈/ A.65 19. Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà ñèëó ïðåäëîæåíèÿ 24, ôóíêöèÿ f (x) âû÷èñëèìà. Ïî òåîðåìå î íåïîäâèæíîé òî÷êå ñóùåñòâóåò n ∈ ω òàêîå, ÷òî ϕf (n) = ϕn . Òîãäà èìååò ìåñòî ñëåäóþùàÿ öåïî÷êàýêâèâàëåíòíîñòåé (âòîðàÿ ýêâèâàëåíòíîñòü ñëåäóåò èç âûáîðà a è b, òðåòüÿ ýêâèâàëåíòíîñòü ñëåäóåò èç îïðåäåëåíèÿ ôóíêöèè f (x)):ϕn ∈ S ⇐⇒ ϕf (n) ∈ S ⇐⇒ f (n) = a ⇐⇒ n ∈/ A ⇐⇒ ϕn ∈/ S.Ïðîòèâîðå÷èå.
Ñëåäîâàòåëüíî, íàøå ïðåäïîëîæåíèå î âû÷èñëèìîñòè ìíîæåñòâà {x ∈ω | ϕx ∈ S} íåâåðíî.Ïóñòü f (x) ïðîèçâîëüíàÿ îäíîìåñòíàÿ ÷.â.ô. Ðàññìîòðèì îäíîýëåìåíòíîå ñåìåéñòâî ôóíêöèé S = {f }. Îíî óäîâëåòâîðÿåò óñëîâèÿì òåîðåìû Ðàéñà, ñëåäîâàòåëüíî, ìíîæåñòâî A = {e ∈ ω | ϕe = f } íå âû÷èñëèìî. Çàìåòèì, ÷òî ìíîæåñòâî A ýòî â òî÷íîñòè ìíîæåñòâî âñåõ êëèíèåâñêèõ íîìåðîâ ôóíêöèè f . Òàêèì îáðàçîì,èç òåîðåìû Ðàéñà ñëåäóåò, ÷òî.  ÷àñòíîñòè, ëþáàÿ ÷.â.ô.
èìååò áåñêîíå÷íî ìíîãî êëèíèåâñêèõíîìåðîâ (ïîñêîëüêó, î÷åâèäíî, ëþáîå êîíå÷íîå ìíîæåñòâî âû÷èñëèìî).Ïðèìåð.÷.â.ô. íå âû÷èñëèìî 19.ìíîæåñòâî âñåõ êëèíèåâñêèõ íîìåðîâ ôèêñèðîâàííîéÂû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà ýòîì ïàðàãðàôå ìû ââåä¼ì ïîíÿòèå âû÷èñëèìî ïåðå÷èñëèìîãî ìíîæåñòâà (ñîêðàùåííî â.ï. ìíîæåñòâà) è èçó÷èì íåêîòîðûå ñâîéñòâà òàêèõ ìíîæåñòâ.
Ñ èíòóèòèâíîé òî÷êè çðåíèÿ ìíîæåñòâî ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì, åñëè ñóùåñòâóåòàëãîðèòì ýôôåêòèâíîãî ïåðå÷èñëåíèÿ âñåõ åãî ýëåìåíòîâ. Ïðè ýòîì ìû äîïóñêàåì,÷òî ýòî ïåðå÷èñëåíèå ìîæåò èìåòü ïîâòîðåíèÿ è íå îáÿçàíî áûòü ïåðå÷èñëåíèåì âêàêîì-òî ñòðîãî îïðåäåë¼ííîì ïîðÿäêå.âû÷èñëèìî ïåðå÷èñ-Ïóñòü k > 1. Ìíîæåñòâî A ⊆ ω k íàçûâàåòñÿ, åñëè A = ∅ èëè A = {hf1 (x), . . . , fk (x)i | x ∈ ω} äëÿ íåêîòîðûõâû÷èñëèìûõ ôóíêöèé f1 (x), . . . , fk (x).Îïðåäåëåíèå.ëèìûì (â.ï.)Äðóãèìè ñëîâàìè, âû÷èñëèìûå ôóíêöèè f1 , . . .
, fk ïîêîîðäèíàòíî ïåðå÷èñëÿþòìíîæåñòâî A.  ñëó÷àå k = 1 îïðåäåëåíèå âûãëÿäèò ïðîùå: ìíîæåñòâî A ⊆ ω ÿâëÿåòñÿ â.ï. òîãäà è òîëüêî òîãäà, êîãäà A = ∅ èëè A = range(f ) äëÿ íåêîòîðîé âû÷èñëèìîé ôóíêöèè f (x). Ââåä¼ííîå îïðåäåëåíèå ÿâëÿåòñÿ ôîðìàëüíûì îïèñàíèåì èíòóèòèâíîãî ïîíÿòèÿ ïåðå÷èñëèìîñòè. Îäíàêî ñóùåñòâóåò íåñêîëüêî ýêâèâàëåíòíûõîïèñàíèé â.ï. ìíîæåñòâ, êàæäîå èç êîòîðûõ îêàçûâàåòñÿ ïîëåçíûì ïðè èçó÷åíèè òåõèëè èíûõ ñâîéñòâ â.ï. ìíîæåñòâ.Òåîðåìà 47(îá ýêâèâàëåíòíûõ îïðåäåëåíèÿõ â.ï. ìíîæåñòâ).Äëÿ ïðîèçâîëüíîãî ìíîæåñòâà A ⊆ ωk ñëåäóþùèå óñëîâèÿ ýêâèâàëåíòíû:1) A âû÷èñëèìî ïåðå÷èñëèìî.2) Ñóùåñòâóåò âû÷èñëèìîå îòíîøåíèå R ⊆ ωk+1 òàêîå, ÷òîhx1 , .
. . , xk i ∈ A ⇐⇒ ∃yR(x1 , . . . , xk , y).3) Ñóùåñòâóåò ÷.â.ô. f (x1, . . . , xk ) òàêàÿ, ÷òî A = dom(f ).66Ãëàâà IV. Òåîðèÿ âû÷èñëèìîñòèÄîêàçàòåëüñòâî. Äîêàæåì ñïðàâåäëèâîñòü èìïëèêàöèè (1) ⇒ (2). Åñëè A = ∅, òîâû÷èñëèìîå ìíîæåñòâî R = ∅ î÷åâèäíî óäîâëåòâîðÿåò óñëîâèþ (2). Åñëè æå A 6= ∅è A = {hf1 (x), . . . , fk (x)i | x ∈ ω}, ãäå f1 , . . . , fk âû÷èñëèìûå ôóíêöèè, òî èìååòìåñòî ýêâèâàëåíòíîñòühx1 , . . . , xk i ∈ A ⇐⇒ ∃y f1 (y) = x1 & . .
. & fk (y) = xk .Òîãäà ìíîæåñòâî R = {hx1 , . . . , xk , yi | f1 (y) = x1 & . . . & fk (y) = xk } ÿâëÿåòñÿ èñêîìûì (k+1)-ìåñòíûì âû÷èñëèìûì îòíîøåíèåì.Òåïåðü äîêàæåì èìïëèêàöèþ (2) ⇒ (3). Ïóñòü R ⊆ ω k+1 âû÷èñëèìîå îòíîøåíèåòàêîå, ÷òî A ÿâëÿåòñÿ åãî ïðîåêöèåé (ñì. ðèñóíîê), ò. å. èìååò ìåñòî ýêâèâàëåíòíîñòüx ∈ A ⇐⇒ ∃yR(x, y).y6HHR"&fA!%-xÎïðåäåëèì ÷àñòè÷íóþ k -ìåñòíóþ ôóíêöèþ f (x) = µy[R(x, y)]. Òàê êàê R âû÷èñëèìî, òî f (x) ÷.â.ô. Êðîìå ýòîãî, èìååò ìåñòîf (x) ↓ ⇐⇒ ∃yR(x, y) ⇐⇒ x ∈ A.Äðóãèìè ñëîâàìè, dom(f ) = A.Äîêàæåì èìïëèêàöèþ (3) ⇒ (1).
Åñëè A = ∅, òî äîêàçûâàòü íå÷åãî. Ïóñòü A 6= ∅.Ñëåäîâàòåëüíî, íàéä¼òñÿ êîðòåæ a = ha1 , . . . , ak i ∈ A. Ïî óñëîâèþ A = dom(f ), ãäå f ÷.â.ô. Òîãäà f âû÷èñëèìà íà íåêîòîðîé ìàøèíå Òüþðèíãà ñ êîäîì e è ïî òåîðåìåîá óíèâåðñàëüíîé ÷.ð.ô.f (x) = out(run(e, ink (x), µy[q(e, x, y) = 0])).Äëÿ êàæäîãî i ∈ {1, . . . , k} îïðåäåëèì 1-ìåñòíóþ âû÷èñëèìóþ ôóíêöèþ(ex(i, n), åñëè q(e, ex(1, n), . . .
, ex(k, n), ex(0, n)) = 0,fi (n) =ai ,åñëè q(e, ex(1, n), . . . , ex(k, n), ex(0, n)) 6= 0. ñèëó ïðåäëîæåíèÿ 24, ôóíêöèè f1 , . . . , fk âû÷èñëèìû.Ïîêàæåì, ÷òî íàáîð ôóíêöèé f1 , . . . , fk èñêîìûé, ò. å. A = {hf1 (x), . . . , fk (x)i |x ∈ ω}. Äëÿ ýòîãî äîêàæåì ñíà÷àëà âêëþ÷åíèå A ⊆ {hf1 (x), . . . , fk (x)i | x ∈ ω}.Ïóñòü x = hx1 , . . . , xk i ∈ A. Òîãäà f (x) = out(run(e, ink (x), µy[q(e, x, y) = 0])) îïðåäåëåíî. Ñëåäîâàòåëüíî, çíà÷åíèå µy[q(e, x, y) = 0] îïðåäåëåíî.
Ñëåäîâàòåëüíî, ñóùåñòâóåò y ∈ ω òàêîé, ÷òî q(e, x, y) = 0. Ïîëîæèì n = py0 · px1 1 · . . . · pxk k . Òîãäàq(e, ex(1, n), . . . , ex(k, n), ex(0, n)) = 0, è çíà÷èò fi (n) = ex(i, n) = xi äëÿ âñåõ i ∈{1, . . . , k}. Òàêèì îáðàçîì, x ∈ {hf1 (x), . . . , fk (x)i | x ∈ ω}.Äîêàæåì îáðàòíîå âêëþ÷åíèå {hf1 (x), . . .
, fk (x)i | x ∈ ω} ⊆ A. Ðàññìîòðèì ïðîèçâîëüíûé íàáîð hf1 (n), . . . , fk (n)i, ãäå n ∈ ω . Åñëè q(e, ex(1, n), . . . , ex(k, n), ex(0, n)) 6=0, òî hf1 (n), . . . , fk (n)i = a ∈ A è âñ¼ äîêàçàíî. Ïóñòü òåïåðü ñïðàâåäëèâî ðàâåíñòâî 19. Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà67q(e, ex(1, n), . . .
, ex(k, n), ex(0, n)) = 0. Òîãäà, â ñèëó ïðåäëîæåíèÿ 32, ìàøèíà ñ êîäîì e, íà÷àâ ðàáîòó íà âõîäíîì ìàøèííîì ñëîâå q1 01ex(1,n) 0 . . . 01ex(k,n) 0, è ïðîäåëàâex(0, n) øàãîâ, ïåðåõîäèò â ñîñòîÿíèå q0 . Òàê êàê äàííàÿ ìàøèíà âû÷èñëÿåò ôóíêöèþ f , çàêëþ÷àåì, ÷òî çíà÷åíèå f (ex(1, n), . . . , ex(k, n)) îïðåäåëåíî. Ñëåäîâàòåëüíî,êîðòåæ hf1 (n), . . . , fk (n)i = hex(1, n), . . . , ex(k, n)i ∈ dom(f ) = A.Âûÿñíèì òåïåðü, êàê ñîîòíîñÿòñÿ ìåæäó ñîáîé ñåìåéñòâî âñåõ â.ï.
ìíîæåñòâ èñåìåéñòâî âñåõ âû÷èñëèìûõ ìíîæåñòâ.Ïðåäëîæåíèå 48.Åñëè A ⊆ ωk âû÷èñëèìî, òî A âû÷èñëèìî ïåðå÷èñëèìî.Äîêàçàòåëüñòâî. Ïóñòü A âû÷èñëèìî, ñëåäîâàòåëüíî, ôóíêöèÿ XA(x1, . . . , xk ) âû-÷èñëèìà. Îïðåäåëèì ÷àñòè÷íóþ ôóíêöèþ f (x) = µy[|XA (x) − 1| = 0]. Òîãäà f ÷.â.ô. è dom(f ) = A. Ñëåäîâàòåëüíî, â ñèëó ïóíêòà (3) òåîðåìû 47 A ÿâëÿåòñÿâ.ï. ìíîæåñòâîì.Óòâåðæäåíèå, îáðàòíîå ê ïðåäëîæåíèþ 48, âîîáùå ãîâîðÿ, íåâåðíî.Ìíîæåñòâî K = {x ∈ ω | ϕx(x) ↓} ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì, íî íå ÿâëÿåòñÿ âû÷èñëèìûì.Äîêàçàòåëüñòâî.
Äîêàæåì, ÷òî K âû÷èñëèìî ïåðå÷èñëèìî. Ïî òåîðåìå îá óíèâåð-Ïðåäëîæåíèå 49.ñàëüíîé ÷.ð.ô. ϕx (y) ÿâëÿåòñÿ äâóõìåñòíîé ÷.â.ô. Òîãäà ôóíêöèÿ f (x) = ϕx (x) îäíîìåñòíàÿ ÷.â.ô. ßñíî, ÷òî K = dom(f ). Îòñþäà ïî ïóíêòó (3) òåîðåìû 47 çàêëþ÷àåì, ÷òî K âû÷èñëèìî ïåðå÷èñëèìî.Äîêàæåì, ÷òî K íå âû÷èñëèìî. Äîïóñòèì, íàïðîòèâ, õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ XK (x) âû÷èñëèìà. Ðàññìîòðèì îäíîìåñòóþ ôóíêöèþ(0,åñëè ϕx (x) ↑f (x) =íå îïðåäåëåíî, åñëè ϕx (x) ↓Òàê êàê f (x) = µy[XK (x) = 0], òî f (x) ÷àñòè÷íî âû÷èñëèìà. Ïî òåîðåìå îá óíèâåðñàëüíîé ÷.ð.ô. ñóùåñòâóåò êëèíèåâñêèé íîìåð n ∈ ω òàêîé, ÷òî f (x) = ϕn (x).Ðàññìîòðèì çíà÷åíèå àðãóìåíòà x = n, ïîëó÷èì ñëåäóþùóþ öåïî÷êó ýêâèâàëåíòíûõ óñëîâèé:ϕn (n) ↓ ⇐⇒ f (n) ↓ ⇐⇒ ϕn (n) ↑ .Ïðîòèâîðå÷èå.
Ñëåäîâàòåëüíî, K íå âû÷èñëèìî.Îïðåäåëåíèå.êðåàòèâíûì.Ìíîæåñòâî K = {x ∈ ω | ϕx (x) ↓} èç ïðåäëîæåíèÿ 49 íàçûâàåòñÿÄàëåå ìû èññëåäóåì ñâîéñòâà çàìêíóòîñòè ñåìåéñòâà â.ï. ìíîæåñòâ îòíîñèòåëüíî òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé. Íàïîìíèì, ÷òî äëÿ âû÷èñëèìûõ ìíîæåñòâñïðàâåäëèâî ñëåäóþùååÏóñòü A, B ⊆ ωk âû÷èñëèìûå ìíîæåñòâà. Òîãäà ìíîæåñòâàA ∪ B , A ∩ B è ω k \ A òîæå âû÷èñëèìû.Äîêàçàòåëüñòâî. Ñì. äîêàçàòåëüñòâî ïðåäëîæåíèÿ 21.Ïðåäëîæåíèå 50.Äëÿ ñåìåéñòâà â.ï. ìíîæåñòâ çàìêíóòîñòü îòíîñèòåëüíî îáúåäèíåíèÿ è ïåðåñå÷åíèÿ îñòà¼òñÿ ñïðàâåäëèâîé.
Îäíàêî, â îòëè÷èå îò âû÷èñëèìûõ ìíîæåñòâ, â.ï. ìíîæåñòâà íåçàìêíóòû îòíîñèòåëüíî äîïîëíåíèÿ.68Ãëàâà IV. Òåîðèÿ âû÷èñëèìîñòèÏóñòü A, B ⊆ ωk âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâà. Òîãäà ìíîæåñòâà A ∪ B è A ∩ B òîæå âû÷èñëèìî ïåðå÷èñëèìû.Äîêàçàòåëüñòâî. Ïóñòü P, R ⊆ ωk+1 òàêèå âû÷èñëèìûå ìíîæåñòâà, ÷òîÏðåäëîæåíèå 51.x ∈ A ⇐⇒ ∃yP (x, y),x ∈ B ⇐⇒ ∃yR(x, y).Òîãäà äëÿ îáúåäèíåíèÿ ïîëó÷àåì:x ∈ A ∪ B ⇐⇒ ∃yP (x, y) ∨ ∃yR(x, y) ⇐⇒ ∃y P (x, y) ∨ R(x, y) ⇐⇒ ∃yQ(x, y),ãäå Q(x, y) = P (x, y) ∨ R(x, y) âû÷èñëèìûé ïðåäèêàò. Ñëåäîâàòåëüíî, A ∪ B âû÷èñëèìî ïåðå÷èñëèìî.Äëÿ ïåðåñå÷åíèÿ èìååì:x ∈ A ∩ B ⇐⇒∃yP (x, y) & ∃zR(x, z) ⇐⇒ ∃y∃z P (x, y) & R(x, z) ⇐⇒⇐⇒ ∃t P (x, ex(0, t)) & R(x, ex(1, t)) ⇐⇒ ∃tQ(x, t),ãäå Q(x, t) = P (x, ex(0, t)) & R(x, ex(1, t)) âû÷èñëèìûé ïðåäèêàò.
Ñëåäîâàòåëüíî,A ∩ B âû÷èñëèìî ïåðå÷èñëèìî.Ìíîæåñòâî A ⊆ ωk âû÷èñëèìî òîãäà è òîëüêî òîâû÷èñëèìî ïåðå÷èñëèìû.(òåîðåìà Ïîñòà).A ωk \ AÒåîðåìà 52ãäà, êîãäà èÄîêàçàòåëüñòâî. (=⇒) Ñëåäóåò èç çàìêíóòîñòè âû÷èñëèìûõ ìíîæåñòâ îòíîñèòåëüíî äîïîëíåíèÿ è ïðåäëîæåíèÿ 48.(⇐=) Ïóñòü P, R ⊆ ω k+1 òàêèå âû÷èñëèìûå ìíîæåñòâà, ÷òîx ∈ A ⇐⇒ ∃yP (x, y),x∈/ A ⇐⇒ ∃yR(x, y).Îïðåäåëèì âû÷èñëèìóþ ôóíêöèþ f (x) = µy[P (x, y) ∨ R(x, y)]. Òîãäà ïîëó÷àåì: x ∈A ⇐⇒ ∃yP (x, y) & ∀y¬R(x, y) ⇐⇒ P (x, f (x)).
Ïîýòîìó XA (x) = XP (x, f (x))ÿâëÿåòñÿ âû÷èñëèìîé ôóíêöèåé. Òàêèì îáðàçîì, A âû÷èñëèìî.Ñóùåñòâóåò ìíîæåñòâî A ⊆ ω òàêîå, ÷òî A âû÷èñëèìî ïåðå÷èñëèìî, íî ω \ A íå ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì.Äîêàçàòåëüñòâî. Ðàññìîòðèì êðåàòèâíîå ìíîæåñòâî K = {x ∈ ω | æx(x) ↓}. ÏîÑëåäñòâèå 53.ïðåäëîæåíèþ 49 ìíîæåñòâî K â.ï. Åñëè áû ω \ K áûëî â.ï., òî ïî òåîðåìå ÏîñòàK áûëî áû âû÷èñëèìûì, ÷òî íåâîçìîæíî.(òåîðåìà î ãðàôèêå) ×àñòè÷íàÿ ôóíêöèÿ f (x1 , .
. . , xk ) ÿâëÿåòñÿ ÷àñòè÷íî âû÷èñëèìîé òîãäà è òîëüêî òîãäà, êîãäà å¼ ãðàôèêÒåîðåìà 54.Γf = {hx1 , . . . , xk , yi | hx1 , . . . , xk i ∈ dom(f ), f (x1 , . . . , xk ) = y}ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì.69 19. Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâàÄîêàçàòåëüñòâî. (=⇒) Ïóñòü f ÷.â.ô. Ïî òåîðåìå îá óíèâåðñàëüíîé ÷.ð.ô.f (x) = out(run(e, ink (x), µy[q(e, x, y) = 0])),ãäå e êîä ìàøèíû Òüþðèíãà, âû÷èñëÿþùåé f . Òîãäà ïîëó÷àåìhx, yi ∈ Γf ⇐⇒ f (x) ↓= y ⇐⇒⇐⇒ ∃z q(e, x, z) = 0 & out(run(e, ink (x), z)) = y⇐⇒ ∃zR(x, y, z),ãäå R = {hx, y, zi | q(e, x, z) = 0 & out(run(e, ink (x), z)) = y}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
