1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 13
Текст из файла (страница 13)
Åñëè t = bT c,ãäå T íåêîòîðàÿ ìàøèíà Òüþðèíãà, w = bM c, ãäå M ìàøèííîå ñëîâî â àëôàâèòåìàøèíû T , òî ïî ïîñòðîåíèþ step(t, w) = bMT0 c. Ñëåäîâàòåëüíî, step(t, w) ÿâëÿåòñÿôóíêöèåé îäíîøàãîâîãî ïðåîáðàçîâàíèÿ êîäîâ ìàøèííûõ ñëîâ. ×òî è òðåáîâàëîñüäîêàçàòü.Çàìåòèì, ÷òî åñëè t íå ÿâëÿåòñÿ êîäîì íèêàêîé ìàøèíû Òüþðèíãà,èëè w íå ÿâëÿåòñÿ êîäîì íèêàêîãî ìàøèííîãî ñëîâà, èëè w êîä ìàøèííîãî ñëîâà, ñîäåðæàùåãî ñèìâîëû, íå âõîäÿùèå â àëôàâèò ìàøèíû, òî âñ¼ ðàâíî ôóíêöèÿstep(t, w) èç ïðåäîæåíèÿ 28 îïðåäåëåíà è âû÷èñëÿåò íåêîòîðîå çíà÷åíèå, êîòîðîåíàì íà ñàìîì äåëå íå âàæíî.
Âàæíû òîëüêî òå çíà÷åíèÿ step(t, w), êîòîðûå ïîëó÷åíû èç t, w, óäîâëåòâîðÿþùèõ îïðåäåëåíèþ ôóíêöèè îäíîøàãîâîãî ïðåîáðàçîâàíèÿêîäîâ ìàøèííûõ ñëîâ. Àíàëîãè÷íîå çàìå÷àíèå îòíîñèòñÿ è ê íåñêîëüêèì ñëåäóþùèìïðåäëîæåíèÿì.Çàìå÷àíèå.Îïðåäåëåíèå.Ôóíêöèåé ìíîãîøàãîâîãî ïðåîáðàçîâàíèÿ êîäîâ ìàøèííûõ ñëîâ íà-çîâ¼ì ëþáóþ âñþäó îïðåäåë¼ííóþ ôóíêöèþ f (t, w, y), óäîâëåòâîðÿþùóþ óñëîâèþ:åñëè t = bT c, ãäå T íåêîòîðàÿ ìàøèíà Òüþðèíãà, w = bM c, ãäå M ìàøèííîåñëîâî â àëôàâèòå ìàøèíû T , òî (y) f (t, w, y) = MT .Ñóùåñòâóåò ï.ð.ô.
run(t, w, y), êîòîðàÿ ÿâëÿåòñÿ ôóíêöèåéìíîãîøàãîâîãî ïðåîáðàçîâàíèÿ êîäîâ ìàøèííûõ ñëîâ.Äîêàçàòåëüñòâî. Èñêîìàÿ ï.ð.ô. run(t, w, y) îïðåäåëÿåòñÿ ïî ñõåìå ïðèìèòèâíîé ðåÏðåäëîæåíèå 29.êóðñèè(run(t, w, 0) = w,run(t, w, y + 1) = step(t, run(t, w, y)),ãäå step(t, x) ôóíêöèÿ îäíîøàãîâîãî ïðåîáðàçîâàíèÿ êîäîâ ìàøèííûõ ñëîâ èçïðåäëîæåíèÿ 28.54Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÎïðåäåëåíèå.Ôóíêöèåé êîäè-Ïóñòü k ∈ ω ôèêñèðîâàííîå íàòóðàëüíîå ÷èñëî.íàçîâ¼ì âñþäó îïðåäåë¼ííóþ ôóíêöèþðîâàíèÿ âõîäíûõ ìàøèííûõ ñëîâink (x1 , .
. . , xk ) = bq1 01x1 0 . . . 01xk 0c.Ïðåäëîæåíèå 30.Ôóíêöèÿ ink (x1, . . . , xk ) ÿâëÿåòñÿ ïðèìèòèâíî ðåêóðñèâíîé.Äîêàçàòåëüñòâî. Ïîëîæèì v(x1, . . . , xk ) = b1x 0 . . . 01x 0cr . Åñëè k > 1, òî ôóíêöèÿ1v(x1 , . . . , xk ) =x1Yp2i− 1· p x1 ·i=1x2Ykp2i+x1 · px1 +x2 +1 · . . .i=1... ·xkYp2i+x1 +...+xk−1 +(k− 2)· px1 +...+xk +(k− 1) ,i=1è ñëåäîâàòåëüíî ÿâëÿåòñÿ ïðèìèòèâíî ðåêóðñèâíîé, â ñèëó ëåìì 18, 25 è 27.
Åñëèæå k = 0, òî v = b0cr = 2 ÿâëÿåòñÿ íóëüìåñòíîé ï.ð.ô.Òîãäà ôóíêöèÿ ink (x1 , . . . , xk ) = 21 · 31 · 50 · 7v(x1 ,...,xk ) ïðèìèòèâíî ðåêóðñèâíà.Îïðåäåëåíèå.Ñ÷¼ò÷èêîì åäèíèö â êîäå âûõîäíîãî ìàøèííîãî ñëîâà íàçîâ¼ì ëþ-áóþ âñþäó îïðåäåë¼ííóþ ôóíêöèþ f (w), óäîâëåòâîðÿþùóþ ñëåäóþùåìó óñëîâèþ:åñëè w = bq0 01y 00s c äëÿ íåêîòîðûõ y, s > 0, òî f (w) = y .Ñóùåñòâóåò ï.ð.ô. out(w), êîòîðàÿ ÿâëÿåòñÿ ñ÷¼ò÷èêîì åäèíèö â êîäå âûõîäíîãî ìàøèííîãî ñëîâà.Äîêàçàòåëüñòâî.
Èñêîìàÿ ï.ð.ô. îïðåäåëÿåòñÿ ïî ñëåäóþùåé ñõåìåÏðåäëîæåíèå 31.long(ex(3,w))out(w) =Xsg|ex(i, ex(3, w)) − 2|.i=0Ôóíêöèåé òåêóùåãî ñîñòîÿíèÿÎïðåäåëåíèå.íàçîâ¼ì ëþáóþ âñþäó îïðåäåë¼ííóþôóíêöèþ f (t, x1 , . . . , xk , y), óäîâëåòâîðÿþùóþ óñëîâèþ: åñëè t = bT c, ãäå T íåêî(y)òîðàÿ ìàøèíà Òüþðèíãà, ìàøèííîå ñëîâî M = q1 01x1 0 . . . 01xk 0 è MT = Aqi aj B , òîf (t, x1 . .
. , xk , y) = i.Ñóùåñòâóåò ï.ð.ô. q(t, x1, . . . , xk , y), êîòîðàÿ ÿâëÿåòñÿ ôóíêöèåé òåêóùåãî ñîñòîÿíèÿ.Äîêàçàòåëüñòâî. Èñïîëüçóÿ ïîñòðîåííûå â ïðåäëîæåíèÿõ 29 è 30 ôóíêöèè, îïðåäå-Ïðåäëîæåíèå 32.ëèì èñêîìóþ ï.ð.ô. ïî ñëåäóþùåé ñõåìåq(t, x1 , . . . , xk , y) = ex(1, run(t, ink (x1 , . . . , xk ), y)). 15. Ìàøèíû Òüþðèíãà vs ×àñòè÷íî ðåêóðñèâíûå ôóíêöèè 15.55Ìàøèíû Òüþðèíãà vs ×àñòè÷íî ðåêóðñèâíûåôóíêöèèÌû, íàêîíåö, ãîòîâû ê òîìó, ÷òîáû ïðèâåñòè äîêàçàòåëüñòâî òåîðåìû î ÷àñòè÷íîéðåêóðñèâíîñòè ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà.Ëþáàÿ ôóíêöèÿ, âû÷èñëèìàÿ ïî Òüþðèíãó, ÿâëÿåòñÿ ÷àñòè÷íî ðåêóðñèâíîé.Äîêàçàòåëüñòâî. Ïóñòü f (x1, .
. . , xk ) ïðîèçâîëüíàÿ ÷àñòè÷íàÿ ôóíêöèÿ, âû÷èñÒåîðåìà 33.ëèìàÿ ïî Òüþðèíãó. Ñëåäîâàòåëüíî, ñóùåñòâóåò ìàøèíà T , êîòîðàÿ âû÷èñëÿåò f .Ïóñòü t êîä T , à x = hx1 , . . . , xk i ïðîèçâîëüíûå çíà÷åíèÿ àðãóìåíòîâ f .Åñëè f (x) îïðåäåëåíî, òî T ïåðåðàáàòûâàåò ñëîâî M = q1 01x1 0 . .
. 01xk 0 â ñëîâî0M = q0 01f (x) 00s äëÿ íåêîòîðîãî s > 0 áåç äîñòðàèâàíèÿ ÿ÷ååê ñëåâà. Ïóñòü ïðè ýòîìn ýòî êîëè÷åñòâî øàãîâ ðàáîòû ìàøèíû T , ïîñëå èñïîëíåíèÿ êîòîðûõ îíà âïåðâûå ïîïàäàåò â ñîñòîÿíèå q0 . Ñëåäîâàòåëüíî, n ÿâëÿåòñÿ ìèíèìàëüíûì ñ óñëîâèåì(n)MT = M 0 .  ñèëó ïðåäëîæåíèé 29, 30, 32, çàêëþ÷àåì, ÷òî run(t, ink (x), n) = bM 0 cè q(t, x, n) = 0. Òîãäà èç ìèíèìàëüíîñòè n ñëåäóåò ðàâåíñòâî n = µy[q(t, x, y) = 0].Îòñþäà, èñïîëüçóÿ ïðåäëîæåíèå 31, çàêëþ÷àåì, ÷òîf (x) = out(run(t, ink (x), n)) = out(run(t, ink (x), µy[q(t, x, y) = 0])).Åñëè æå f (x) íå îïðåäåëåíî, òî T , íà÷àâ ðàáîòó ñ âõîäíîãî ìàøèííîãî ñëîâà(y)M = q1 01x1 0 .
. . 01xk 0, íèêîãäà íå îñòàíîâèòñÿ, ò. å. q0 íå âõîäèò â MT äëÿ âñåõy ∈ ω . Ñëåäîâàòåëüíî, äëÿ ëþáîãî y ∈ ω èìååò ìåñòî q(t, x, y) 6= 0, îòêóäà ñëåäóåò,÷òî çíà÷åíèå µy[q(t, x, y) = 0] íå îïðåäåëåíî. Òàêèì îáðàçîì, îïÿòü âûïîëíÿåòñÿñîîòíîøåíèåf (x) = out(run(t, ink (x), µy[q(t, x, y) = 0])).Òàê êàê ôóíêöèÿ q(t, x, y) ïðèìèòèâíî ðåêóðñèâíà, òî µy[q(t, x, y) = 0] ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ. Ïîñêîëüêó ink (x), run(t, w, y), out(w) ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè, òî ôóíêöèÿ f (x) = out(run(t, ink (x), µy[q(t, x, y) = 0])) ÷àñòè÷íîðåêóðñèâíà.Èç òåîðåìû 33 ìîæíî âûâåñòè íåñêîëüêî âàæíûõ ñëåäñòâèé.
Ñëåäóþùèå òðè ðåçóëüòàòà ìîæíî ñ÷èòàòü äîñòàòî÷íûì îïðàâäàíèåì òðóäî¼ìêîé ðàáîòû, ïðîäåëàííîéâ ïðåäûäóùèõ ïàðàãðàôàõ.×àñòè÷íàÿ ôóíêöèÿ âû÷èñëèìà ïî Òüþðèíãó òîãäà è òîëüêî òîãäà,êîãäà îíà ÿâëÿåòñÿ ÷àñòè÷íî ðåêóðñèâíîé.Äîêàçàòåëüñòâî. Ñëåäóåò èç òåîðåìû 16 è òåîðåìû 33.Ëþáàÿ ÷.ð.ô. ìîæåò áûòü ïîëó÷åíà èç ïðîñòåéøèõ ôóíêöèé ñïîìîùüþ êîíå÷íîé ïîñëåäîâàòåëüíîñòè ïðèìåíåíèé îïåðàòîðîâ S , R èëè M , â êîòîðîé îáùåå ÷èñëî ïðèìåíåíèé îïåðàòîðà M íå ïðåâîñõîäèò 1.Äîêàçàòåëüñòâî.
Åñëè f (x) ï.ð.ô., òî ïî îïðåäåëåíèþ f (x) ìîæåò áûòü ïîëó÷åÑëåäñòâèå 34.Ñëåäñòâèå 35.íà èç ïðîñòåéøèõ ôóíêöèé ñ ïîìîùüþ êîíå÷íîé ïîñëåäîâàòåëüíîñòè ïðèìåíåíèéîïåðàòîðîâ S è R, áåç èñïîëüçîâàíèÿ îïåðàòîðà M .Åñëè f (x) ÷.ð.ô., òî èç äîêàçàòåëüñòâà òåîðåìû 33 ñëåäóåò, ÷òîf (x) = out(run(t, ink (x), µy[q(t, x, y) = 0])),(∗)56Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèãäå t êîä ìàøèíû Òüþðèíãà, âû÷èñëÿþùåé f (x).Ôóíêöèè q(t, x, y), ink (x), run(t, w, y), out(w) ïðèìèòèâíî ðåêóðñèâíû è, ñëåäîâàòåëüíî, ìîãóò áûòü ïîëó÷åíû èç ïðîñòåéøèõ ôóíêöèé òîëüêî c ïîìîùüþ îïåðàòîðîâS è R.
Òàêèì îáðàçîì, äîêàçûâàåìîå óòâåðæäåíèå âûòåêàåò èç òîæäåñòâà (∗).Ïóñòü k ∈ ω , K íåêîòîðîå ñåìåéñòâî k -ìåñòíûõ ÷àñòè÷íûõ ôóíêöèé. (k+1)-ìåñòíàÿ ÷àñòè÷íàÿ ôóíêöèÿ F (x0 , x1 , . . . , xk ) íàçûâàåòñÿK , åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ:1) äëÿ ëþáîãî n ∈ ω ñóùåñòâóåò f ∈ K òàêàÿ, ÷òî F (n, x1 , .
. . , xk ) = f (x1 , . . . , xk );2) äëÿ ëþáîé f ∈ K ñóùåñòâóåò n ∈ ω òàêîå, ÷òî F (n, x1 , . . . , xk ) = f (x1 , . . . , xk ).Äðóãèìè ñëîâàìè, K ñîâïàäàåò ñ ìíîæåñòâîì ôóíêöèé {F (0, x), F (1, x), F (2, x), . . .}.Îïðåäåëåíèå.óíèâåðñàëüíîéäëÿ ñåìåéñòâà(îá óíèâåðñàëüíîé ÷.ð.ô.) Ñóùåñòâóåò (k+1)-ìåñòíàÿ ÷.ð.ô. F (x0 , x1 ,, óíèâåðñàëüíàÿ äëÿ ñåìåéñòâà âñåõ k-ìåñòíûõ ÷.ð.ô.Äîêàçàòåëüñòâî.  êà÷åñòâå F âîçüì¼ì (k+1)-ìåñòíóþ ÷àñòè÷íóþ ôóíêöèþÒåîðåìà 36..
. . , xk )F (x0 , x1 , . . . , xk ) = out(run(x0 , ink (x1 . . . , xk ), µy[q(x0 , x1 , . . . , xk , y) = 0])).Èç ïðåäëîæåíèé 2932 ñëåäóåò, ÷òî F (x0 , x1 , . . . , xk ) ÷.ð.ô.ßñíî, ÷òî ôèêñèðóÿ çíà÷åíèå àðãóìåíòà x0 â F (x0 , x1 , . . . , xk ), ìû ïîëó÷èì íåêîòîðóþ k -ìåñòíóþ ÷.ð.ô. Åñëè æå f (x1 , . . . , xk ) ïðîèçâîëüíàÿ k -ìåñòíàÿ ÷.ð.ô., òîâçÿâ â êà÷åñòâå t êîä âû÷èñëÿþùåé å¼ ìàøèíû Òüþðèíãà, ïî òåîðåìå 33 ïîëó÷èì,÷òî f (x1 , . . . , xk ) = F (t, x1 , . . . , xk ).Òàêèì îáðàçîì, F óíèâåðñàëüíàÿ äëÿ âñåõ k -ìåñòíûõ ÷.ð.ô.Èç òåîðåìû îá óíèâåðñàëüíîé ÷.ð.ô.
ñëåäóåò, ÷òî ñóùåñòâóåò óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà Tuniv , êîòîðàÿ â îïðåäåë¼ííîì ñìûñëå ñïîñîáíà çàìåíèòü áåñêîíå÷íîåñåìåéñòâî âñåõ ìàøèí Òüþðèíãà. Ðàáîòó Tuniv ìîæíî îïèñàòü ñëåäóþùèì îáðàçîì(ñì. ðèñóíîê): íà âõîä óíèâåðñàëüíîé ìàøèíû ïîäà¼òñÿ êîðòåæ äàííûõ (e, x); óíèâåðñàëüíàÿ ìàøèíà ïî êîäó e êîíñòðóèðóåò ïðîãðàììó ìàøèíû Te , ñîîòâåòñòâóþùóþýòîìó êîäó, è çàïóñêàåò å¼ íà âõîäíûõ äàííûõ x; ðåçóëüòàò f (x) ðàáîòû ìàøèíûTe âûäà¼òñÿ íà âûõîä Tuniv è ÿâëÿåòñÿ îêîí÷àòåëüíûì ðåçóëüòàòîì å¼ ðàáîòû, ò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
