1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 16
Текст из файла (страница 16)
Ïóñòü ψn (x) è θn (x) ïðèåìëåìûå óíè-âåðñàëüíûå ôóíêöèè. Íóæíî äîêàçàòü, ÷òî íàéäåòñÿ âû÷èñëèìàÿ ïåðåñòàíîâêà íàòóðàëüíûõ ÷èñåë p òàêàÿ, ÷òîψp(x) (p(y)) ' p(θx (y)),äëÿ âñåõ íàòóðàëüíûõ ÷èñåë x è y .Ëåììà 4.3.5 Åñëè ψx (y) ïðèåìëåìàÿ, òî äëÿ ëþáîé ÷.ð.ô. f (x, y, z)íàéäåòñÿ ðàçíîçíà÷íàÿ î.ð.ô.
g(x, y) òàêàÿ, ÷òî ψg(x,y) (z) ' f (x, y, z).90Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÄîêàçàòåëüñòâî. Ðàññìîòðèì ôóíêöèþf ∗ (u, z) ' f ((u)0 , (u)1 , z).Äëÿ íåå íàéäåòñÿ ðàçíîçíà÷íàÿ ôóíêöèÿ g ∗ (u) òàêàÿ, ÷òî ψg∗ (u) (z) 'f ∗ (u, z). Ïîäñòàâëÿÿ u = hx, yi, ïîëó÷èìf (x, y, z) ' f ((hx, yi)0 , (hx, yi)1 , z) ' f ∗ (hx, yi , z) ' ψg∗ (hx,yi) (z).Ôóíêöèÿ g(x, y) = g ∗ (hx, yi) óäîâëåòâîðÿåò ëåììå, òàê êàê ëåãêî óáåäèòüñÿ, ÷òî îíà ðàçíîçíà÷íà; ýòî ñëåäóåò èç ðàçíîçíà÷íîñòè g ∗ . Ëåììàäîêàçàíà.Ëåììà 4.3.6 (Ëåììà î ìíîæåñòâåííîñòè) Åñëè ψx (y) ïðèåìëå-ìàÿ ôóíêöèÿ, òî ñóùåñòâóåò ðàçíîçíà÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ h(x, t),òàêàÿ, ÷òî äëÿ ëþáûõ x, y, t ∈ N âûïîëíåíî ψx (y) ' ψh(x,t) (y).Äîêàçàòåëüñòâî. Ïðèìåíèì ëåììó 4.3.5 ê ôóíêöèè f (x, t, y) ' ψx (y) +0 · t. Ïîëó÷èì ðàçíîçíà÷íóþ ôóíêöèþ h(x, t) òàêóþ, ÷òî ψx (y) ' ψx (y) +0 · t ' ψh(x,t) (y). Ëåììà äîêàçàíà.Èç ýòîé ëåììû â ÷àñòíîñòè ñëåäóåò, ÷òî ó êàæäîé ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè æx èìååòñÿ áåñêîíå÷íî ìíîãî íîìåðîâ i òàêèõ,÷òî æx =æi ,ïðè÷åì ñóùåñòâóåò àëãîðèòì, ñòðîÿùèé ïî ëþáîìó x áåñêîíå÷íîå ñåìåéñòâî òàêèõ íîìåðîâ.
 ýòîì íåò íè÷åãî óäèâèòåëüíîãî, ïîñêîëüêó ëþáóþïðîãðàììó ìîæíî èçìåíÿòü òàê, ÷òîáû èçìåí¼ííàÿ ïðîãðàììà âû÷èñëÿëà òó æå ñàìóþ ôóíêöèþ, äîáàâëÿÿ ëþáîå êîíå÷íîå ÷èñëî îïåðàòîðîâ,êîòîðûå íå ïðîèçâîäÿò íèêàêèõ èçìåíåíèé.Çàôèêñèðóåì íåêîòîðóþ ÷àñòè÷íî ðåêóðñèâíóþ ôóíêöèþ κm (y) îòm è y òàêóþ, ÷òî äëÿ ëþáîãî m0 ∈ N, åñëè æm0 (x) ïåðåñòàíîâêà íà N,òî κm0 (y) ' æ−1m0 (y). Ìîæíî âçÿòü, íàïðèìåð, ôóíêöèþκm (y) = µx (sg |æm (x) − y| = 0).Âåðíåìñÿ ó äîêàçàòåëüñòâó òåîðåìû.
Îáùàÿ èäåÿ ñîñòîèò â òîì, ÷òîñíà÷àëà ìû óêàæåì íåêîòîðûé àëãîðèòì, ñòðîÿùèé ïî ëþáîìó z íåêîòîðóþ âû÷èñëèìóþ ïåðåñòàíîâêó hz òàêóþ, ÷òî äëÿ ëþáîãî x âûïîëíåíîõîòÿ áû îäíî èç ñëåäóþùèõ äâóõ óñëîâèé:1. ψhz (x) = æz θx κz ;2. κz ϕhz (x) æz = θx .4.3. Åäèíñòâåííîñòü óíèâåðñàëüíîé ôóíêöèè91Ïðè ýòîì hz (y) îêàæåòñÿ âû÷èñëèìîé ôóíêöèåé îò z, y . Èñïîëüçóÿ ïðèåìëåìîñòü ôóíêöèè æx (y), âîçüìåì âû÷èñëèìóþ ôóíêöèþ g(z) òàê, ÷òîáû æg(z) (y) ' hz (y).
Ïî òåîðåìå î íåïîäâèæíîé òî÷êå äëÿ íåêîòîðîãî nïîëó÷èì æn = æg(n) = hn . Ïîñêîëüêó hn âñåãäà âû÷èñëèìàÿ ïåðåñòàíîâêà, ïîëó÷àåì, ÷òî æn âû÷èñëèìàÿ ïåðåñòàíîâêà íà N. Îáîçíà÷èìp(x) = hn (x) = æn (x) è ïîäñòàâèì ýòî îáîçíà÷åíèå â âûøåïðèâåäåííûåóñëîâèÿ. Ïîëó÷èì, ÷òî äëÿ ëþáîãî x âûïîëíåíî õîòÿ áû îäíî èç ñëåäóþùèõ óñëîâèé:1. ψp(x) = pθx p−1 ;2. p−1 ψp(x) p = θx .Ïîñêîëüêó äëÿ p èìååòñÿ îáðàòíîå îòîáðàæåíèå, â ëþáîì èç ýòèõ äâóõñëó÷àåâ ìû ïîëó÷èì ψp(x) p = pθx , òî åñòü, âîçâðàùàÿñü ê íà÷àëüíîìóñïîñîáó çàïèñè àðãóìåíòîâ, ïîëó÷èì, ÷òî äëÿ ëþáûõ x è y áóäåò ñïðàâåäëèâî ψ(p(x), p(y)) ' p(θ(x, y)), ÷òî è äîêàæåò òåîðåìó.Íàì òàêæå ïîíàäîáèòñÿ îáùåå çàìå÷àíèå, êàñàþùååñÿ áóäóùåãî ïîñòðîåíèÿ ïåðåñòàíîâêè hz (y).Çàìå÷àíèå î ïîñòðîåíèè ïåðåñòàíîâêè. Ïðåäïîëîæèì, ÷òî íåêîòîðûéàëãîðèòì ïåðå÷èñëÿåò ïàðû (x, y) íàòóðàëüíûõ ÷èñåë.
Îáîçíà÷èì ÷åðåç Mt ìíîæåñòâî âñåõ òàêèõ ïàð, ïåðå÷èñëåííûõ çà ïåðâûå t øàãîâ(M0 = ∅). Ïðåäïîëîæèì, ÷òî ýòîò àëãîðèòì äåéñòâóåò òàê, ÷òî íà êàæäîì ÷¼òíîì øàãå t+1 âûáèðàåòñÿ íàèìåíüøåå x, íå ñîäåðæàùååñÿ ñðåäèëåâûõ êîîðäèíàò ïàð, âõîäÿùèõ âî ìíîæåñòâî Mt , è äëÿ íåãî êàêèìòîîáðàçîì âû÷èñëÿåòñÿ íåêîòîðîå y , íå ñîäåðæàùååñÿ ñðåäè ïðàâûõ êîîðäèíàò ïàð, âõîäÿùèõ âî ìíîæåñòâî Mt , ïîñëå ÷åãî ïîëó÷åííàÿ ïàðà(x, y) äîáàâëÿåòñÿ ê ïåðå÷èñëåíèþ: Mt+1 = Mt ∪ {(x, y)}. Íà êàæäîìíå÷¼òíîì øàãå t + 1 îñóùåñòâëÿåòñÿ ñèììåòðè÷íîå äåéñòâèå, à èìåííî, âûáèðàåòñÿ íàèìåíüøåå y , íå ñîäåðæàùååñÿ ñðåäè ïðàâûõ êîîðäèíàòïàð, âõîäÿùèõ âî ìíîæåñòâî Mt , äëÿ êîòîðîãî áåðåòñÿ íåêîòîðîå x, íåñîäåðæàùååñÿ ñðåäè ëåâûõ êîîðäèíàò ïàð, âõîäÿùèõ âî ìíîæåñòâî Mt èïîëàãàåòñÿ Mt+1 = Mt ∪ {(x, y)}S . Òîãäà îòîáðàæåíèå q(x), îïðåäåëåííîåêàê q(x) = y ⇔ (x, y) ∈ M = t∈N Mt , ÿâëÿåòñÿ âû÷èñëèìûì âçàèìíîîäíîçíà÷íûì îòîáðàæåíèåì èç ìíîæåñòâà íàòóðàëüíûõ ÷èñåë íà ñåáÿ.Äåéñòâèòåëüíî, ÷òîáû âû÷èñëèòü çíà÷åíèå q(x), íóæíî çàïóñòèòü ýòîòïðîöåññ è äîæäàòüñÿ, êîãäà ïàðà âèäà (x, y) áóäåò ïåðå÷èñëåíà, è âûäàòüy â êà÷åñòâå q(x) Âû÷èñëèìîñòü q ñëåäóåò èç Òåçèñà ×¼ð÷à, à ñâîéñòâîáûòü ïåðåñòàíîâêîé ëåãêî ïðîâåðÿåòñÿ.Òåïåðü äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà îñòàëîñü èçëîæèòü ñàìî ïîñòðîåíèå ïåðåñòàíîâêè hz .
Ìû îïèøåì àëãîðèòì, êîòîðûé áóäåò ïî çà-92Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèäàííîìó z ïåðå÷èñëÿòü ìíîæåñòâî ïàð {(x, y) | hz (x) = y}.Øàã 0. Ïîëàãàåì M0 = ∅.×åòíûé øàã t + 1. (Äîáàâëåíèå íîâîãî ýëåìåíòà â îáëàñòü îïðåäåëåíèÿhz .) Èùåì íàèìåíüøèé x, íå ñîäåðæàùèéñÿ ñðåäè ëåâûõ êîîðäèíàò ïàð,ñîäåðæàùèõñÿ â Mt . Äëÿ íåãî íàäî íàéòè w = hz (x), íå ñîäåðæàùååñÿñðåäè ïðàâûõ êîîðäèíàò ïàð, ñîäåðæàùèõñÿ â Mt , ïðè÷åì òàê, ÷òîáûäëÿ ëþáîãî y ∈ N ÷òîáû âûïîëíÿëîñü ðàâåíñòâîψw (y) ' æz θx κz (y).(4.1)Ìû íàõîäèì åãî òàê: çàôèêñèðîâàâ ðàçíîçíà÷íóþ âû÷èñëèìóþ ôóíêöèþ q(z, x) òàêóþ, ÷òî∀y ( ψq(z,x) (y) ' æz θx κz (y) ),ñóùåñòâóþùóþ ïî ëåììå 4.3.5, ìû èñïîëüçóåì ñâîéñòâî ìíîæåñòâåííîñòè (ëåììà 4.3.6) äëÿ òîãî, ÷òîáû íàéòè çíà÷åíèå w òàêîå, ÷òî∀y ( ψq(z,x) (y) ' ψw (y) )è w íå ñîäåðæèòñÿ â ìíîæåñòâå ïðàâûõ êîîðäèíàò ïàð, âõîäÿùèõ âîìíîæåñòâî Mt .
Ïîëîæèì òåïåðü hz (x) = w.Íå÷åòíûé øàã t + 1 . (Äîáàâëåíèå íîâîãî ýëåìåíòà â îáëàñòü çíà÷åíèéhz .) Îñóùåñòâëÿåòñÿ ñèììåòðè÷íûì îáðàçîì ñ ðàññìîòðåíèåì âìåñòî ðàâåíñòâà (4.1) ðàâåíñòâà θx (y) ' κz ψhz (x) æz (y), äëÿ êîòîðîãî íóæíî ïîèçâåñòíîìó u = hz (x) íàéòè x òàê, ÷òîáû óäîâëåòâîðèòü óñëîâèÿì çàìå÷àíèÿ î ïåðåñòàíîâêå.Î÷åâèäíî, ÷òî ïðè òàêîì ïîñòðîåíèè, äëÿ ëþáîãî x áóäåò âûïîëíåíî õîòÿ áû îäíî èç óïîìÿíóòûõ âûøå ðàâåíñòâ (1), (2), è ïîýòîìóïîñòðîåííàÿ íàìè ôóíêöèÿ hz (x) ñòðîèòñÿ â ñîîòâåòñòâèè ñ çàìå÷àíèåìî ïîñòðîåíèè ïåðåñòàíîâêè. ¤Óïðàæíåíèÿ.1. Äîêàæèòå, ÷òî îòíîøåíèå ïîäîáèÿ íà ìíîæåñòâå âñåõ ôóíêöèé ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè, òî åñòü ÷òî îíî ðåôëåêñèâíî,ñèììåòðè÷íî è òðàíçèòèâíî.2.
Äîêàæèòå, ÷òî åñëè ψx (y) ïðèåìëåìàÿ âû÷èñëèìàÿ ôóíêöèÿθx (y) ïðîèçâîëüíàÿ ôóíêöèÿ, ïîäîáíàÿ åé, òî θx (y) òîæå ïðèåìëåìàÿ âû÷èñëèìàÿ ôóíêöèÿ.4.4. Ïåðå÷èñëèìûå ìíîæåñòâà93Óêàçàíèå. Ïóñòü ôóíêöèè θx (y) è ψx (y) ïîäîáíû, à èìåííî äëÿ íåêîòîðîé âû÷èñëèìîé ïåðåñòàíîâêè p íàòóðàëüíûõ ÷èñåë âûïîëíåíîθp(x) (p(y)) ' pψx (y).Ïðåäïîëîæèì, ÷òî ψx (y) ïðèåìëåìàÿ ôóíêöèÿ. Äîêàæåì, ÷òî θx (y) òîæåïðèåìëåìàÿ ôóíêöèÿ.Âîçüìåì ïðîèçâîëüíóþ âû÷èñëèìóþ ÷àñòè÷íóþ ôóíêöèþ f (x, y). Ñóùåñòâóåòâû÷èñëèìàÿ ðàçíîçíà÷íàÿ ôóíêöèÿ g(x) òàêàÿ, ÷òîp−1 f (p(x), p(y)) ' ψg(x) (y).Îòñþäà ïîëó÷èìf (p(x), p(y)) ' pψg(x) (y) ' θpg(x) (py).Ñäåëàâ â ïîñëåäíåì ðàâåíñòâå çàìåíû x0 = p(x), y 0 = p(y), ïîëó÷èìf (x0 , y 0 ) ' θpgp−1 (y 0 ).Îñòàëîñü çàìåòèòü, ÷òî ôóíêöèÿ pgp−1 âû÷èñëèìà è ðàçíîçíà÷íà.3.
Ïóñòü θx (y) ïðèåìëåìàÿ ôóíêöèÿ. Äîêàæèòå, ÷òî êëàññ âñåõ ïðèåìëåìûõ ôóíêöèé ðàâåí{pθp−1 (x) (p−1 (y)) | p âû÷èñëèìàÿ ïåðåñòàíîâêà íà N}.4.4 Ïåðå÷èñëèìûå ìíîæåñòâàÎïðåäåëåíèå 4.4.1 Ìíîæåñòâî íàòóðàëüíûõ ÷èñåë S ⊆ N íàçûâà-åòñÿ âû÷èñëèìî ïåðå÷èñëèìûì3 (ñîêðàùåííî â.ï. ìíîæåñòâîì), åñëè S = ∅ ëèáî S = range (f ) äëÿ íåêîòîðîé âû÷èñëèìîé ôóíêöèèf : N → N.Ïðåäëîæåíèå 4.4.2 Êàæäîå âû÷èñëèìîå ìíîæåñòâî âû÷èñëèìî ïå-ðå÷èñëèìî.Äîêàçàòåëüñòâî.
Ïóñòü A ïðîèçâîëüíîå âû÷èñëèìîå ìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Åñëè îíî ïóñòî, òî óòâåðæäåíèå î÷åâèäíî.  ïðîòèâíîì ñëó÷àå çàôèêñèðóåì íåêîòîðîå ÷èñëî a ∈ A è îïðåäåëèì½x, åñëè x ∈ Af (x) =a, åñëè x ∈/ A.Î÷åâèäíî,÷òî A = range (f ). ¤Êàê áóäåò âèäíî èç äàëüíåéøåãî, îáðàòíîå íåâåðíî, ò.å., ñóùåñòâóþòâû÷èñëèìî ïåðå÷èñëèìûå íåâû÷èñëèìûå ìíîæåñòâà.3â ëèòåðàòóðå ìîæíî âñòðåòèòü òàêæå óñòàðåâøèé òåðìèí ðåêóðñèâíî ïåðå÷èñëèìîå ìíîæåñòâî94Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÒåîðåìà 4.4.3 (Ýêâèâàëåíòíûå îïðåäåëåíèÿ â.ï. ìíîæåñòâ) ÏóñòüS ⊆ N. Òîãäà ñëåäóþùèå óñëîâèÿ ýêâèâàëåíòíû:1. S âû÷èñëèìî ïåðå÷èñëèìî;2.
äëÿ ïîäõîäÿùåãî âû÷èñëèìîãî îòíîøåíèÿ R ⊆ N2 âûïîëíåíî∀x (x ∈ S ⇔ ∃t R(x, t));3. äëÿ ïîäõîäÿùåãî âû÷èñëèìîãî îòíîøåíèÿ R ⊆ Nk+1 âûïîëíåíî∀x (x ∈ S ⇔ ∃t1 . . . ∃tk R(x, t1 , . . . , tk ));4. S = dom (f ), äëÿ ïîäõîäÿùåé ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèè;5. S = range (f ), äëÿ ïîäõîäÿùåé ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèè.Äîêàçàòåëüñòâî. (1) ⇒ (2). Åñëè S = ∅, òî ìîæíî, íàïðèìåð, çàïèñàòü∀x (x ∈ S ⇔ ∃t(x + t + 1 = 0)). Åñëè æå S 6= ∅, òî òîãäà äëÿ íåêîòîðîéâû÷èñëèìîé ôóíêöèè f : N → N âûïîëíåíî S = range (f ).  ýòîì ñëó÷àåèìååì: x ∈ S ⇔ ∃t (x = f (t)).(2) ⇒ (3). Î÷åâèäíî.(3) ⇒ (4).
Ïóñòü R(x, t1 , . . . , tk ) îòíîøåíèå êàê â óñëîâèè (3). Îïðåäåëèì f (x) = µt R(x, (t)1 , . . . , (t)k ). Î÷åâèäíî, ÷òî f ÷àñòè÷íàÿ âû÷èñëèìàÿôóíêöèÿ è f (x) ↓⇔ ∃t1 . . . ∃tk R(x, t), îòêóäà S = dom (f ).(4) ⇒ (5). Åñëè S = dom (g) è g ÷àñòè÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ, òîïîëîæèì f (x) = x · (0(g(x)) + 1). Ôóíêöèÿ f ÷àñòè÷íàÿ âû÷èñëèìàÿ èrange (f ) = S .(5) ⇒ (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
