1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 15
Текст из файла (страница 15)
Ïóñòü x êîä íåêîòîðîé ìàøèíû T1 = hA, {q0, . . . , qr }, P1, q1, q0i,Ëåììà 42.à y êîä íåêîòîðîé ìàøèíû T2 = hA, {q0 , . . . , qs }, P2 , q1 , q0 i, ïðè÷¼ì T1 è T2 èìåþòîäèí è òîò æå âíåøíèé àëôàâèò A = {a0 , . . . , an }. Òîãäà èõ êîìïîçèöèÿ T1 ◦ T2 =hA, {q0 , . . . , qr+s }, P, q1 , q0 i èìååò ïðîãðàììóqq ,...,qsP = P1 q0r+1 ∪ P2 q1r+1 ,...,qr+s .Íàèáîëüøèé èíäåêñ ñîñòîÿíèÿ ìàøèíû ñ êîäîì t íàõîäèòñÿ ñ ïîìîùüþ âû÷èñëèìîé ôóíêöèè m(t) = ex(0, long(t)), à íàèáîëüøèé èíäåêñ ñèìâîëà âíåøíåãî àëôàâèòàñ ïîìîùüþ ôóíêöèè n(t) = ex(1, long(t)). Çàìåòèì, ÷òî â ñèëó íàøèõ ïðåäïîëîæåíèé,n(x) = n(y).Òîãäà, èñïîëüçóÿ âû÷èñëèìûå ôóíêöèèk(t, i, j) = ex(0, ex(2i 3j , t)),l(t, i, j) = ex(1, ex(2i 3j , t)),s(t, i, j) = ex(2, ex(2i 3j , t)),ìîæíî ïðåäñòàâèòü êîäû x è y â âèäåYk(x,i,j) l(x,i,j) ·5s(x,i,j)x=p22i 3j ·3,16i6m(x)06j6n(x)y=Yk(y,i,j) ·3l(y,i,j) ·5s(y,i,j)p22i 3j.16i6m(y)06j6n(y)Cëåäóþùèå äâå âû÷èñëèìûå ôóíêöèè îñóùåñòâëÿþò çàìåíó èíäåêñîâ ñîñòîÿíèéâ êîäàõ ïðîãðàìì P1 è P2 â ñîîòâåòñòâèè ñ îïðåäåëåíèåì êîìïîçèöèè ìàøèí:(k(x, i, j), åñëè k(x, i, j) 6= 0,g(x, i, j) =m(x) + 1, åñëè k(x, i, j) = 0,(k(y, i, j) + m(x), åñëè k(y, i, j) 6= 0,h(x, y, i, j) =0,åñëè k(y, i, j) = 0.Òîãäà êîä êîìïîçèöèè T1 ◦ T2 âû÷èñëÿåòñÿ ñ ïîìîùüþ ôóíêöèèYYg(x,i,j) l(x,i,j) ·5s(x,i,j)h(x,y,i,j) l(y,i,j) ·5s(y,i,j)x◦y =p22i 3j ·3×p22i+m(x) 3j·3.16i6m(x)06j6n(x)16i6m(y)06j6n(y)(∗)62Ãëàâà IV.
Òåîðèÿ âû÷èñëèìîñòèÇàìåòèì, ÷òî åñëè x, y íå óäîâëåòâîðÿþò óñëîâèþ ëåììû, òî ôóíêöèÿ â ïðàâîé ÷àñòèòîæäåñòâà (∗) âñ¼ ðàâíî îïðåäåëåíà è âû÷èñëÿåò íåêîòîðîå çíà÷åíèå, êîòîðîå íàìíà ñàìîì äåëå íå âàæíî. Ïîýòîìó ìîæíî ñ÷èòàòü, ÷òî òîæäåñòâî (∗) îïðåäåëÿåòçíà÷åíèÿ ôóíêöèè x ◦ y äëÿ ïðîèçâîëüíûõ íàòóðàëüíûõ x, y .
Îòñþäà îêîí÷àòåëüíîçàêëþ÷àåì, ÷òî ïîñòðîåííàÿ âû÷èñëèìàÿ ôóíêöèÿ x ◦ y ÿâëÿåòñÿ èñêîìîé.Äëÿ ëþáîé ÷àñòè÷íî âû÷èñëèìîé ôóíêöèèñóùåñòâóåò âû÷èñëèìàÿ ôóíêöèÿ s(y1, . . . , ym) òàêàÿ, ÷òî(î ïàðàìåòðèçàöèè).f (y1 , . . . , ym , x1 , . .
. , xn )Òåîðåìà43f (y1 , . . . , ym , x1 , . . . , xn ) = ϕns(y1 ,...,ym ) (x1 , . . . , xn ).Äîêàçàòåëüñòâî. Îáîçíà÷èì äëÿ êðàòêîñòè y = hy1, . . . , ymi, x = hx1, . . . , xni è ââå-ä¼ì ôóíêöèþ f 0 (x, y), ïîëîæèâ ïî îïðåäåëåíèþ f 0 (x, y) = f (y, x). ßñíî, ÷òî f 0 (x, y) ÷.â.ô. Ñëåäîâàòåëüíî, ñóùåñòâóåò ìàøèíà Òüþðèíãà F 0 , êîòîðàÿ å¼ âû÷èñëÿåò.Äëÿ êàæäîãî y ∈ ω îïðåäåëèì âñïîìîãàòåëüíóþ ìàøèíó Hy , êîòîðàÿ îñóùåñòâëÿåò ñëåäóþùåå ïðåîáðàçîâàíèå:q1 0 =⇒ 01y q0 0.HyÏðîãðàììà äëÿ H0 ñîñòîèò èç îäíîé êîìàíäû q1 0 → q0 0R. Åñëè æå y > 1, òîïðîãðàììà äëÿ Hy èìååò âèä:q1 0 → q2 0Rq2 0 → q3 1R... ...qy 0 → qy+1 1Rqy+1 0 → q0 1RÄîáàâèì â ýòó ïðîãðàììó äëÿ êàæäîãî 1 6 i 6 y + 1 ôèêòèâíóþ êîìàíäó qi 1 → q0 0.Òîãäà êîä ìàøèíû Hy âû÷èñëÿåòñÿ ñ ïîìîùüþ ôóíêöèè 52åñëè y = 0,p 2 · p 6 ,y+1yh(y) =QQ 2i+1 ·3·522p222 ·52 ·p2i 3 , åñëè y > 1.p2i· p23·5y+1 ·i=1i=2Çàôèêñèðóåì çíà÷åíèÿ y , ñ÷èòàÿ èõ ïàðàìåòðàìè, è ðàññìîòðèì ôóíêöèþ g(x) =f (x, y).
Ïîñòðîèì ìàøèíó Ty , âû÷èñëÿþùóþ g(x). Ñõåìà ðàáîòû Ty âûãëÿäèò ñëåäóþùèì îáðàçîì:0q1 01x1 0 . . . 01xn 0 =⇒01x1 0 . . . 01xn qα 0 =⇒ 01x1 0 . . . 01xn 01y1 qβ1 0 =⇒+(Á )nHy1Hy2=⇒ 01x1 0 . . . 01xn 01y1 01y2 qβ2 0 =⇒ . . . =⇒ 01x1 0 . . . 01xn 01y1 0 . . . 01ym qβm 0 =⇒−Hy2Hy3(Á )m+nHym0=⇒qγ 01x1 0 . . . 01xn 01y1 0 . . . 01ym 0 =⇒q0 1f (x,y) 0 .
. . 0.0−(Á)m+nF(Åñëè f 0 (x, y) íå îïðåäåëåíî, òî âûøå â ñõåìå ìàøèíà F 0 íå îñòàíàâëèâàåòñÿ.)Òàêèì îáðàçîì Ty = (Á+ )n ◦ Hy1 ◦ . . . ◦ Hym ◦ (Á− )m+n ◦ F 0 . Ïóñòü e1 = b(Á+ )n c èe2 = b(Á− )m+n ◦ F 0 c. Ëåììà 42 ïîçâîëÿåò íàì âû÷èñëèòü êîä ìàøèíû Ty ñ ïîìîùüþôóíêöèès(y) = e1 ◦ h(y1 ) ◦ . . . ◦ h(ym ) ◦ e2 .Ïîñêîëüêó ôóíêöèè x◦y è h(y) âû÷èñëèìû, çàêëþ÷àåì, ÷òî s(y) òîæå âû÷èñëèìà.Ïî ïîñòðîåíèþ ϕns(y) (x) = g(x) = f 0 (x, y) = f (y, x).
Ñëåäîâàòåëüíî, ôóíêöèÿ s(y) èñêîìàÿ. 18. Òåîðåìà î íåïîäâèæíîé òî÷êå63 çàêëþ÷åíèè ïàðàãðàôà ìû äîêàæåì s-m-n-òåîðåìó, êîòîðàÿ ñâÿçûâàåò íóìåðàöèè ϕke äëÿ ðàçëè÷íûõ k .Ñëåäñòâèå 44Äëÿ ëþáûõ m, n ∈ ω ñóùåñòâóåò (m+1)-ìåñòíàÿòàêàÿ, ÷òî(s-m-n-òåîðåìà).smn (e, y1 , . . . , ym )âû÷èñëèìàÿ ôóíêöèÿϕm+n(y1 , . . . , ym , x1 , . .
. , xn ) = ϕnsm(x1 , . . . , xn ).en (e,y1 ,...,ym )Äîêàçàòåëüñòâî. Ðàññìîòðèì (m+n+1)-ìåñòíóþ ÷.â.ô. f (e, y, x) = ϕm+n(y, x). Ïîeòåîðåìå î ïàðàìåòðèçàöèè ñóùåñòâóåò â.ô. s(e, y) òàêàÿ, ÷òî èìååò ìåñòî f (e, y, x) =ϕns(e,y) (x). Ôóíêöèÿ s ÿâëÿåòñÿ èñêîìîé s-m-n-ôóíêöèåé. 18.Òåîðåìà î íåïîäâèæíîé òî÷êåÒåîðåìà î íåïîäâèæíîé òî÷êå (äðóãîå íàçâàíèå òåîðåìà î ðåêóðñèè) áûëà äîêàçàíàÊëèíè è ÿâëÿåòñÿ îäíèì èç íàèáîëåå âàæíûõ ðåçóëüòàòîâ òåîðèè âû÷èñëèìîñòè.ż êîðîòêîå äîêàçàòåëüñòâî èñïîëüçóåò s-m-n-òåîðåìó è íà ïåðâûé âçãëÿä êàæåòñÿíåñêîëüêî ìèñòè÷åñêèì.Òåîðåìà 45Äëÿ ëþáîé ÷àñòè÷íî âû÷èñëèìîé ôóíêöèè.(î íåïîäâèæíîé òî÷êå).a∈ωϕf (a) = ϕañóùåñòâóåòòàêîå, ÷òîÄîêàçàòåëüñòâî.
Ðàññìîòðèì ÷àñòè÷íî âû÷èñëèìóþ ôóíêöèþ F (e, y, x) = ϕ2e (y, x),f (x)êîòîðàÿ ÿâëÿåòñÿ óíèâåðñàëüíîé äëÿ ñåìåéñòâà âñåõ 2-ìåñòíûõ ÷.â.ô. Ïî s-m-nòåîðåìå ñóùåñòâóåò âû÷èñëèìàÿ ôóíêöèÿ s(e, y) òàêàÿ, ÷òîϕ2e (y, x) = ϕs(e,y) (x).(∗)Ôóíêöèÿ ϕf (s(y,y)) (x) ÿâëÿåòñÿ 2-ìåñòíîé ÷.â.ô. îò ïåðåìåííûõ hy, xi. Ñëåäîâàòåëüíî, â ñèëó óíèâåðñàëüíîñòè íàéäåòñÿ êëèíèåâñêèé íîìåð n ∈ ω òàêîé, ÷òîϕf (s(y,y)) (x) = ϕ2n (y, x).(∗∗)Èç (∗) è (∗∗) ïðè e = n ñëåäóåò, ÷òî ϕf (s(y,y)) (x) = ϕs(n,y) (x). Ïîäñòàâèâ â ïîëó÷åííîå òîæäåñòâî y = n, ïîëó÷èì ϕf (s(n,n)) (x) = ϕs(n,n) (x).
Îòñþäà âèäíî, ÷òîíàòóðàëüíîå ÷èñëî a = s(n, n) ÿâëÿåòñÿ èñêîìûì.Ôóíêöèþ f (x) èç òåîðåìû î íåïîäâèæíîé òî÷êå ìîæíî íåôîðìàëüíî ïðåäñòàâëÿòü êàê ýôôåêòèâíûé ïðåîáðàçîâàòåëü ïðîãðàìì, êîòîðûé ëþáóþ ïðîãðàììó n, ðåàëèçóþùóþ ïðîöåäóðó ϕn , ïåðåðàáàòûâàåò â ïðîãðàììó f (n), ðåàëèçóþùóþ, âîîáùåãîâîðÿ, êàêóþ-òî äðóãóþ ïðîöåäóðó ϕf (n) . Èíòóèòèâíûé ñìûñë òåîðåìû î íåïîäâèæíîé òî÷êå çàêëþ÷àåòñÿ â òîì, ÷òî äëÿ ëþáîãî òàêîãî ïðåîáðàçîâàòåëÿ íàéä¼òñÿ õîòÿáû îäíà ïðîöåäóðà ϕa , êîòîðàÿ íå èçìåíÿåòñÿ ïîä åãî äåéñòâèåì, ò.
å. ϕf (a) = ϕa .Äðóãèìè ñëîâàìè, ó ëþáîãî òàêîãî ïðåîáðàçîâàòåëÿ íàéä¼òñÿ íåïîäâèæíàÿ òî÷êàïðîöåäóðà.ϕ0ϕ1...ϕa...-- ïðåîáðà-çîâàòåëüf-- ϕf (0)- ϕf (1)...- ϕf (a)...= ϕa64Ãëàâà IV. Òåîðèÿ âû÷èñëèìîñòèÒåîðåìà î íåïîäâèæíîé òî÷êå äîïóñêàåò ñëåäóþùåå îáîáùåíèå ñ ïàðàìåòðàìè x:f (x, y)ϕf (x,g(x)) = ϕg(x) Äîêàçûâàåòñÿ äàííîå îáîáùåíèå òàêg(x)æå êàê è òåîðåìà î íåïîäâèæíîé òî÷êå â êëàññè÷åñêîé ôîðìóëèðîâêå.Çàìå÷àíèå.äëÿ ëþáîé ÷àñòè÷íî âû÷èñëèìîé ôóíêöèèòàêàÿ, ÷òîìàÿ ôóíêöèÿ.ñóùåñòâóåò âû÷èñëè- ïðîãðàììèðîâàíèè èçâåñòíà ïîïóëÿðíàÿ çàäà÷à-ãîëîâîëîìêà î íàïèñàíèè ïðîãðàìì, âîñïðîèçâîäÿùèõ ñâîé ñîáñòâåííûé òåêñò (òàêèå ïðîãðàììû íàçûâàþò ñëîâîì ¾quine¿).Îêàçûâàåòñÿ, ñóùåñòâîâàíèå ïîäîáíûõ ïðîãðàìì áëèçêî ñâÿçàíî ñ òåîðåìîé îíåïîäâèæíîé òî÷êå.
 îïðåäåë¼ííîì ñìûñëå, åñëè äëÿ ÿçûêà ïðîãðàììèðîâàíèÿñïðàâåäëèâà òåîðåìà î ïàðàìåòðèçàöèè, òî ìîæíî íàïèñàòü ïðîãðàììó íà äàííîìÿçûêå, êîòîðàÿ âûâîäèò ñâîé ñîáñòâåííûé êîä.Äîêàæåì ñóùåñòâîâàíèå ïîäîáíîé ïðîãðàììû äëÿ ÿçûêà ìàøèí Òüþðèíãà, ò. å.íåîáõîäèìî ïîêàçàòü, ÷òî ñóùåñòâóåò ïðîãðàììà P ñ êîäîì e, êîòîðàÿ ïîñëå çàïóñêàâñåãäà îñòàíàâëèâàåòñÿ è âûäà¼ò (â êà÷åñòâå âûõîäíîãî çíà÷åíèÿ íà ëåíòå) ñâîé ñîáñòâåííûé êîä e.
Äëÿ ýòîãî ðàññìîòðèì âû÷èñëèìóþ ôóíêöèþ g(x, y) = x è ïðèìåíèìê íåé òåîðåìó î ïàðàìåòðèçàöèè ïîëó÷èì íåêîòîðóþ âû÷èñëèìóþ ôóíêöèþ f (x)òàêóþ, ÷òî g(x, y) = ϕf (x) (y). Äàëåå ïðèìåíèì òåîðåìó î íåïîäâèæíîé òî÷êå ê ôóíêöèè f (x) ïîëó÷èì ÷èñëî a ∈ ω òàêîå, ÷òî ϕa = ϕf (a) . Èç äîêàçàòåëüñòâà òåîðåìû îíåïîäâèæíîé òî÷êå âèäíî, ÷òî a = s(n, n) äëÿ íåêîòîðîé s-m-n-ôóíêöèè s, à èç äîêàçàòåëüñòâà òåîðåìû î ïàðàìåòðèçàöèè âûòåêàåò, ÷òî ëþáàÿ s-m-n-ôóíêöèÿ âñåãäà âêà÷åñòâå ñâîèõ çíà÷åíèé âûäàåò êîäû íåêîòîðûõ ïðîãðàìì. Îòñþäà çàêëþ÷àåì, ÷òîíàéäåííîå a ÿâëÿåòñÿ êîäîì ïðîãðàììû, è ïðîãðàììà ñ êîäîì a âû÷èñëÿåò ôóíêöèþÏðèìåð.ϕa (y) = ϕf (a) (y) = g(a, y) = a,ò. å.
âûäà¼ò ñâîé ñîáñòâåííûé êîä a.Òåîðåìà î íåïîäâèæíîé òî÷êå èìååò î÷åíü âàæíîå ñëåäñòâèå, êîòîðîå óòâåðæäàåò,÷òî íèêàêîå íåòðèâèàëüíîå (ò. å. ïðèñóùåå íåêîòîðûì, íî íå âñåì ôóíêöèÿì) ñâîéñòâî ÷àñòè÷íî âû÷èñëèìûõ ôóíêöèé íå ìîæåò áûòü ýôôåêòèâíî ðàñïîçíàâàåìûìïî èõ êëèíèåâñêèì íîìåðàì. Äëÿ äîêàçàòåëüñòâà äàííîãî óòâåðæäåíèÿ íàì ïîíàäîáèòñÿ ñëåäóþùåå îïðåäåëåíèå, êîòîðîå ÿâëÿåòñÿ ïåðåôîðìóëèðîâêîé îïðåäåëåíèÿðåêóðñèâíîãî îòíîøåíèÿ â òåðìèíàõ âû÷èñëèìûõ ôóíêöèé.âû÷èñëèìûì, åñëè åãî õàðàêòåðèñòè-Ìíîæåñòâî A ⊆ ω n íàçûâàåòñÿ÷åñêàÿ ôóíêöèÿ XA (x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
