1610906281-974acaa5ee9a7bc9236c4fe86efeeea8 (824379), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

. . , xn i, y)).Îòñþäà ñëåäóåò, ÷òî âñÿêàÿ âû÷èñëèìàÿ íà ÌÌ ôóíêöèÿ ÿâëÿåòñÿ ÷.ð.ô.Òåîðåìà äîêàçàíà.Òàêèì îáðàçîì, êëàññû ÷.ð.ô. è ôóíêöèé, âû÷èñëèìûõ íà ÌÌ, ñîâïàäàþò.Ïðîñìàòðèâàÿ äîêàçàòåëüñòâî òåîðåìû, ñ ó÷¼òîì ýòîãî ìû ïîëó÷àåìñëåäóþùóþ òåîðåìó:Òåîðåìà 1.0.9 (Òåîðåìà Êëèíè î íîðìàëüíîé ôîðìå) Ñóùåñòâóþòïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ U (y) è ïðèìèòèâíî ðåêóðñèâíîå îòíîøåíèå T (m, x, y) òàêèå, ÷òî äëÿ ëþáîãî n ∈ N è ëþáîé ÷.ð.ô. f (x1 , .

. . , xn )íàéä¼òñÿ m ∈ N òàêîå, ÷òîf (x1 , . . . , xn ) ' U (µyT (m, hx1 , . . . , xn i, y)).(1.1)Òåîðåìà 1.0.10 (Òåîðåìà îá óíèâåðñàëüíîé ôóíêöèè) Äëÿ ëþáî-ãî n ∈ N ñóùåñòâóåò n + 1ìåñòíàÿ ÷.ð.ô. ψ(m, x1 , . . . , xn ) òàêàÿ, ÷òîäëÿ ëþáîé ÷.ð.ô. f (x1 , . . . , xn ) íàéä¼òñÿ m ∈ N òàêîå, ÷òîf (x1 , . .

. , xn ) ' ψ(m, x1 , . . . , xn ).Äîêàçàòåëüñòâî.  êà÷åñòâå ψ(m, x1 , . . . , xn ) ãîäèòñÿ, íàïðèìåð, ôóíêöèÿ U (µyT (m, hx1 , . . . , xn i, y)).Òàêèì îáðàçîì, âñå ÷.ð.ô. ñ ôèêñèðîâàííûì ÷èñëîì àðãóìåíòîâ ìîæíî ¾ñîáðàòü¿ â îäíó åäèíñòâåííóþ ôóíêöèþ ñ ÷èñëîì àðãóìåíòîâ íà 1áîëüøå è ïîëó÷àòü èç îäíîé ýòîé ôóíêöèè âñå ôóíêöèè, ïðîñòî ôèêñèðóÿ ïåðâûé àðãóìåíò. Ïðè ýòîì åñòåñòâåííî äåðæàòü â óìå àíàëîãèþ,ñîãëàñíî êîòîðîé ýòà ôóíêöèÿ ÿâëÿåòñÿ óíèâåðñàëüíûì âû÷èñëèòåëüíûì óñòðîéñòâîì, â ïåðâûé àðãóìåíò ïðîãðàììîé; èçìåíÿÿ ïðîãðàììó, ìîæíî âû÷èñëÿòü ëþáóþ ôóíêöèþ.Åñëè m íîìåð ïðîãðàììû P , òî ïîëîæèì{m}(x1 , . . . , xn ) ' AnP (x1 , . . . , xn ),14Ãëàâà 1.Ìèíèìàøèíûåñëè æå m íå ÿâëÿåòñÿ íîìåðîì íèêàêîé ïðîãðàììû, òî {m}(x1 , .

. . , xn )ñ÷èòàåì íåîïðåäåë¼ííûì.  ëþáîì ñëó÷àå, ïî äàííîìó m ìîæíî âû÷èñëèòü çíà÷åíèå {m}(x1 , . . . , xn ) ñëåäóþùèì îáðàçîì: ïåðåáèðàåì ïî ïîðÿäêó íàòóðàëüíûå ÷èñëà y = 0, 1, . . . äî òåõ ïîð, ïîêà íå âûïîëíèòñÿT (m, hx1 , . . . , xn i, y), è ïîñëå ýòîãî íàõîäèì ðåçóëüòàò â âèäå U (y).

Åñëèm íå êîä êàêîéëèáî ÌÌ, òî ýòî òîæå âûïîëíåíî: â ýòîì ñëó÷àå îáàçíà÷åíèÿ {m}(x1 , . . . , xn ) è T (m, hx1 , . . . , xn i, y) íå îïðåäåëåíû. Çíà÷èò,èìååò ìåñòî ðàâåíñòâî{m}(x1 , . . . , xn ) ' U (µyT (m, hx1 , . . . , xn i, y)) .Íàðÿäó ñ ïðèâåä¼ííûìè âûøå òåîðåìàìè, ñëåäóþùàÿ òåîðåìà òàêæåÿâëÿåòñÿ îäíèì èç âàæíåéøèõ ðåçóëüòàòîâ î âû÷èñëèìîñòè.Òåîðåìà 1.0.11 (Òåîðåìà î ïàðàìåòðèçàöèè (smnòåîðåìà)) Äëÿëþáîé âû÷èñëèìîé ôóíêöèè F (y1 , .

. . , ym , x1 , . . . , xn ) ñóùåñòâóåò ðàçíîçíà÷íàÿ ïðèìèòèâíî ðåêóðñèâíàÿ ôóíêöèÿ s(y1 , . . . , ym ) òàêàÿ, ÷òî äëÿ ëþáûõ y1 , . . . , ym âûïîëíåíî {s(y1 , . . . , ym )}(x1 , . . . , xn ) ' F (y1 , . . . , ym , x1 , . . . , xn ).Äîêàçàòåëüñòâî. ÔóíêöèÿF 0 (x1 , . . . , xn , y1 , . . . , ym ) ' F (y1 , .

. . , ym , x1 , . . . , xn )òàêæå âû÷èñëèìà, è îíà âû÷èñëÿåòñÿ íà ÌÌ íåêîòîðîé ïðîãðàììîé P .Çàôèêñèðîâàâ ïðîèçâîëüíûå y1 , . . . , ym , ìîæíî ïîñòðîèòü ïðîãðàììó äëÿâû÷èñëåíèÿ ôóíêöèè F 0 (x1 , . . . , xn , y1 , . . . , ym ) îò îñòàâøèõñÿ ïåðåìåííûõx1 , . . . , xn ñëåäóþùèì îáðàçîì: ñíà÷àëà èäóò îïåðàòîðû0:1:Rn+1 :=y1Rn+2 :=y2...m-1:Rn+m := ym ,ïîñëå ýòîãî çàïèøåì ïîñëåäîâàòåëüíîñòü êîìàíä P 0 , êîòîðàÿ ïîëó÷àåòñÿ èç ïîñëåäîâàòåëüíîñòè êîìàíä ïðîãðàììû P çàìåíîé âñåõ êîìàíäif ...

goto k íà êîìàíäû if ... goto k+m è êîìàíä goto k íà êîìàíäû goto k+m è â ïîëó÷èâøåìñÿ ñïèñêå êîìàíä ðàññòàâèì íîìåðà ïî ïîðÿäêó, íà÷èíàÿ ñ 0. Íåòðóäíî óáåäèòüñÿ, ÷òî ïðè ëþáûõ y1 , . . . , ym , ïîëó÷åííàÿ òàêèì ñïîñîáîì ïðîãðàììà âû÷èñëèò íàì çíà÷åíèå F 0 (x1 , . . . , xn , y1 , . . . , ym ).15Ïóñòü P 0 ïîñëåäîâàòåëüíîñòü êîìàíä c0 , . . . , cl (áåç íîìåðîâ ñëåâà). Òîãäà ñ ó÷¼òîì îïðåäåëåíèÿ êîäîâ ïîñëåäîâàòåëüíîñòåé, ìû ïîëó÷àåì, ÷òîêîä ïîëó÷èâøåéñÿ â ðåçóëüòàòå ïðîãðàììû áóäåò ðàâåíγ(c )+10 )+1·. . .·pm+llhh0, 2(n + 1), y1 i , h0, 2(n + 2), y2 i , .

. . , h0, 2(n + m), ym ii·pγ(cmÏîñëåäíåå âûðàæåíèå äà¼ò íàì ï.ð. ô. s(y1 , . . . , ym ) ñî ñâîéñòâîìF (x̄, ȳ) ' F 0 (ȳ, x̄) ' {s(ȳ)}(x̄).Ôóíêöèÿ s ðàçíîçíà÷íà, ò.ê. ïî çíà÷åíèþ s(y1 , . . . , ym ) ìîæíî ëåãêî âîññòàíîâèòü èñõîäíûå àðãóìåíòû y1 , . . . , ym , íàïðèìåð, y1 = ((s(y1 , . . . , ym ))0 )2 ,y2 = ((s(y1 , . . . , ym ))1 )2 , y3 = ((s(y1 , . . . , ym ))2 )2 , .

. . Îòñþäà ñëåäóåò, ÷òî sîáëàäàåò òðåáóåìûìè ñâîéñòâàìè. .

Характеристики

Список файлов лекций