1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 14
Текст из файла (страница 14)
å.F (e, x) = f (x).(e, x)âõîä -Tunivxâûõîä-F (e, x)6f (x)?T0Îïðåäåëåíèå.T1...Te...Tn...Ïóñòü k ∈ ω . Äëÿ êàæäîãî e ∈ ω ââåä¼ì îáîçíà÷åíèåϕke (x1 , . . . , xk ) = out(run(e, ink (x1 . . . , xk ), µy[q(e, x1 , . . . , xk , y) = 0])).-ìåñòíîé ÷àñòè÷íî âû÷èñëèìîé ôóíêöèåéÔóíêöèþ ϕke (x1 , . . . , xk ) áóäåì íàçûâàòü ke.  ñëó÷àå îäíîìåñòíûõ ôóíêöèé áóäåì ïðîñòî ïèñàòü ϕe (x)áåç âåðõíåãî èíäåêñà.ñ êëèíèåâñêèì íîìåðîì 16. Óíèâåðñàëüíûå ôóíêöèè57Åñëè e êîä ìàøèíû Òüþðèíãà, êîòîðàÿ âû÷èñëÿåò ôóíêöèþ f , òîe òàêæå áóäåò êëèíèåâñêèì íîìåðîì ýòîé ôóíêöèè.
Íî îáðàòíîå, âîîáùå ãîâîðÿ,íåâåðíî! Íå ëþáîé êëèíèåâñêèé íîìåð ôóíêöèè ÿâëÿåòñÿ êîäîì ìàøèíû Òüþðèíãà,âû÷èñëÿþùåé ýòó ôóíêöèþ. Ñì. çàìå÷àíèå ïîñëå ïðåäëîæåíèÿ 28.Çàìå÷àíèå.Ñóùåñòâóþò ÷àñòè÷íûå ôóíêöèè, íå ÿâëÿþùèåñÿ ÷àñòè÷íî ðåêóðñèâíûìè.Äîêàçàòåëüñòâî. Ðàññìîòðèì ñåìåéñòâî {ϕ0(x), ϕ1(x), ϕ2(x), . .
.}.  ñèëó òåîðåìû îáÑëåäñòâèå 37.óíèâåðñàëüíîé ÷.ð.ô. îíî ñîâïàäàåò ñ ñåìåéñòâîì âñåõ îäíîìåñòíûõ ÷.ð.ô. Ââåä¼ìñëåäóþùóþ âñþäó îïðåäåë¼ííóþ îäíîìåñòíóþ ôóíêöèþ(ϕx (x) + 1, åñëè ϕx (x) îïðåäåëåíî,f (x) =0,èíà÷å.Äîïóñòèì, f ÷.ð.ô. Òîãäà íàéä¼òñÿ e ∈ ω òàêîå, ÷òî f = ϕe . Ñëåäîâàòåëüíî, ϕe òîæåâñþäó îïðåäåëåíà.  ÷àñòíîñòè, çíà÷åíèå ϕe (e) îïðåäåëåíî. Íî òîãäà ϕe (e) = f (e) =ϕe (e) + 1. Ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî, f íå ÿâëÿåòñÿ ÷àñòè÷íî ðåêóðñèâíîé. 16.Óíèâåðñàëüíûå ôóíêöèèÌû óæå óáåäèëèñü â òîì, ÷òî äëÿ ñåìåéñòâà âñåõ k -ìåñòíûõ ÷.ð.ô.
ñóùåñòâóåò óíèâåðñàëüíàÿ (k+1)-ìåñòíàÿ ôóíêöèÿ, êîòîðàÿ ñàìà ÿâëÿåòñÿ ÷.ð.ô. Îäíàêî äëÿ ñåìåéñòâà âñåõ k -ìåñòíûõ ï.ð.ô. è äëÿ ñåìåéñòâà âñåõ k -ìåñòíûõ ð.ô. àíàëîãè÷íîåñâîéñòâî íå èìååò ìåñòà.Ïóñòü k > 1. Íå ñóùåñòâóåò (k+1)-ìåñòíîé ï.ð.ô., óíèâåðñàëüíîé äëÿ ñåìåéñòâà âñåõ k-ìåñòíûõ ï.ð.ô.Äîêàçàòåëüñòâî. Äîïóñòèì, íàïðîòèâ, F (x0, x1, . . . , xk ) ï.ð.ô., óíèâåðñàëüíàÿ äëÿÏðåäëîæåíèå 38.ñåìåéñòâà âñåõ k -ìåñòíûõ ï.ð.ô., ò. å.
{F (0, x1 , . . . , xk ), F (1, x1 , . . . , xk ), . . .} êëàññâñåõ k -ìåñòíûõ ï.ð.ô. Îïðåäåëèì k -ìåñòíóþ ôóíêöèþ:f (x1 , . . . , xk ) = F (x1 , x1 , x2 , . . . , xk ) + 1.Òîãäà f (x1 , . . . , xk ) ï.ð.ô. Ñëåäîâàòåëüíî, â ñèëó óíèâåðñàëüíîñòè F íàéä¼òñÿ n ∈ω òàêîé, ÷òî äëÿ âñåõ x1 , . . . , xk ∈ ω âûïîëíÿåòñÿ F (n, x1 , . . . , xk ) = f (x1 , . . .
, xk ).Ðàññìîòðèì çíà÷åíèÿ x1 = n, x2 = . . . = xk = 0. Òîãäà ïîëó÷àåì:F (n, n, 0, . . . , 0) = f (n, 0, . . . , 0) = F (n, n, 0, . . . , 0) + 1.Ïðîòèâîðå÷èå.Ïóñòü k > 1. Íå ñóùåñòâóåò (k+1)-ìåñòíîé ð.ô., óíèâåðñàëüíîé äëÿ ñåìåéñòâà âñåõ k-ìåñòíûõ ð.ô.Äîêàçàòåëüñòâî. Ïîâòîðÿåò äîêàçàòåëüñòâî ïðåäëîæåíèÿ 38.Ïðåäëîæåíèå 39.Óñëîâèå k > 1 â ôîðìóëèðîâêàõ ïðåäëîæåíèé 38 è 39 ïðèñóòñòâóåòíå ñëó÷àéíî. Äëÿ ñåìåéñòâà âñåõ 0-ìåñòíûõ ï.ð.ô. (êîòîðîå ñîâïàäàåò ñ ñåìåéñòâîìâñåõ 0-ìåñòíûõ ð.ô.) ñóùåñòâóåò óíèâåðñàëüíàÿ ï.ð.ô. ýòî, î÷åâèäíî, 1-ìåñòíàÿôóíêöèÿ F (x) = x.Çàìå÷àíèå.58Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÄèàãîíàëüíûé ìåòîä äîêàçàòåëüñòâà ïðåäëîæåíèÿ 38 ñóùåñòâåííî îïèðàåòñÿ íàïðåäïîëîæåíèå î ïðèìèòèâíîé ðåêóðñèâíîñòè ôóíêöèè F (x0 , x1 , .
. . , xk ). Åñëè ýòîïðåäïîëîæåíèå îñëàáèòü è ñ÷èòàòü, ÷òî F (x0 , x1 , . . . , xk ) ðåêóðñèâíàÿ, òî äèàãîíàëüíûå ðàññóæäåíèÿ óæå íè ê ÷åìó íå ïðèâîäÿò, ò. å. íå äîêàçûâàþò îòñóòñòâèÿð.ô., óíèâåðñàëüíîé äëÿ ñåìåéñòâà âñåõ ï.ð.ô. Áîëåå òîãî, ñïðàâåäëèâî ñëåäóþùååóòâåðæäåíèå, êîòîðîå ìû ïðèâîäèì áåç äîêàçàòåëüñòâà.Ñóùåñòâóåò (k+1)-ìåñòíàÿ ð.ô., óíèâåðñàëüíàÿ äëÿ ñåìåéñòâàâñåõ k-ìåñòíûõ ï.ð.ô.Ïðåäëîæåíèå 40.Ïîëíîå äîêàçàòåëüñòâî ïðåäëîæåíèÿ 40 èçëîæåíî â [7].  îñíîâå ýòîãî äîêàçàòåëüñòâà ëåæàò òåîðåìà Ðîáèíñîíà î√òîì, ÷òî âñå 1-ìåñòíûå ï.ð.ô. ìîæíî ïîëó÷èòü2èç ôóíêöèé s(x) = x+1 è q(x) = x−[ x] îïåðàöèÿìè ñëîæåíèÿ, ñóïåðïîçèöèè è èòåðèðîâàíèÿ ôóíêöèé, è òåîðåìà î ðåêóðñèâíîñòè ôóíêöèé, ïîëó÷åííûõ èç íåêîòîðûõï.ð.ô. ñ ïîìîùüþ ðåêóðñèè 2-é ñòóïåíè.Èç ïðåäëîæåíèÿ 40 âûòåêàåò âàæíîå ñëåäñòâèå, óòâåðæäàþùåå, ÷òî êëàññ âñåõï.ð.ô.
íå ñîâïàäàåò ñ êëàññîì âñåõ ð.ô. Íàïîìíèì, ÷òî ñïðàâåäëèâû ñëåäóþùèåòåîðåòèêî-ìíîæåñòâåííûå âêëþ÷åíèÿ:ÏÐÔ ⊆ ÐÔ ⊆ ×ÐÔ.Êàæäîå èç ýòèõ âêëþ÷åíèé ñòðîãîå. Âòîðîå âêëþ÷åíèå ÿâëÿåòñÿ ñòðîãèì, ïîñêîëüêó, î÷åâèäíî, ñóùåñòâóþò íå âñþäó îïðåäåë¼ííûå ÷.ð.ô. Íàïðèìåð, íèãäå íå îïðåäåë¼ííàÿ ôóíêöèÿ f = µx[s(x) = 0] ÿâëÿåòñÿ ÷.ð.ô.
Äîêàæåì, ÷òî ïåðâîå âêëþ÷åíèåÿâëÿåòñÿ ñòðîãèì.Ñóùåñòâóåò ðåêóðñèâíàÿ ôóíêöèÿ, íå ÿâëÿþùàÿñÿ ïðèìèòèâíîðåêóðñèâíîé.Äîêàçàòåëüñòâî. Ïóñòü F (x, y) ð.ô., óíèâåðñàëüíàÿ äëÿ ñåìåéñòâà âñåõ 1-ìåñòíûõÑëåäñòâèå 41.ï.ð.ô., êîòîðàÿ ñóùåñòâóåò â ñèëó ïðåäëîæåíèÿ 40. Åñëè áû F (x, y) áûëà ïðèìèòèâíîðåêóðñèâíîé, òî îíà áûëà áû ï.ð.ô., óíèâåðñàëüíîé äëÿ ñåìåéñòâà âñåõ 1-ìåñòíûõï.ð.ô., ÷òî íåâîçìîæíî â ñèëó ïðåäëîæåíèÿ 38.Ñóùåñòâóåò äðóãîé èçâåñòíûé ïðèìåð ðåêóðñèâíîé ôóíêöèè, êîòîðàÿ íå ÿâëÿåòñÿïðèìèòèâíî ðåêóðñèâíîé, ýòî òàê íàçûâàåìàÿ. Îïðåäåëåíèåè ñâîéñòâà ôóíêöèè Àêêåðìàíà ìîæíî íàéòè â [7].ôóíêöèÿ ÀêêåðìàíàÂîïðîñ î ñóùåñòâîâàíèè óíèâåðñàëüíîé ôóíêöèè ìîæíî èññëåäîâàòü íåòîëüêî äëÿ ñåìåéñòâ âñåõ k -ìåñòíûõ ÷.ð.ô., ð.ô.
èëè ï.ð.ô. Äîêàæåì, ÷òî ñóùåñòâóåò2-ìåñòíàÿ ï.ð.ô., óíèâåðñàëüíàÿ äëÿ ñåìåéñòâà âñåõ ïîëèíîìîâ îò îäíîé ïåðåìåííîéñ íàòóðàëüíûìè êîýôôèöèåíòàìè.Åñëè f (x) = an xn +an−1 xn−1 +. . .+a1 x+a0 ïîëèíîì, ai ∈ ω , n ∈ ω , òî ñîïîñòàâèìåìó êîä(f ) = pa00 +1 · pa11 +1 · . . . · pnan +1 , ãäå p0 = 2, p1 = 3, p2 = 5, . . . ïåðå÷èñëåíèåïðîñòûõ ÷èñåë â ïîðÿäêå âîçðàñòàíèÿ.Çàìåòèì, ÷òî åñëè k = êîä(f ), òî ñòåïåíü ïîëèíîìà f íàõîäèòñÿ ñ ïîìîùüþ ôóíêöèè long(k), à i-é êîýôôèöèåíò f íàõîäèòñÿ ñ ïîìîùüþ ôóíêöèè ex(i, k)−1.Îïðåäåëèì äâóõìåñòíóþ ïðèìèòèâíî ðåêóðñèâíóþ ôóíêöèþÏðèìåð.long(y)F (y, x) =Xi=0(ex(i, y)−1) · xi .59 16. Óíèâåðñàëüíûå ôóíêöèèÒîãäà, ñ îäíîé ñòîðîíû, åñëè ó ôóíêöèè F (y, x) çàôèêñèðîâàòü çíà÷åíèå y , òîïîëó÷èòñÿ íåêîòîðûé ïîëèíîì îò ïåðåìåííîé x ñ íàòóðàëüíûìè êîýôôèöèåíòàìè.Ñ äðóãîé ñòîðîíû, åñëè f ïðîèçâîëüíûé ïîëèíîì, òî F (êîä(f ), x) = f (x).
Òàêèìîáðàçîì, F èñêîìàÿ óíèâåðñàëüíàÿ ôóíêöèÿ. çàêëþ÷åíèè ïàðàãðàôà ïðèâåä¼ì ñâîäíóþ òàáëèöó ðåçóëüòàòîâ î ñóùåñòâîâàíèè óíèâåðñàëüíûõ ôóíêöèé äëÿ êëàññîâ âñåõ k -ìåñòíûõ ï.ð.ô., âñåõ k -ìåñòíûõ ð.ô.è âñåõ k -ìåñòíûõ ÷.ð.ô (k > 1).êëàññ âñåõk -ìåñòíûõï.ð.ô.êëàññ âñåõk -ìåñòíûõð.ô.êëàññ âñåõk -ìåñòíûõ÷.ð.ô.óíèâåðñàëüíàÿï.ð.ô.óíèâåðñàëüíàÿð.ô.óíèâåðñàëüíàÿ÷.ð.ô.−++−−−−−+Äëÿ êëàññà âñåõ k -ìåñòíûõ ï.ð.ô.
íå ñóùåñòâóåò (k+1)-ìåñòíîé óíèâåðñàëüíîéï.ð.ô. â ñèëó ïðåäëîæåíèÿ 38.Äëÿ êëàññà âñåõ k -ìåñòíûõ ï.ð.ô. ñóùåñòâóþò (k+1)-ìåñòíûå óíèâåðñàëüíûå ð.ô.è ÷.ð.ô. â ñèëó ïðåäëîæåíèÿ 40.Äëÿ êëàññà âñåõ k -ìåñòíûõ ð.ô. íå ñóùåñòâóåò (k+1)-ìåñòíûõ óíèâåðñàëüíûõï.ð.ô. è ð.ô. â ñèëó ïðåäëîæåíèÿ 39.Äëÿ êëàññà âñåõ k -ìåñòíûõ ð.ô. íå ñóùåñòâóåò (k+1)-ìåñòíîé óíèâåðñàëüíîé÷.ð.ô., òàê êàê â ïðîòèâíîì ñëó÷àå óíèâåðñàëüíàÿ ÷.ð.ô. äëÿ äàííîãî êëàññà áûëà áû âñþäó îïðåäåë¼ííîé.Äëÿ êëàññà âñåõ k -ìåñòíûõ ÷.ð.ô. íå ñóùåñòâóåò (k+1)-ìåñòíûõ óíèâåðñàëüíûõï.ð.ô.
è ð.ô., ïîñêîëüêó â äàííîì êëàññå åñòü íå âñþäó îïðåäåë¼ííûå ôóíêöèè.Äëÿ êëàññà âñåõ k -ìåñòíûõ ÷.ð.ô. ñóùåñòâóåò (k+1)-ìåñòíàÿ óíèâåðñàëüíàÿ ÷.ð.ô.â ñèëó òåîðåìû 36.Ãëàâà IVÒåîðèÿ âû÷èñëèìîñòèââåäåíèåìÄàííàÿ ãëàâà ÿâëÿåòñÿâ òåîðèþ âû÷èñëèìîñòè è ñîäåðæèò ôóíäàìåíòàëüíûå ïîíÿòèÿ è òåîðåìû èç íåñêîëüêèõ, ñòàâøèõ óæå êëàññè÷åñêèìè, ðàçäåëîâýòîé òåîðèè.
Äëÿ äàëüíåéøåãî å¼ èçó÷åíèÿ ìîæíî ïîðåêîìåíäîâàòü êíèãè [1], [7],[10], [11].Îñíîâíîé ðåçóëüòàò ïðåäûäóùåé ãëàâû ïîçâîëÿåò íàì ââåñòè ñëåäóþùåå÷àñòè÷íî âû÷èñëèìîé (÷.â.ô.),×àñòè÷íàÿ ôóíêöèÿ f íàçûâàåòñÿåñëè îíà óäîâëåòâîðÿåò ëþáîìó èç ñëåäóþùèõ äâóõ óñëîâèé:(1) f ÿâëÿåòñÿ ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèåé;(2) f âû÷èñëèìà ïî Òüþðèíãó.Âñþäó îïðåäåë¼ííóþ ÷àñòè÷íî âû÷èñëèìóþ ôóíêöèþ áóäåì íàçûâàòü.Îïðåäåëåíèå.ôóíêöèåé (â.ô.)âû÷èñëèìîé÷.â.ô.Äàëåå ìû áóäåì èñïîëüçîâàòü òåðìèí, ïîñêîëüêó äëÿ íàñ òåïåðü íå èìååò çíà÷åíèÿ, êàêàÿ èç ôîðìàëèçàöèé ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè èñïîëüçóåòñÿ âðàññóæäåíèÿõ. òåîðèè âû÷èñëèìîñòè âàæíóþ ðîëü èãðàåò ââåä¼ííàÿ â ïðåäûäóùåé ãëàâå êëèíèåâñêàÿ íóìåðàöèÿ ϕke äëÿ êëàññà âñåõ k -ìåñòíûõ ÷àñòè÷íî âû÷èñëèìûõ ôóíêöèé.Íàïîìíèì, ÷òî å¼ îïðåäåëåíèå çàäà¼òñÿ òîæäåñòâîìϕke (x1 , .
. . , xk ) = out(run(e, ink (x1 . . . , xk ), µy[q(e, x1 , . . . , xk , y) = 0])),ïðàâàÿ ÷àñòü êîòîðîãî ÿâëÿåòñÿ (k+1)-ìåñòíîé ÷.â.ô., óíèâåðñàëüíîé äëÿ ñåìåéñòâàâñåõ k -ìåñòíûõ ÷.â.ô. 17.Òåîðåìà î ïàðàìåòðèçàöèè äàííîì ïàðàãðàôå ìû äîêàæåì ôóíäàìåíòàëüíóþ òåîðåìó òåîðèè âû÷èñëèìîñòè òåîðåìó î ïàðàìåòðèçàöèè. Èíòóèòèâíûé ñìûñë äàííîé òåîðåìû ñîñòîèò â ñëåäóþùåì. Åñëè çàäàíà íåêîòîðàÿ ÷.â.ô. f (y, x), ïåðåìåííûå êîòîðîé óñëîâíî ðàçäåëåíûíà äâå ãðóïïû, òî ê âû÷èñëåíèþ ýòîé ôóíêöèè ìîæíî ïîäîéòè äâóìÿ ñïîñîáàìè.Ïåðâûé ñïîñîá ñòàíäàðòíûé: ìû öåëèêîì ïîäà¼ì íà âõîä ìàøèíû T , âû÷èñëÿþùåé f , âåñü íàáîð hy, xi è ïîëó÷àåì íà âûõîäå çíà÷åíèå f (y, x).Âòîðîé ñïîñîá: ìû ôèêñèðóåì çíà÷åíèÿ ïåðåìåííûõ y , ñ÷èòàÿ èõ ïàðàìåòðàìè,è ïðåîáðàçóåì ïðîãðàììó ìàøèíû T ñ ïîìîùüþ ñïåöèàëüíîãîâïðîãðàììó íîâîé ìàøèíû Ty , êîòîðàÿ óæå áóäåò âû÷èñëÿòü ôóíêöèþ f êàê ôóíêöèþîò îñòàâøèõñÿ ïåðåìåííûõ x.
Êîä ìàøèíû Ty çàâèñèò îò çíà÷åíèé y , íî îñíîâíîåñâîéñòâî çàêëþ÷àåòñÿ â òîì, ÷òî ýòîò êîä ìîæåò áûòü âû÷èñëåí ïî y ñ ïîìîùüþíåêîòîðîé â.ô. s(y). Ñòðîãî ãîâîðÿ, ïàðàìåòðèçàòîð ýòî è åñòü ôóíêöèÿ s, êîòîðàÿ,èñïîëüçóÿ çíà÷åíèÿ y , ïðåîáðàçóåò êîä e ìàøèíû T â êîä s(y) ìàøèíû Ty .ïàðàìåòðèçàòîðà61 17. Òåîðåìà î ïàðàìåòðèçàöèè' $T-f (y, x)6TyS&66(y, x)%yxÄëÿ äîêàçàòåëüñòâà òåîðåìû î ïàðàìåòðèçàöèè íàì ïîòðåáóåòñÿ ñëåäóþùàÿ òåõíè÷åñêàÿ ëåììà.Ñóùåñòâóåò äâóõìåñòíàÿ âû÷èñëèìàÿ ôóíêöèÿ x◦y, óäîâëåòâîðÿþùàÿóñëîâèþ: åñëè x = bT1c, y = bT2c, ãäå T1 è T2 íåêîòîðûå ìàøèíû Òüþðèíãà,èìåþùèå îäèí è òîò æå âíåøíèé àëôàâèò, òî x ◦ y = bT1 ◦ T2cÄîêàçàòåëüñòâî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
