1610906281-2dcf0fef1ce626ab2dbf8dbda8c94e1a (Машины Тьюринга и др), страница 2

Òàê ìîæíî, íàïðèìåð, ãîâîðèòü î ïðîáëåìå ðàñïîçíàâàíèÿëèíåéíî íåçàâèñèìûõ êîíå÷íûõ ñåìåéñòâ â ïðîñòðàíñòâå âåêòîðñòðîêíàä ïîëåì ðàöèîíàëüíûõ ÷èñåë, î ïðîáëåìå ðàñïîçíàâàíèÿ ïîëèíîìîâíàä ïîëåì ðàöèîíàëüíûõ ÷èñåë, èìåþùèõ êîðåíü â çàäàííîì èíòåðâàëåñ ðàöèîíàëüíûìè êîíöàìè, ïðîáëåìå ðàñïîçíàâàíèÿ ïðîãðàìì äàííîãîàëãîðèòìè÷åñêîãî ÿçûêà ñðåäè ìíîæåñòâà âñåõ òåêñòîâ è ò.ä.Ðàçóìååòñÿ, â ñèëó ñâîåãî îïðåäåëåíèÿ, ñàìà àëãîðèòìè÷åñêàÿ ïðîáëåìà ðàññìàòðèâàåòñÿ íàä íåêîòîðûì íóìåðîâàííûì ìíîæåñòâîì, èñòàëî áûòü ðàçðåøèìîñòü àëãîðèòìè÷åñêîé ïðîáëåìû çàâèñèò îò òîãî, âðàìêàõ êàêîãî íóìåðîâàííîãî ìíîæåñòâà îíà ðàññìàòðèâàåòñÿ. Îäíàêî,âî ìíîãèõ ñëó÷àÿõ åñòåñòâåííûå íóìåðàöèè êëàññîâ îáúåêòîâ îêàçûâàþòñÿ ýêâèâàëåíòíûìè ìåæäó ñîáîé â íåêîòîðîì ñìûñëå. íàñòîÿùåå âðåìÿ î ðàçðåøèìîñòè è íåðàçðåøèìîñòè àëãîðèòìè÷åñêèõ ïðîáëåì èçâåñòíî äîñòàòî÷íî ìíîãî.

Íàïðèìåð, èçâåñòíî, ÷òîíå ñóùåñòâóåò àëãîðèòìà, ïîçâîëÿþùåãî ïî ïðîèçâîëüíîìó ìíîãî÷ëå-f (x1 , . . . , xn ) ñ öåëî÷èñëåííûìè êîýôôèöèåíòàìè óçíàâàòü, åñòü ëè óóðàâíåíèÿ f (x1 , . . . , xn ) = 0 öåëî÷èñëåííîå ðåøåíèå, òî åñòü ñóùåñòâóþò1ëè òàêèå öåëûå ÷èñëà z1 , . . . , zn , ÷òî f (z1 , . . . , zn ) = 0 èëè íåò. Ïîæàëóé,íóîäíèì èç ñàìûõ ëþáîïûòíûõ è âàæíûõ ðåçóëüòàòîâ ÿâëÿåòñÿ ðåçóëüòàòî òîì, ÷òî íåðàçðåøèìà ïðîáëåìà ðàñïîçíàâàíèÿ èñòèííûõ ìàòåìàòè÷åñêèõ óòâåðæäåíèé. Ýòîò ìàòåìàòè÷åñêèé ðåçóëüòàò ñòðîãî äîêàçûâàåò,÷òî ìàòåìàòè÷åñêàÿ äåÿòåëüíîñòü íîñèò ïðèíöèïèàëüíî òâîð÷åñêèé õàðàêòåð.3Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå è òåîðåìà ÐàéñàÄëÿ êàæäîéâû÷èñëèìîé ôóíêöèè h(t, x̄) ñóùåñòâóåò âñþäó îïðåäåë¼ííàÿ âû÷èñëèìàÿ ôóíêöèÿ n(x̄) òàêàÿ, ÷òîÒåîðåìà 3.1 (Òåîðåìà Êëèíè î íåïîäâèæíîé òî÷êå)æh(n(x̄),x̄) = æn(x̄) .(Ñëó÷àé ïóñòîãî êîðòåæà x̄) Äëÿ êàæäîé âû÷èñëèìîé ôóíêöèè h(t)ñóùåñòâóåò íàòóðàëüíîå ÷èñëî n òàêîå, ÷òîæh(n) = æn .1Ýòî ðåøåíèå 10é ïðîáëåìû Ãèëüáåðòà, ïîëó÷åííîå â 70õ ãîäàõ XX âåêà ñîâåò-ñêèì è ðîññèéñêèì ìàòåìàòèêîì Þ.Â.

Ìàòèÿñåâè÷åì7Äîêàçàòåëüñòâî.Çàìåòèì, ÷òî {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̄),Âû÷èñëèìóþ ôóíêöèþà ÷èñëîh(t)n = s(a0 , a0 ).

â ôîðìóëèðîâêå òåîðåìû î íåïîäâèæ-íîé òî÷êå ìîæíî àññîöèèðîâàòü ñ àëãîðèòìè÷åñêèì ïðåîáðàçîâàòåëåìïðîãðàìì. Èç ýòîé òåîðåìû ñëåäóåò, ÷òî äëÿ ëþáîãî òàêîãî àëãîðèòìè÷åñêîãî ïðåîáðàçîâàòåëÿ ïðîãðàìì íàéäåòñÿ òàêàÿ ïðîãðàììàðåçóëüòàòå å¼ ïðåîáðàçîâàíèÿ ïîëó÷èòñÿ ïðîãðàììà÷èñëÿåò òó æå ñàìóþ ôóíêöèþ:Óïðàæíåíèå.h(n),n,÷òî âêîòîðàÿ âû-æh(n) = æn .Äîêàçàòü âòîðóþ ÷àñòü òåîðåìû î íåïîäâèæíîé òî÷êå.Ïóñòü X ïðîèçâîëüíûé íåïóñòîéêëàññ ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé, íå ñîâïàäàþùèé ñ êëàññîì âñåõ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé. Òîãäà ìíîæåñòâîÒåîðåìà 3.2 (Òåîðåìà Ðàéñà){x | æx ∈ X}íîìåðîâ ôóíêöèé, ïîïàäàþùèõ â êëàññ X, íå âû÷èñëèìî.Äîêàçàòåëüñòâî.{x | æx ∈ X}Ïðåäïîëîæèì ïðîòèâíîå, à èìåííî, ÷òî îòíîøåíèåâû÷èñëèìî. Ïîëüçóÿñü òåì, ÷òî êëàññXíåïóñò è íå ñîâ-ïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íûõ âû÷èñëèìûõ ôóíêöèé, çàôèêñèðóåìíàòóðàëüíûå ÷èñëàëèìóþ ôóíêöèþfaèbòàêèå, ÷òîæa ∈ Xèæb ∈/ X.ñëåäóþùèì îáðàçîì:f (x) =b,a,åñëèåñëè8æx ∈ Xæx ∈/ X.Îïðåäåëèì âû÷èñ-Ïî òåîðåìå î íåïîäâèæíîé òî÷êå, ñóùåñòâóåòÒåïåðü ïðåäïîëîæèì, ÷òîæ n ∈ X.n ∈ N òàêîå, ÷òî æf (n) =æn .æn = æf (n) = æb ∈/ X.ÒîãäàÏðîòèâîðå÷èå.Çíà÷èò îñòàåòñÿ òîëüêî ñëó÷àéX.æn ∈/ X.æn = æf (n) = æa ∈æn ∈/ X íåâîçìîæåí.Íî òîãäàÎïÿòü ïîëó÷èëè ïðîòèâîðå÷èå.

Çíà÷èò è ñëó÷àéÎòñþäà çàêëþ÷àåì, ÷òî ïðåäïîëîæåíèå î âû÷èñëèìîñòè ìíîæåñòâà{x | æx ∈ X}n åñòü êîä ïðîãðàììû, âû÷èñëÿþùåé ôóíêöèþ æn . Èçíåâåðíî.Âñïîìíèì, ÷òîòåîðåìû Ðàéñà ñëåäóåò, ÷òî ïðîèçâîëüíîå ñâîéñòâî âû÷èñëèìûõ ôóíêöèé ðàñïîçíàâàåìî ïî âû÷èñëÿþùèì èõ ïðîãðàììàì ñ ïîìîùüþ íåêîòîðîãî àëãîðèòìà òîëüêî â òåõ ñëó÷àÿõ, êîãäà ëèáî âñå âû÷èñëèìûå ôóíêöèè îáëàäàþò äàííûì ñâîéñòâîì ëèáî íè îäíà âû÷èñëèìàÿ ôóíêöèÿ èìíè îäíî íåòðèâèàëüíîå ñâîéñòâî âû÷èñëèìûõ ôóíêöèé àëãîðèòìè÷åñêè íå ðàñïîçíàâàåìî ïî èõ ïðîãðàììàìíå îáëàäàåò. Èíûìè ñëîâàìè,.4Âû÷èñëèìî ïåðå÷èñëèìûå ìíîæåñòâàÌíîæåñòâî S ⊆ N íàçûâàåòñÿ âû÷èñëèìî ïåðå÷èñëèìûì (ñîêðàù¼ííî â.ï.

ìíîæåñòâîì), åñëè S = ∅ ëèáî S = range (f )äëÿ íåêîòîðîé âñþäó îïðåäåë¼ííîé âû÷èñëèìîé ôóíêöèè f : N → N.Îïðåäåëåíèå 4.12Íåôîðìàëüíî, â. ï. ìíîæåñòâà ýòî òàêèå ìíîæåñòâà, êîòîðûå ìîæíî ïåðå÷èñëèòü íåêîòîðûì àëãîðèòìè÷åñêèì ïðîöåññîì, êîòîðûé âðåìÿîò âðåìåíè ìîæåò âûäàâàòü íåêîòîðûå ÷èñëà, è âñ¼, ÷òî ýòîò ïðîöåññêîãäàëèáî âûäàñò, îáðàçóåò ýòî â.ï. ìíîæåñòâî.Ïðîñòåéøèìè ïðèìåðàìè â.ï.

ìíîæåñòâ ìîãóò ñëóæèòü∅, N,ëþáîåêîíå÷íîå ìíîæåñòâî. ×èòàòåëþ ïðåäëàãàåòñÿ ñàìîìó óáåäèòüñÿ â ýòîì.Ïðåäëîæåíèå 4.2÷èñëèìî.Äîêàçàòåëüñòâî.Êàæäîå âû÷èñëèìîå ìíîæåñòâî âû÷èñëèìî ïåðåÏóñòüA ⊆ N ïðîèçâîëüíîå âû÷èñëèìîå ìíîæå-ñòâî íàòóðàëüíûõ ÷èñåë. Åñëè îíî ïóñòî, òî óòâåðæäåíèå î÷åâèäíî. Âïðîòèâíîì ñëó÷àå çàôèêñèðóåì íåêîòîðîå ÷èñëîf (x) =Î÷åâèäíî,÷òî2x,a,åñëèa∈Aè îïðåäåëèìx∈Aâ ïðîòèâíîîì ñëó÷àå.A = range (f ). â ëèòåðàòóðå ìîæíî âñòðåòèòü òàêæå óñòàðåâøèé òåðìèí ðåêóðñèâíî ïåðå÷èñ-ëèìîå ìíîæåñòâî9Òåîðåìà 4.3 (Òåîðåìà Ïîñòà) Ïðîèçâîëüíîå ìíîæåñòâî íàòóðàëüíûõ ÷èñåë âû÷èñëèìî òîãäà è òîëüêî òîãäà, êîãäà îíî âû÷èñëèìî ïåðå÷èñëèìî è åãî äîïîëíåíèå âû÷èñëèìî ïåðå÷èñëèìî.Äîêàçàòåëüñòâî.Âû÷èñëèìàÿ ïåðå÷èñëèìîñòü ëþáîãî âû÷èñëèìîãîìíîæåñòâà à òàêæå åãî äîïîëíåíèÿ (êîòîðîå òàêæå áóäåò âû÷èñëèìîïåðå÷èñëèìûì) ñëåäóåò èç ïðåäëîæåíèÿ 4.2.Ïðåäïîëîæèì, ÷òî ìíîæåñòâàA ⊆ N è N \ A â.

ï. Íåôîðìàëüíî ìîæA ñëåäóþùèìíî îïèñàòü àëãîðèòì ðàñïîçíàâàíèÿ ýëåìåíòîâ ìíîæåñòâàîáðàçîì:îäíîâðåìåííî ïåðå÷èñëÿåì ìíîæåñòâî÷èñëîx,Aè åãî äîïîëíåíèå;êîòîðîå íàñ èíòåðåñóåò, îáÿçàòåëüíî ïîÿâèòñÿ â îä-íîì èç ýòèõ ïåðå÷èñëåíèé, è ýòî äàñò íàì íåïîñðåäñòâåííûéîòâåò íà âîïðîñ x∈ A?.Áîëåå ôîðìàëüíîå äîêàçàòåëüñòâî âûãëÿäèò òàê. Ñëó÷àé, êîãäà õîòÿáû îäíî èç ýòèõ ìíîæåñòâ ïóñòî, òðèâèàëåí.

Ïîýòîìó ìîæíî ñ÷èòàòü,÷òî îáà îíè ÿâëÿþòñÿ îáëàñòÿìè çíà÷åíèé âû÷èñëèìûõ âñþäó îïðåäå-A = range (f ), N \ A = range (g). Îïðåäåëèì âñþäóh(x) = µt(x = f (t) ∨ x = g(t)).óáåäèòüñÿ, ÷òî x ∈ A ⇔ x = f (h(x)).ë¼ííûõ ôóíêöèé:îïðåäåë¼ííóþ âû÷èñëèìóþ ôóíêöèþÍåòðóäíîÑëåäóþùåå ïðåäëîæåíèå äà¼ò íàì âåñüìà óäîáíûé èíñòðóìåíò äëÿäîêàçàòåëüñòâà âû÷èñëèìîé ïåðå÷èñëèìîñòè ìíîæåñòâ.Ïðîèçâîëüíîå ìíîæåñòâî A ⊆ N âû÷èñëèìî ïåðå÷èñëèìî òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò âû÷èñëèìîå áèíàðíîåîòíîøåíèå R(t, x) òàêîå, ÷òî äëÿ âñåõ x ∈ N âûïîëíåíîÏðåäëîæåíèå 4.4x ∈ A ⇔ ∃tR(t, x).Äîêàçàòåëüñòâî.

Ïóñòü ìíîæåñòâî A âû÷èñëèìî ïåðå÷èñëèìî. ÅñëèA = ∅, òî â êà÷åñòâå R(t, x) ìîæíî âçÿòü ïóñòîå îòíîøåíèå. Åñëè íåò,òî A = range (f ), äëÿ ïîäõîäÿùåé ðåêóðñèâíîé ôóíêöèè f , è äëÿ ëþáîãîx ñïðàâåäëèâà ýêâèâàëåíòíîñòüx ∈ A ⇔ (∃tx = f (t)).Îòñþäà ñëåäóåò, ÷òî â êà÷åñòâåR(t, x)ãîäèòñÿ âû÷èñëèìîå îòíîøåíèåx = f (t).Äîêàæåì óòâåðæäåíèå â îáðàòíóþ ñòîðîíó.

Ïóñòü äëÿ ëþáîãîïîëíåíîx ∈ A ⇔ ∃tR(t, x).ÅñëèA = ∅,10xâû-òî äîêàçûâàòü íå÷åãî. ÅñëèA 6= ∅,òî çàôèêñèðóåì íåêîòîðûé ýëåìåíòôóíêöèÿf (z),a ∈ A.Ëåãêî âèäåòü, ÷òîîïðåäåë¼ííàÿ, êàêf (z) =(z)1 , åñëè R((z)0 , (z)1 )a, â ïðîòèâíîì ñëó÷àåðåêóðñèâíà è îáëàäàåò ñâîéñòâîìrange (f ) = A. Ãðàôèêîì ÷àñòè÷íîé ôóíêöèè f : Nk 99K N íàçûâàåòñÿ ìíîæåñòâî Γ(f ) = {hx1, . . . , xk , yi | f (x1, . . .

, xk ) = y}.Òåîðåìà 4.6 (Òåîðåìà î ãðàôèêå) Ïðîèçâîëüíàÿ ÷àñòè÷íàÿ ôóíêöèÿf : Nk 99K N ÿâëÿåòñÿ ÷.ð.ô. òîãäà è òîëüêî òîãäà, êîãäà å¼ ãðàôèê â. ï. ìíîæåñòâî.Îïðåäåëåíèå 4.5Äîêàçàòåëüñòâî.f : Nk 99K N ÷.ð.ô. Òîãäà îíà èìååò ïðåäñòàâëåíèå â âèäå f (x̄) ' U (µtT (a, hx̄i, t)), äëÿ íåêîòîðîãî a ∈ N. Òåïåðüî÷åâèäíî, ÷òî äëÿ ëþáîãî z âûïîëíåíîz ∈ Γ(f ) ⇔ ∃t seq (z) ∧ lh (z) = k + 1 ∧ T (a, h(z)0 , . . . , (z)k−1 i, t) ∧∀t0 < t¬T (a, h(z)0 , . . . , (z)k−1 i, t0 ) ∧ (z)k = U (t) ,Ïóñòüè óòâåðæäåíèå ñëåäóåò èç Ïðåäëîæåíèÿ 4.4.f : Nk → N âû÷èñëèìî ïåðå÷èñëèì. Íåôîðìàëüíî, ïðîöåññ âû÷èñëåíèÿ ôóíêöèè f ìîæíî îñóùåñòâèòüòàê: âçÿâ àðãóìåíòû x̄, ïåðå÷èñëÿåì ìíîæåñòâî Γ(f ) äî òåõ ïîð, ïîêàíå âñòðåòèì ÷èñëî âèäà hx̄, yi.

Êàê òîëüêî ýòî ïðîèçîéä¼ò, âûäàäèì y âÏóñòü òåïåðü ãðàôèêΓ(f )ôóíêöèèêà÷åñòâå îòâåòà.Γ(f ) = ∅, òîf = ∅ è ïîýòîìó f ÷àñòè÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ. Åñëè Γ(f ) 6= ∅,òî ñóùåñòâóåò âñþäó îïðåäåë¼ííàÿ âû÷èñëèìàÿ ôóíêöèÿ g òàêàÿ, ÷òîΓ(f ) = range (g). Ôóíêöèþ f òåïåðü ìîæíî îïðåäåëèòü òàê:Äàäèì òåïåðü áîëåå ôîðìàëüíîå äîêàçàòåëüñòâî. Åñëèf (x1 , . . . , xk ) = (g(µt [(g(t))0 = x1 & . .

. & (g(t))k−1 = xk ]))k .Îòñþäà ñëåäóåò, ÷òîf ÷àñòè÷íàÿ âû÷èñëèìàÿ ôóíêöèÿ.Òåîðåìà 4.7 Ïåðåñå÷åíèå è îáúåäèíåíèå ëþáûõ äâóõ â. ï. ìíîæåñòâòîæå ÿâëÿåòñÿ â. ï. ìíîæåñòâîì.11Äîêàçàòåëüñòâî. Ñíà÷àëà ìû ïðåäñòàâèì íåôîðìàëüíîå îïèñàíèå ïðîöåäóðû ïåðå÷èñëåíèÿ òàêèõ ìíîæåñòâ. ÅñëèAèB â.

ï. ìíîæåñòâà, òîäëÿ òîãî, ÷òîáû ïåðå÷èñëèòü èõ îáúåäèíåíèå, íóæíî îäíîâðåìåííî çàïóñòèòü ïðîöåññû ïåðå÷èñëåíèÿ ýòèõ ìíîæåñòâ è ïåðå÷èñëÿòü âñå ýëåìåíòû, êîòîðûå áóäóò âûäàíû õîòÿ áû îäíèì ïðîöåññîì. Äëÿ ïåðå÷èñëåíèÿïåðåñå÷åíèÿ ýòèõ ìíîæåñòâ íóæíî ïîî÷åðåäíî äåëàòü øàãè â ïåðå÷èñëåíèè ýòèõ ìíîæåñòâ è êàæäûé ðàç, êîãäà ñðåäè ýëåìåíòîâ, ïåðå÷èñëÿåìûõ ýòèìè ïðîöåññàìè ïîÿâëÿåòñÿ íîâûé, åù¼ íå ïåðå÷èñëåííûé íèîäíèì ïðîöåññîì ýëåìåíò, äîáàâëÿòü åãî â èòîãîâîå ïåðå÷èñëåíèå.Äàäèì òåïåðü ôîðìàëüíîå äîêàçàòåëüñòâî, èñïîëüçóþùåå ïðåäñòàâëåíèå â.ï. ìíîæåñòâ èç Ïðåäëîæåíèÿ 4.4. ÏóñòüA è B â. ï. ìíîæåñòâà.Åñëè õîòü îäíî èç ýòèõ ìíîæåñòâ ïóñòî, òî óòâåðæäåíèå òðèâèàëüíî.Ïðåäïîëîæèì, ÷òî îíè îáà íåïóñòû.

Òîãäà äëÿ ïîäõîäÿùèõ âû÷èñëèìûõ îòíîøåíèéP (t, x)èQ(t, x)ñïðàâåäëèâû ýêâèâàëåíòíîñòèx ∈ A ↔ ∃tP (t, x)èx ∈ B ↔ ∃tQ(t, x).Âû÷èñëèìàÿ ïåðå÷èñëèìîñòü ìíîæåñòâàA∪Bñëåäóåò èç ýêâèâà-ëåíòíîñòèx ∈ A ∪ B ⇔ ∃t(P (t, x) ∨ Q(t, x)),à âû÷èñëèìàÿ ïåðå÷èñëèìîñòü ìíîæåñòâàA∩Bñëåäóåò èç ýêâèâàëåíò-íîñòèx ∈ A ∩ B ⇔ ∃t(P ((t)0 , x) ∧ Q((t)1 , x)).Òåîðåìà 4.8ìûì.Ñóùåñòâóåò â.

ï. ìíîæåñòâî, íå ÿâëÿþùååñÿ âû÷èñëè-Äîêàçàòåëüñòâî. êà÷åñòâå òàêîãî ìíîæåñòâî ìîæíî âçÿòü, íàïðè-K = {x | {x}(x) ↓}.Äîñòàòî÷íî ïîíÿòü, ÷òî ýòî â. ï. ìíîæåñòâî. Äåéñòâèòåëüíî, èç {x}(x) 'U (µtT (x, hxi, t)) ñëåäóåò, ÷òî x ∈ K ýêâèâàëåíòíî óñëîâèþ ∃tT (x, hxi, t),îòêóäà è ñëåäóåò óòâåðæäåíèå. ìåð, îïðåäåë¼ííîå ðàíåå íåâû÷èñëèìîå ìíîæåñòâî12.