1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 15
Текст из файла (страница 15)
Òàê ìîæíî, íàïðèìåð, ãîâîðèòü î ïðîáëåìå ðàñïîçíàâàíèÿëèíåéíî íåçàâèñèìûõ êîíå÷íûõ ñåìåéñòâ â ïðîñòðàíñòâå âåêòîðñòðîêíàä ïîëåì ðàöèîíàëüíûõ ÷èñåë, î ïðîáëåìå ðàñïîçíàâàíèÿ ïîëèíîìîâíàä ïîëåì ðàöèîíàëüíûõ ÷èñåë, èìåþùèõ êîðåíü â çàäàííîì èíòåðâàëåñ ðàöèîíàëüíûìè êîíöàìè, ïðîáëåìå ðàñïîçíàâàíèÿ ïðîãðàìì äàííîãîàëãîðèòìè÷åñêîãî ÿçûêà ñðåäè ìíîæåñòâà âñåõ òåêñòîâ è ò.ä.Ðàçóìååòñÿ, â ñèëó ñâîåãî îïðåäåëåíèÿ, ñàìà àëãîðèòìè÷åñêàÿ ïðîáëåìà ðàññìàòðèâàåòñÿ íàä íåêîòîðûì íóìåðîâàííûì ìíîæåñòâîì, èñòàëî áûòü ðàçðåøèìîñòü àëãîðèòìè÷åñêîé ïðîáëåìû çàâèñèò îò òîãî, âðàìêàõ êàêîãî íóìåðîâàííîãî ìíîæåñòâà îíà ðàññìàòðèâàåòñÿ. Îäíàêî,âî ìíîãèõ ñëó÷àÿõ åñòåñòâåííûå íóìåðàöèè êëàññîâ îáúåêòîâ îêàçûâàþòñÿ ýêâèâàëåíòíûìè ìåæäó ñîáîé â íåêîòîðîì ñìûñëå. Ââèäó ýòîãî,ðàçðåøèìîñòü ïðîáëåìû íå çàâèñèò îò êîíêðåòíîãî âûáîðà åñòåñòâåííîéíóìåðàöèè. Áîëåå òî÷íûé ñìûñë ýòîìó óòâåðæäåíèþ ìîæíî ïðèäàòü ÷åðåç óòî÷íåíèå ïîíÿòèÿ ýêâèâàëåíòíîñòè, ïðèâîäèìîãî íèæå.Îïðåäåëåíèå 4.1.5 Ïóñòü ν1 íóìåðàöèÿ ìíîæåñòâà S è ν0 íóìåðàöèÿ íåêîòîðîãî åãî ïîäìíîæåñòâà S0 ⊆ S .
Áóäåì ãîâîðèòü, ÷òîíóìåðàöèÿ ν0 ñâîäèòñÿ ê íóìåðàöèè ν1 , åñëè ñóùåñòâóåò òàêàÿ âû÷èñëèìàÿ ôóíêöèÿ f , ÷òî ν0 = ν1 f . Ýòîò ôàêò îáîçíà÷àåòñÿ, êàê ν0 6 ν1 .Åñëè ν0 6 ν1 è ν1 6 ν0 , òî ãîâîðÿò, ÷òî íóìåðàöèè ν0 è ν1 ýêâèâàëåíòíû. Ýòîò ôàêò îáîçíà÷àåòñÿ, êàê ν0 ≡ ν1 .Èíà÷å ãîâîðÿ, íóìåðàöèÿ ν0 ñâîäèòñÿ ê íóìåðàöèè ν1 , åñëè, ðàñïîëàãàÿ íóìåðàöèåé ν1 , ìû ìîæåì ñ÷èòàòü, ÷òî ðàñïîëàãàåì è íóìåðàöèåéν0 , ïîëó÷àÿ åå â âèäå êîìïîçèöèè ñ âû÷èñëèìîé ôóíêöèåé.4.1. Íóìåðàöèè è àëãîðèòìè÷åñêèå ïðîáëåìû85Óïðàæíåíèÿ.1.
Äîêàçàòü, ÷òî îòíîøåíèå ≡ íà íóìåðàöèÿõ ïðîèçâîëüíîãî íåïóñòîãî ìíîæåñòâà S ðåôëåêñèâíî, ñèììåòðè÷íî è òðàíçèòèâíî, òî åñòüîíî ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè.2. Ïóñòü ν0 è ν1 ýêâèâàëåíòíûå íóìåðàöèè îäíîãî è òîãî æå ìíîæåñòâà. Äîêàçàòü, ÷òî äëÿ ëþáîãî ïîäìíîæåñòâà S0 ⊆ S àëãîðèòìè÷åñêàÿ ïðîáëåìà S0 ðàçðåøèìà íàä (S, ν0 ) òîãäà è òîëüêî òîãäà,êîãäà îíà ðàçðåøèìà íàä (S, ν1 ). Ýòî îçíà÷àåò, ÷òî ïðè èçó÷åíèèàëãîðèòìè÷åñêèõ ïðîáëåì íàä íóìåðîâàííûìè ìíîæåñòâàìè, â ýêâèâàëåíòíûõ íóìåðàöèÿõ ðàçðåøèìû îäíè è òå æå ïðîáëåìû.Òåîðåìà 4.1.6 Âñÿêàÿ ðàçðåøèìàÿ íóìåðàöèÿ áåñêîíå÷íîãî ìíîæåñòâàýêâèâàëåíòíà íåêîòîðîé îäíîçíà÷íîé íóìåðàöèè.Äîêàçàòåëüñòâî.
Ïóñòü ν ðàçðåøèìàÿ íóìåðàöèÿ áåñêîíå÷íîãî ìíîæåñòâà S . Îïðåäåëèì ôóíêöèþ f ñëåäóþùèì îáðàçîì:f (0) = 0f (k + 1) = min{z | νz ∈/ {νf (0), . . . , νf (k)}}.Ôóíêöèÿ f âñþäó îïðåäåëåíà â ñèëó áåñêîíå÷íîñòè ìíîæåñòâà S . Ïîñêîëüêó íóìåðàöèÿ ν ðàçðåøèìà, ìû èìååì âîçìîæíîñòü ñ ïîìîùüþ çàïóñêà íåêîòîðîé àëãîðèòìè÷åñêîé ïðîöåäóðû ïî ïðîèçâîëüíûì äàííûìíàòóðàëüíûì ÷èñëàì x è y ñðàâíèòü, ðàâíû ëè çíà÷åíèÿ ν(x) è ν(y).
Îòñþäà âèäíî, ÷òî ôóíêöèÿ f (x) èíòóèòèâíî âû÷èñëèìà. Ïî òåçèñó ×¼ð÷àîíà ðåêóðñèâíà.Îïðåäåëèì ν ∗ (x) = νf (x). Íóìåðàöèÿ ν ∗ íóìåðóåò íåêîòîðîå ïîäìíîæåñòâî â S . Äîêàæåì, ÷òî ýòà íóìåðàöèÿ îäíîçíà÷íà è íóìåðóåò âñ¼S . Îäíîçíà÷íîñòü ñëåäóåò èç î÷åâèäíîãî ñâîéñòâàν ∗ (k + 1) = νf (k + 1) ∈/ {ν ∗ (0), . . .
, ν ∗ (k)}(òî åñòü ν ∗ (k + 1) íå ñîâïàäàåò íè ñ îäíèì èç ÷èñåë ν ∗ (0), . . . , ν ∗ (k)).Ïîêàæåì òåïåðü, ÷òî îáëàñòü çíà÷åíèé íóìåðàöèè ν åñòü âñ¼ ìíîæåñòâî S . Îïðåäåëèì äëÿ s ∈ S : m(s) = min{i | ν(i) = s}. ÏóñòüM = {m(s) | s ∈ S} = {a0 < a1 < a2 < . . .}.Ñëåäóþùåå ñâîéñòâî äîñòàòî÷íî î÷åâèäíî:86Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÅñëè x ∈/ M , òî ñóùåñòâóåò x0 < x òàêîå, ÷òî νx0 = νx.Îòñþäà ñëåäóåò, ÷òî åñëè z < ak+1 , òî z = ai äëÿ íåêîòîðîãî i < k + 1.Äîñòàòî÷íî èíäóêöèåé ïîêàçàòü, ÷òî f (j) = aj äëÿ âñåõ j ∈ N.
Î÷åâèäíî, ÷òî m(ν(0)) = 0, îòêóäà ñëåäóåò a0 = 0. Ïðåäïîëîæèì, ÷òî ðàâåíñòâàf (j) = aj óæå äîêàçàíû äëÿ j = 0, . . . , k . Òîãäà â êà÷åñòâå f (k + 1) ãîäèòñÿ òîëüêî ak+1 , òàê êàê åñëè ïîïûòàòüñÿ âûáðàòü êàêîåíèáóäü ÷èñëîz < ak+1 , òî ïî ïðèâåäåííîìó âûøå ñâîéñòâó ìíîæåñòâà M νz áóäåòðàâíî îäíîìó èç ýëåìåíòîâ νai äëÿ íåêîòîðîãî i < k + 1, è áóäåò ñïðàâåäëèâî νz ∈ {νa0 , .
. . , νak }. Ïîñëåäíåå ìíîæåñòâî ïî ïðåäïîëîæåíèþèíäóêöèè áóäåò ðàâíî {νf (0), . . . , νf (k)}. Ïîñêîëüêó f (k + 1) âûáèðàåòñÿ, êàê µz(νz ∈/ {νf (0), . . . , νf (k)}), ýòî íåâîçìîæíî. Ñ äðóãîé ñòîðîíû÷èñëî ak+1 óæå ãîäèòñÿ â êà÷åñòâå f (k + 1). Çíà÷èò f (k + 1) = aj+1 . ñèëó îïðåäåëåíèÿ ν ∗ = νf èìååì ν ∗ 6 ν . Äàëåå, ν 6 ν ∗ , ïîñêîëüêóν = ν ∗ g , ãäå âû÷èñëèìàÿ ôóíêöèÿ g îïðåäåëåíà, êàê g(x) = µt(νf (t) =ν(x)). Èòàê, ν ∗ ≡ ν è ν îäíîçíà÷íà. ¤Â íàñòîÿùåå âðåìÿ î ðàçðåøèìîñòè è íåðàçðåøèìîñòè àëãîðèòìè÷åñêèõ ïðîáëåì èçâåñòíî äîñòàòî÷íî ìíîãî. Íàïðèìåð, èçâåñòíî,÷òî íåñóùåñòâóåò àëãîðèòìà, ïîçâîëÿþùåãî ïî ìíîãî÷ëåíó ñ öåëî÷èñëåííûìèêîýôôèöèåíòàìè óçíàâàòü, åñòü ó íåãî öåëûé êîðåíü èëè íåò.2 Ïîæàëóé,îäíèì èç ñàìûõ ëþáîïûòíûõ è âàæíûõ ðåçóëüòàòîâ ÿâëÿåòñÿ ðåçóëüòàòî òîì, ÷òî íåðàçðåøèìà ïðîáëåìà ðàñïîçíàâàíèÿ èñòèííûõ ìàòåìàòè÷åñêèõ óòâåðæäåíèé.
Ýòîò ìàòåìàòè÷åñêèé ðåçóëüòàò ñòðîãî äîêàçûâàåò,÷òî ìàòåìàòè÷åñêàÿ äåÿòåëüíîñòü íîñèò ïðèíöèïèàëüíî òâîð÷åñêèé õàðàêòåð.4.2 Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå è òåîðåìà ÐàéñàÒåîðåìà 4.2.1 (Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå) Äëÿ êàæ-äîé âû÷èñëèìîé ôóíêöèè h(t, x̄) ñóùåñòâóåò âñþäó îïðåäåëåííàÿ âû÷èñëèìàÿ ôóíêöèÿ n(x̄) òàêàÿ, ÷òîæh(n(x̄),x̄) = æn(x̄) .(Ñëó÷àé ïóñòîãî êîðòåæà x̄) Äëÿ êàæäîé âû÷èñëèìîé ôóíêöèè h(t)2Ýòî ðåøåíèå 10é ïðîáëåìû Ãèëüáåðòà, ïîëó÷åííîå â 70õ ãîäàõ XX âåêà ñîâåòñêèì ìàòåìàòèêîì Þ.Â.Ìàòèÿñåâè÷åì4.2. Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå è òåîðåìà Ðàéñà87ñóùåñòâóåò íàòóðàëüíîå ÷èñëî n òàêîå, ÷òîæh(n) = æn .Äîêàçàòåëüñòâî.
Çàìåòèì, ÷òî {t}(y, x̄, z) âû÷èñëèìàÿ ôóíêöèÿ îòt, y , x̄, z . Ýòî ñëåäóåò èç ñóùåñòâîâàíèÿ óíèâåðñàëüíûõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ïî òåîðåìå î ïàðàìåòðèçàöèè ñóùåñòâóåò âû÷èñëèìàÿôóíêöèÿ s(t, y, x̄) òàêàÿ, ÷òî{t}(y, x̄, z) ' {s(t, y, x̄)}(z).Äëÿ ïîäõîäÿùåãî a0 ∈ N èìååìæh(s(y,y,x̄),x̄) (z) ' {a0 }(y, x̄, z) ' {s(a0 , y, x̄)}(z) ' æs(a0 ,y,x̄) (z).Ïîäñòàâèâ y = a0 , ïîëó÷èìæh(s(a0 ,a0 ,x̄),x̄) (z) ' æs(a0 ,a0 ,x̄) (z),îòêóäà ÿñíî, ÷òî ôóíêöèÿ n(x̄) = s(a0 , a0 , x̄) ãîäèòñÿ â êà÷åñòâå èñêîìîé.Ñëó÷àé ïóñòîãî êîðòåæà ïåðåìåííûõ x̄ ðàññìàòðèâàåòñÿ àíàëîãè÷íî.Ïîæàëóé, ðàçíèöà ñîñòîèò òîëüêî â òîì, ÷òî â ðåçóëüòàòå ïîëó÷èòñÿ íåôóíêöèÿ n(x̄) = s(a0 , a0 , x̄), à ÷èñëî n = s(a0 , a0 ). ¤Âû÷èñëèìóþ ôóíêöèþ h(t) â ôîðìóëèðîâêå òåîðåìû î íåïîäâèæíîé òî÷êå ìîæíî àññîöèèðîâàòü ñ àëãîðèòìè÷åñêèì ïðåîáðàçîâàòåëåìïðîãðàìì.
Èç ýòîé òåîðåìû ñëåäóåò, ÷òî äëÿ ëþáîãî òàêîãî àëãîðèòìè÷åñêîãî ïðåîáðàçîâàòåëÿ ïðîãðàìì íàéäåòñÿ òàêàÿ ïðîãðàììà n, ÷òî âðåçóëüòàòå å¼ ïðåîáðàçîâàíèÿ ïîëó÷èòñÿ ïðîãðàììà h(n), êîòîðàÿ âû÷èñëÿåò òó æå ñàìóþ ôóíêöèþ: æh(n) = æn .Óïðàæíåíèå. Äîêàçàòü âòîðóþ ÷àñòü òåîðåìû î íåïîäâèæíîé òî÷êå.Òåîðåìà 4.2.2 (Òåîðåìà Ðàéñà) Ïóñòü X ïðîèçâîëüíûé íåïóñòîéêëàññ ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé, íå ñîâïàäàþùèé ñ êëàññîì âñåõ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé.
Òîãäà ìíîæåñòâî{x | æx ∈ X}íîìåðîâ ôóíêöèé, ïîïàäàþùèõ â êëàññ X, íå âû÷èñëèìî.Äîêàçàòåëüñòâî. Ïðåäïîëîæèì ïðîòèâíîå, à èìåííî, ÷òî îòíîøåíèå{x | æx ∈ X} âû÷èñëèìî. Ïîëüçóÿñü òåì, ÷òî êëàññ X íåïóñò è íå ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé, çàôèêñèðóåì88Ãëàâà 4.
Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèíàòóðàëüíûå ÷èñëà a è b òàêèå, ÷òî æa ∈ X è æb ∈/ X. Îïðåäåëèì âû÷èñëèìóþ ôóíêöèþ f ñëåäóþùèì îáðàçîì:½b, åñëè æx ∈ Xf (x) =a, åñëè æx ∈/ X.Ïî òåîðåìå î íåïîäâèæíîé òî÷êå, ñóùåñòâóåò n ∈ N òàêîå, ÷òî æf (n) =æn .Òåïåðü ïðåäïîëîæèì, ÷òî æn ∈ X. Òîãäà æn = æf (n) = æb ∈/ X.Ïðîòèâîðå÷èå.Çíà÷èò îñòàåòñÿ òîëüêî ñëó÷àé æn ∈/ X. Íî òîãäà æn = æf (n) = æa ∈X. Îïÿòü ïîëó÷èëè ïðîòèâîðå÷èå.
Çíà÷èò è ñëó÷àé æn ∈/ X íåâîçìîæåí.Îòñþäà çàêëþ÷àåì, ÷òî ïðåäïîëîæåíèå î âû÷èñëèìîñòè ìíîæåñòâà{x | æx ∈ X} íåâåðíî. ¤Âñïîìíèì, ÷òî n åñòü êîä ïðîãðàììû, âû÷èñëÿþùåé ôóíêöèþ æn . Èçòåîðåìû Ðàéñà ñëåäóåò, ÷òî ïðîèçâîëüíîå ñâîéñòâî âû÷èñëèìûõ ôóíêöèé ðàñïîçíàâàåìî ïî âû÷èñëÿþùèì èõ ïðîãðàììàì ñ ïîìîùüþ íåêîòîðîãî àëãîðèòìà òîëüêî â òåõ ñëó÷àÿõ, êîãäà ëèáî âñå âû÷èñëèìûå ôóíêöèè îáëàäàþò äàííûì ñâîéñòâîì ëèáî íè îäíà âû÷èñëèìàÿ ôóíêöèÿ èìíå îáëàäàåò. Èíûìè ñëîâàìè, íè îäíî íåòðèâèàëüíîå ñâîéñòâî âû÷èñëèìûõ ôóíêöèé àëãîðèòìè÷åñêè íå ðàñïîçíàâàåìî ïî èõ ïðîãðàììàì.4.3 Åäèíñòâåííîñòü óíèâåðñàëüíîé ôóíêöèèÌû èñïîëüçîâàëè ìàøèíû ؼíôèëäà äëÿ ïîñòðîåíèÿ êîíêðåòíîé óíèâåðñàëüíîé âû÷èñëèìîé ôóíêöèè ϕ(n, x).
Îäíàêî ìû ìîãëè áû òàêæåâûáðàòü äëÿ ýòîé öåëè íàïðèìåð, ìàøèíû Òüþðèíãà, íîðìàëüíûå àëãîðèôìû Ìàðêîâà èëè ëþáóþ äðóãóþ èç èìåþùèõñÿ ìíîãî÷èñëåííûõôîðìàëèçàöèé ïîíÿòèÿ àëãîðèòìà. Êðîìå òîãî, ìû ìîãëè áû èñïîëüçîâàòü êàêóþíèáóäü äðóãóþ êîíêðåòíóþ íóìåðàöèþ ìàøèí ؼíôèëäà.Ïîëó÷åííàÿ â ðåçóëüòàòå óíèâåðñàëüíàÿ ôóíêöèÿ ìîæåò îòëè÷àòüñÿ îòϕ. Âîçíèêàåò åñòåñòâåííûé âîïðîñ: Íàñêîëüêî ðàçëè÷íûìè ìîãóò ïîëó÷àòüñÿ óíèâåðñàëüíûå âû÷èñëèìûå ôóíêöèè? Îêàçûâàåòñÿ ÷òî âñå óíèâåðñàëüíûå âû÷èñëèìûå ôóíêöèè, óäîâëåòâîðÿþùèå îäíîìó äîñòàòî÷íî åñòåñòâåííîìó óñëîâèþ, à èìåííî òåîðåìå î ïàðàìåòðèçàöèè, áóäóò âäîñòàòî÷íî ñèëüíîì ñìûñëå îäèíàêîâûìè. Ýòîìó ôåíîìåíó è ïîñâÿùåííàñòîÿùèé ïàðàãðàô.Îïðåäåëåíèå 4.3.1 Íàçîâåì ÷àñòè÷íî ðåêóðñèâíóþ ôóíêöèþ ψn (x) îòn è x ïðèåìëåìîé åñëè äëÿ ëþáîé ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè f (n, x)4.3.
Åäèíñòâåííîñòü óíèâåðñàëüíîé ôóíêöèè89ñóùåñòâóåò ðàçíîçíà÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ g(n) òàêàÿ, ÷òî ψg(n) (x) 'f (n, x).Èç òåîðåìû î ïàðàìåòðèçàöèè ñëåäóåò, ÷òî óíèâåðñàëüíàÿ ôóíêöèÿϕ(x, y) ' æx (y), ïîñòðîåííàÿ íàìè, î÷åâèäíî, ÿâëÿåòñÿ ïðèåìëåìîé.Îïðåäåëåíèå 4.3.2 Âû÷èñëèìîé ïåðåñòàíîâêîé íàòóðàëüíûõ ÷èñåë íà-çûâàåòñÿ ëþáîå âû÷èñëèìîå âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå èç N íàN.Îïðåäåëåíèå 4.3.3 Íàçîâåì äâå ôóíêöèè ψn (x) è θn (x) ïîäîáíûìè, åñ-ëè ñóùåñòâóåò âû÷èñëèìàÿ ïåðåñòàíîâêà íàòóðàëüíûõ ÷èñåë p òàêàÿ,÷òî äëÿ ëþáûõ n, x ∈ N âûïîëíåíîψp(n) (p(x)) ' p(θn (x)).Âàæíî çàìåòèòü, ÷òî åñëè ψn (x) è θn (x) äâå ïîäîáíûå ôóíêöèè,òî âû÷èñëèìàÿ ïåðåñòàíîâêà p, óïîìÿíóòàÿ â îïðåäåëåíèè, îòîáðàæàåòïîêîîðäèíàòíî ìíîæåñòâî òðîåê{(n, x, θn (x)) | n, x ∈ N}íà ìíîæåñòâî òðîåê{(n, x, ψn (x)) | n, x ∈ N}.Îòñþäà ñëåäóåò, ÷òî ïîäîáíûå ôóíêöèè ψ è θ, ðàññìàòðèâàåìûå êàêìíîæåñòâà òðîåê íàòóðàëüíûõ ÷èñåë, ñîâïàäàþò ñ òî÷íîñòüþ äî âû÷èñëèìîé ïåðåêîäèðîâêè (èëè ïåðåîáîçíà÷åíèÿ) p íàòóðàëüíûõ ÷èñåë.Òåîðåìà 4.3.4 (Åäèíñòâåííîñòü ïðèåìëåìîé ôóíêöèè) Ëþáûå äâåïðèåìëåìûå ôóíêöèè ïîäîáíû.Äîêàçàòåëüñòâî òåîðåìû.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
