С.С. Марченков - Избранные главы дискретной математики (1124120), страница 18
Текст из файла (страница 18)
Åñëè ìàøèíà M02 çàêàí÷èâàåò ðàáîòó, òîçàïóñêàåì ìàøèíó M03 íà òðåòüåé äîðîæêå, è ò.ä.Åñëè çíà÷åíèÿ âñåõ ôóíêöèé g1 , . . . , gm îïðåäåëåíû, òî â ðåçóëüòàòåîïèñàííîãî ïðîöåññà ìîäåëèðîâàíèÿ ìàøèí M01 , . . . , M0m íà m äîðîæêàõëåíòû áóäóò çàïèñàíû â îñíîâíîì êîäå çíà÷åíèÿg1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ).(4.8)Òåïåðü íåîáõîäèìî ¾âûðîâíÿòü¿ ýòè çàïèñè, ò.å. ðàñïîëîæèòü èõ íà ñîîòâåòñòâóþùèõ äîðîæêàõ òàê, ÷òîáû ïîñëåäîâàòåëüíîñòü çíà÷åíèé ôóíêöèé g1 , . .
. , gm âûãëÿäåëà êàê îñíîâíîé êîä íàáîðà (4.8). Çäåñü íàì âíîâüïîíàäîáÿòñÿ ñèìâîëû 2, êîòîðûå ìîãóò íàõîäèòüñÿ íà ëþáîé èç äîðîæåê.Îíè óïðîñòÿò ïðîöåññ ¾âûðàâíèâàíèÿ¿ çàïèñåé íà äîðîæêàõ, ïîçâîëÿÿîïðåäåëèòü ïîòåíöèàëüíûå ãðàíèöû ýòèõ çàïèñåé.Îñòàåòñÿ ñîâñåì íåìíîãî äëÿ çàâåðøåíèÿ âû÷èñëåíèÿ çíà÷åíèé ôóíêöèé g1 , . . .
, gm . Ñëåäóåò òîëüêî âûïîëíèòü îáðàòíûé ïåðåõîä èç àëôàâèòàB â àëôàâèò {0, 1}, ò.å. ñôîðìèðîâàòü íà ëåíòå îñíîâíîé êîä íàáîðà (4.8).Çàâåðøàþùèé ýòàï âû÷èñëåíèÿ çíà÷åíèÿ ôóíêöèè f ñîñòîèò â òîì, ÷òîê ïîëó÷åííîìó îñíîâíîìó êîäó íàáîðà (4.8) ïðèìåíÿåòñÿ ìàøèíà Òüþðèíãà M0 .Ïîäðîáíî îïèñàííûé àëãîðèòì âû÷èñëåíèÿ ôóíêöèè f íà ìàøèíåÒüþðèíãà ïîçâîëÿåò ïîñòðîèòü ýòó ìàøèíó Òüþðèíãà â âèäå êîìïîçèöèè áîëåå ïðîñòûõ ìàøèí Òüþðèíãà, âêëþ÷àþùèõ, â ÷àñòíîñòè, ìàøèíûM0 , M01 , .
. . , M0m .Ïåðåéäåì ê îïåðàöèè ïðèìèòèâíîé ðåêóðñèè. Ïóñòü ôóíêöèè g èh ïðàâèëüíî âû÷èñëèìû íà ìàøèíàõ Òüþðèíãà M0 , M1 , à ôóíêöèÿf (x1 , . . . , xn ) ïîëó÷àåòñÿ èç ôóíêöèé g, h ñ ïîìîùüþ îïåðàöèè ïðèìèòèâíîé ðåêóðñèè (4.5). Êàê è â ñëó÷àå îïåðàöèè ñóïåðïîçèöèè, ââåäåì â ëåíòî÷íûé àëôàâèò ìàøèí M0 , M1 ñèìâîë 2, ÷òîáû îòìå÷àòü ïóñòûå êëåò82êè, â êîòîðûõ â ïðîöåññå âû÷èñëåíèÿ ïîáûâàëè ãîëîâêè ìàøèí M0 , M1 .Ñîîòâåòñòâóþùèì îáðàçîì ìîäèôèöèðîâàííûå ìàøèíû Òüþðèíãà îáîçíà÷èì ÷åðåç M00 è M01 .Äëÿ âû÷èñëåíèÿ ôóíêöèè f íàì ïîíàäîáÿòñÿ òðè äîðîæêè íà ëåíòå.Íà ïåðâîé äîðîæêå áóäåò ïîñòîÿííî íàõîäèòüñÿ èñõîäíûé íàáîð çíà÷åíèé ïåðåìåííûõ x1 , . . . , xn , íà âòîðîé äîðîæêå ¾òåêóùåå¿ çíà÷åíèåïîñëåäíåé ïåðåìåííîé (ïî êîòîðîé âåäåòñÿ ðåêóðñèÿ), à íà òðåòüåé äîðîæêå áóäóò âû÷èñëÿòüñÿ çíà÷åíèÿ ôóíêöèé g è h.
 ñâÿçè ñ ýòèì ðàñïðåäåëåíèåì äîðîæåê ïåðâîå äåéñòâèå ìàøèíû Òüþðèíãà, âû÷èñëÿþùåé ôóíêöèþ f , áóäåò ñîñòîÿòü â ïåðåïèñûâàíèè îñíîâíîãî êîäà íàáîðà(x1 , . . . , xn ) íà ïåðâóþ äîðîæêó è ñîçäàíèè îñíîâíîãî êîäà ÷èñëà 0 íàâòîðîé äîðîæêå. Òðåòüþ äîðîæêó ïîêà îñòàâëÿåì ïóñòîé.Âòîðîé ýòàï âû÷èñëåíèé çàêëþ÷àåòñÿ â ïåðåíîñå ñ ïåðâîé äîðîæêè íàòðåòüþ ÷èñåë x1 , . . . , xn−1 , ôîðìèðîâàíèè íà òðåòüåé äîðîæêå îñíîâíîãîêîäà íàáîðà (x1 , . . . , xn−1 ) è ïðèìåíåíèè ê ýòîìó êîäó ìàøèíû M00 . Âñåäàëüíåéøèå äåéñòâèÿ ïî âû÷èñëåíèþ çíà÷åíèÿ ôóíêöèè f áóäóò ñîäåðæàòüñÿ â öèêëå.Èòàê, ñðàâíèâàåì ÷èñëî, çàïèñàííîå íà âòîðîé äîðîæêå, ñ ÷èñëîì xn ,èìåþùèìñÿ íà ïåðâîé äîðîæêå.
Åñëè ýòè ÷èñëà ðàâíû, òî íà òðåòüåéäîðîæêå ïðåäñòàâëåíî â îñíîâíîì êîäå èñêîìîå çíà÷åíèå ôóíêöèè f èíàì íåîáõîäèìî ëèøü óáðàòü äîðîæêè è ïîëó÷èòü îñíîâíîé êîä ðåçóëüòàòà âû÷èñëåíèé.  ïðîòèâíîì ñëó÷àå ïóñòü íà âòîðîé è òðåòüåé äîðîæêàõ çàïèñàíû â îñíîâíîì êîäå ÷èñëà y è z . Äîáàâèì 1 ê ÷èñëó yíà âòîðîé äîðîæêå, îáðàçóåì íà òðåòüåé äîðîæêå îñíîâíîé êîä íàáîðà(x1 , . . . , xn−1 , y, z) è ïðèìåíèì ê ýòîìó íàáîðó ìàøèíó M01 . Ïîñëå ýòîãîâåðíåìñÿ ê íà÷àëó öèêëà.Îïåðàöèÿ ìèíèìèçàöèè ðàññìàòðèâàåòñÿ â çíà÷èòåëüíîé ñòåïåíè àíàëîãè÷íî îïåðàöèè ïðèìèòèâíîé ðåêóðñèè. Ïîýòîìó ñîîòâåòñòâóþùèå ðàññóæäåíèÿ ìû îïóñêàåì. Òåîðåìà äîêàçàíà.ÓÏÐÀÆÍÅÍÈßÎïèñàòü ïîäðîáíî ðàáîòó ìàøèíû Òüþðèíãà, êîòîðàÿ îñóùåñòâëÿåò ïðèìåíåíèå îïåðàöèè ìèíèìèçàöèè (4.6) ê ôóíêöèè g .8. 5. Óíèâåðñàëüíàÿ ìàøèíà ÒüþðèíãàÓíèâåðñàëüíîñòü ÿâëåíèå, õàðàêòåðíîå äëÿ òåîðèè àëãîðèòìîâ. Áîëüøèíñòâî ñàìûõ èçâåñòíûõ ðåçóëüòàòîâ òåîðèè àëãîðèòìîâ òàê èëè èíà÷åñâÿçàíû ñ óíèâåðñàëüíîñòüþ.83Ïîíÿòèå óíèâåðñàëüíîñòè ïðîùå âñåãî îáúÿñíèòü íà ïðèìåðå ôóíêöèé îäíîé ïåðåìåííîé.
Ïóñòü f0 (x), f1 (x), . . . ïîñëåäîâàòåëüíîñòü ôóíêöèé, çàäàííûõ íà N . Ýòî ìîãóò áûòü, íàïðèìåð, ÷àñòè÷íî ðåêóðñèâíûåôóíêöèè, íî ìîãóò áûòü è âñþäó îïðåäåëåííûå íåâû÷èñëèìûå ôóíêöèè.Ôóíêöèÿ U (n, x) íàçûâàåòñÿf0 , f1 , . . ., åñëè âûïîëíÿþòñÿ äâà óñëîâèÿ:âî-ïåðâûõ, äëÿ ëþáîãî n èç N ôóíêöèÿ U (n, x) êàê ôóíêöèÿ îò xñîâïàäàåò ñ íåêîòîðîé ôóíêöèåé fm (x);âî-âòîðûõ, äëÿ ëþáîé ôóíêöèè fm (x) íàéäåòñÿ òàêîå n (èõ ìîæåòáûòü è íåñêîëüêî), ÷òî ôóíêöèÿ U (n, x) êàê ôóíêöèÿ îò x ñîâïàäàåò ñôóíêöèåé fm (x).Ýòî îïðåäåëåíèå óíèâåðñàëüíîé ôóíêöèè ìîæíî âûðàçèòü íåñêîëüêî èíà÷å, åñëè ñêàçàòü, ÷òî ñîâîêóïíîñòü ôóíêöèé {U (0, x), U (1, x), . . .}ñîâïàäàåò ñ ñîâîêóïíîñòüþ {f0 (x), f1 (x), . .
.} (ïîä÷åðêíåì åùå ðàç, ÷òîâ ïîñëåäîâàòåëüíîñòè U (0, x), U (1, x), . . . ôóíêöèè f0 (x), f1 (x), . . . ðàñïîëàãàþòñÿ â ïðîèçâîëüíîì ïîðÿäêå è, âîçìîæíî, ñ ïîâòîðåíèÿìè).Ïîíÿòèå óíèâåðñàëüíîé ìàøèíû Òüþðèíãà ìîæíî ñ÷èòàòü âàðèàíòîìïîíÿòèÿ óíèâåðñàëüíîé ôóíêöèè. Äëÿ ïðîñòîòû îãðàíè÷èìñÿ òîëüêî ìàøèíàìè Òüþðèíãà, èìåþùèìè ëåíòî÷íûé àëôàâèò {0, 1}.Íàçîâåì ìàøèíó Òüþðèíãà U, åñëè îíà âû÷èñëÿåòôóíêöèþ U (n, x), êîòîðàÿ ÿâëÿåòñÿ óíèâåðñàëüíîé äëÿ ïîñëåäîâàòåëüíîñòè ôóíêöèé îäíîé ïåðåìåííîé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà ñëåíòî÷íûì àëôàâèòîì {0, 1}.óíèâåðñàëüíîé äëÿ ïîñëåäîâàòåëüíîñòèôóíêöèéóíèâåðñàëüíîéÒåîðåìà 4.2.Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà ñóùåñòâóåò.Ìû ïðîäåìîíñòðèðóåì, êàê ìîæíî ïîñòðîèòü óíèâåðñàëüíóþ ìàøèíó Òüþðèíãà.
Ê ñîæàëåíèþ, íàì íå óäàñòñÿ âûïèñàòüïðîãðàììó óíèâåðñàëüíîé ìàøèíû Òüþðèíãà (â ïðåäëàãàåìîì ñïîñîáåïîñòðîåíèÿ îíà áóäåò ñîäåðæàòü áîëåå ñîòíè êîìàíä), îäíàêî ïðèíöèïûåå óñòðîéñòâà äîâîëüíî ïðîñòû è ìû ïîñòàðàåìñÿ èõ èçëîæèòü.Ïðåæäå âñåãî, ìû õîòèì çàíóìåðîâàòü âñå ìàøèíû Òüþðèíãà, ðàáîòàþùèå â àëôàâèòå {0, 1}, ò.å. ñîïîñòàâèòü êàæäîé ìàøèíå Òüþðèíãàíåêîòîðîå ÷èñëî èç N . Ïðè ýòîì ñïîñîá íóìåðàöèè äîëæåí áûòü òàêèì,÷òîáû ïî íîìåðó ìàøèíû Òüþðèíãà ìîæíî áûëî áû (òîæå íà ìàøèíåÒüþðèíãà) îäíîçíà÷íî âîññòàíîâèòü åå ïðîãðàììó.Ñíà÷àëà çàêîäèðóåì êîìàíäû ìàøèí Òüþðèíãà.
Êîìàíäå (4.1) ñîïîñòàâèì ñëîâî â àëôàâèòå {0, 1, 2}, èìåþùåå âèäÄîêàçàòåëüñòâî.2ai 2d(j)2al 2d(D)2d(s)2,84(4.9)ãäå d(m) äâîè÷íîå ïðåäñòàâëåíèå ÷èñëà m è d(L) = 0, d(R) = 1,d(S) = 01.Åñëè ïðîãðàììà ìàøèíû Òüþðèíãà M èìååò p êîìàíä è èì óæåñîïîñòàâëåíû ñëîâà w1 , . . . , wp âèäà (4.9) â àëôàâèòå {0, 1, 2}, òî âñåéïðîãðàììå ìàøèíû M ñîïîñòàâèì ñëîâî â àëôàâèòå {0, 1, 2, 3}, êîòîðîåèìååò âèäw1 3w2 3 . .
. 3wp(4.10)(ïîðÿäîê ñëîâ w1 , . . . , wp â ñëîâå (4.10) ðîëè íå èãðàåò). Íîìåðîì ìàøèíû M òåïåðü áóäåì ñ÷èòàòü ÷èñëî, èìåþùåå ïðåäñòàâëåíèå (4.10) â÷åòâåðè÷íîé ñèñòåìå ñ÷èñëåíèÿ.Ïîíÿòíî, ÷òî â ðåçóëüòàòå êàæäàÿ ìàøèíà Òüþðèíãà ïîëó÷èò íåêîòîðûé íîìåð (è äàæå íåñêîëüêî íîìåðîâ, ïîñêîëüêó ñëîâà w1 , . . .
, wp â ñëîâå (4.10) ìîæíî ïåðåñòàâëÿòü). Ïðè ýòîì ïî íîìåðó ìàøèíû Òüþðèíãàñðàâíèòåëüíî ïðîñòî âîññòàíîâèòü ïðîãðàììó ìàøèíû: äîñòàòî÷íî ëèøüïðåäñòàâèòü ýòîò íîìåð â ÷åòâåðè÷íîé ñèñòåìå ñ÷èñëåíèÿ. Îòìåòèì åùå,÷òî äàëåêî íå êàæäîå íàòóðàëüíîå ÷èñëî áóäåò ÿâëÿòüñÿ íîìåðîì íåêîòîðîé ìàøèíû Òüþðèíãà. Îäíàêî, ïîëüçóÿñü àëãîðèòìîì êîäèðîâàíèÿìàøèí Òüþðèíãà, íå ñîñòàâëÿåò îñîáîãî òðóäà ïðîàíàëèçèðîâàòü ÷åòâåðè÷íîå ïðåäñòàâëåíèå íàòóðàëüíîãî ÷èñëà è âûÿñíèòü, îïðåäåëÿåò ëèîíî ïðîãðàììó ìàøèíû Òüþðèíãà.Ïåðåéäåì òåïåðü ê ïîñòðîåíèþ óíèâåðñàëüíîé ìàøèíû Òüþðèíãà U .Ñîáñòâåííî, ìû ïðîâåäåì ëèøü îïèñàíèå ôóíêöèîíèðîâàíèÿ óíèâåðñàëüíîé ìàøèíû U . Äåòàëè ïîñòðîåíèÿ ïðîãðàìì äëÿ îòäåëüíûõ ÷àñòåéìàøèíû U ìû îñòàâëÿåì ÷èòàòåëþ.Èòàê, ïóñòü íà ëåíòå ìàøèíû U â îñíîâíîì êîäå ïðåäñòàâëåíà ïàðà ÷èñåë n, x.
Êàê è â 4, âûäåëèì íà ëåíòå ìàøèíû U òðè äîðîæêè.Ïåðâàÿ äîðîæêà áóäåò ñëóæèòü äëÿ çàïèñè ïðîãðàììû ìàøèíû Òüþðèíãà, èìåþùåé íîìåð n (îáîçíà÷èì ýòó ìàøèíó ÷åðåç Mn ). Íà âòîðîéäîðîæêå áóäåò õðàíèòüñÿ äâîè÷íûé íîìåð ¾òåêóùåãî¿ ñîñòîÿíèÿ ìàøèíû Mn . À íà òðåòüåé äîðîæêå áóäåò ñîáñòâåííî ìîäåëèðîâàòüñÿ ïðîöåññïðèìåíåíèÿ ìàøèíû Mn ê àðãóìåíòó x. ñîîòâåòñòâèè ñ ðàñïðåäåëåíèåì ðîëè äîðîæåê ìàøèíà U ïðåæäåâñåãî ïåðåíîñèò ÷èñëî n íà ïåðâóþ äîðîæêó è ñîçäàåò íà íåé ÷åòâåðè÷íóþ çàïèñü n (ïðè ýòîì ìîæíî ïîëüçîâàòüñÿ ¾øêîëüíûì¿ àëãîðèòìîìäåëåíèÿ íà 4 ñ îñòàòêîì).
Íà âòîðóþ äîðîæêó ìàøèíà U çàïèñûâàåò÷èñëî 1, à íà òðåòüþ ÷èñëî x â îñíîâíîì êîäå. Êðîìå òîãî, íà òðåòüåéäîðîæêå îñîáûì ñèìâîëîì (ìåòêîé) ïîìå÷àåòñÿ òà êëåòêà, êîòîðóþ âäàííûé ìîìåíò âðåìåíè îáîçðåâàåò ãîëîâêà ìîäåëèðóåìîé ìàøèíû Mn .85Èñïîëüçóÿ ñòðóêòóðó ïðåäñòàâëåíèé (4.9),(4.10), ìàøèíà U íà ïåðâîéäîðîæêå ïðîâåðÿåò, ÿâëÿåòñÿ ëè ÷åòâåðè÷íàÿ çàïèñü ÷èñëà n íîìåðîìíåêîòîðîé ìàøèíû Òüþðèíãà.
Åñëè íåò, òî ìàøèíà U ðåàëèçóåò êàêóþëèáî ïðîñòóþ ôóíêöèþ (íàïðèìåð, êîíñòàíòó 0).Ïðåäïîëîæèì, ÷òî íà ïåðâîé äîðîæêå äåéñòâèòåëüíî çàïèñàí êîä ìàøèíû Òüþðèíãà Mn .  ýòîì ñëó÷àå ìàøèíà U øàã çà øàãîì ìîäåëèðóåòïðîöåññ ïðèìåíåíèÿ ìàøèíû Mn ê àðãóìåíòó x. Äëÿ ýòîãî ñ òðåòüåéäîðîæêè ñ÷èòûâàåòñÿ ñèìâîë ai , êîòîðûé â äàííûé (ìîäåëèðóåìûé) ìîìåíò âðåìåíè îáîçðåâàåò ãîëîâêà ìàøèíû Mn .
Çàòåì ìàøèíà U ïîñëåäîâàòåëüíî ïðîñìàòðèâàåò êîä ìàøèíû Mn , ïðåäñòàâëåííûé íà ïåðâîéäîðîæêå, è ðàçûñêèâàåò â íåì ñëîâî (4.9), ãäå j íîìåð ¾òåêóùåãî¿ ñîñòîÿíèÿ ìàøèíû Mn , çàïèñàííûé íà âòîðîé äîðîæêå. Íàéäÿ ýòî ñëîâî,ìàøèíà U îñóùåñòâëÿåò ïðåîáðàçîâàíèÿ íà âòîðîé è òðåòüåé äîðîæêàõëåíòû, ñîîòâåòñòâóþùèå òðîéêå (al , D, s). Èìåííî, íà âòîðîé äîðîæêåäâîè÷íàÿ çàïèñü ÷èñëà j çàìåíÿåòñÿ äâîè÷íîé çàïèñüþ ÷èñëà s, à íàòðåòüåé äîðîæêå îáîçðåâàåìûé ìàøèíîé Mn ñèìâîë ai çàìåíÿåòñÿ ñèìâîëîì al è ñäâèãàåòñÿ ìåòêà, óêàçûâàþùàÿ ïîëîæåíèå ãîëîâêè ìàøèíûMn íà ëåíòå. Äàëåå ìàøèíà U ïåðåõîäèò ê ìîäåëèðîâàíèþ ñëåäóþùåãîøàãà ðàáîòû ìàøèíû Mn .Åñëè ìàøèíà Mn çàêàí÷èâàåò ðàáîòó íàä àðãóìåíòîì x, òî ìàøèíà Uïðåîáðàçóåò ðåçóëüòàò âû÷èñëåíèé ìàøèíû Mn , ïîëó÷åííûé íà òðåòüåéäîðîæêå, â îñíîâíîé êîä.
 ïðîòèâíîì ñëó÷àå ìàøèíà U , êàê è ìàøèíàMn , ðàáîòàåò íåîãðàíè÷åííî äîëãî. Òåîðåìà äîêàçàíà.Êàê ìû îòìå÷àëè âûøå, ñóùåñòâîâàíèå óíèâåðñàëüíîé ìàøèíû Òüþðèíãà U ðàâíîñèëüíî ñóùåñòâîâàíèþ âû÷èñëèìîé ôóíêöèè U (n, x), óíèâåðñàëüíîé äëÿ ìíîæåñòâà âñåõ âû÷èñëèìûõ ôóíêöèé îäíîé ïåðåìåííîé. ñâîþ î÷åðåäü èç ïîñëåäíåãî ôàêòà âûòåêàåò ðÿä ñëåäñòâèé, ñîñòàâëÿþùèõ ÿäðî òåîðèè àëãîðèòìîâ. Ïðèâåäåì íåêîòîðûå èç íèõ.Ðàññìîòðèì ïðåæäå âñåãî ¾äèàãîíàëüíóþ¿ ôóíêöèþ U (x, x) + 1.
Î÷åâèäíî, ÷òî îíà âû÷èñëèìà. Çíà÷èò, äëÿ íåêîòîðîãî n è âñåõ x äîëæíîâûïîëíÿòüñÿ ðàâåíñòâîU (n, x) = U (x, x) + 1.Ïîäñòàâëÿÿ â íåãî âìåñòî x ÷èñëî n, ïîëó÷èì ¾ïðîòèâîðå÷èâîå¿ ðàâåíñòâîU (n, n) = U (n, n) + 1.(4.11)Îäíàêî ïðîòèâîðå÷èÿ çäåñü íåò. Ðàâåíñòâî (4.11) ïîêàçûâàåò ëèøü, ÷òî86çíà÷åíèå U (n, n) íå îïðåäåëåíî (èç ïîñòðîåíèÿ ôóíêöèè U ëåãêî ïîíÿòü,÷òî ôóíêöèÿ U ÷àñòè÷íàÿ).Òàêèì îáðàçîì, èìåÿ óíèâåðñàëüíóþ âû÷èñëèìóþ ôóíêöèþ U , ìûìîæåò òî÷íî óêàçàòü íàáîð (èìåííî íàáîð (n, n), ãäå n åñòü íîìåð ôóíêöèè U (x, x) + 1 â íóìåðàöèè ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé, äàâàåìîéôóíêöèåé U ), íà êîòîðîì ôóíêöèÿ U çàâåäîìî íå îïðåäåëåíà.
Èòàê,ôóíêöèÿ U (x, x) + 1 âû÷èñëèìà è íå âñþäó îïðåäåëåíà.Îäíàêî áûâàþò òàêèå âû÷èñëèìûå íå âñþäó îïðåäåëåííûå ôóíêöèè(íàïðèìåð ôóíêöèÿ [log2 x]), êîòîðûå ëåãêî äîîïðåäåëÿþòñÿ äî âñþäóîïðåäåëåííûõ âû÷èñëèìûõ ôóíêöèé. Ôóíêöèÿ U (x, x) + 1 ýòèì ñâîéñòâîì íå îáëàäàåò.Íå ñóùåñòâóåò òàêîé âñþäó îïðåäåëåííîé âû÷èñëèìîé ôóíêöèè, êîòîðàÿ ñîâïàäàåò ñ ôóíêöèåé U (x, x) + 1 íà âñåé ååîáëàñòè îïðåäåëåíèÿ.Ñëåäñòâèå 1.Ïðåäïîëîæèì, íàïðîòèâ, ÷òî òàêàÿ ôóíêöèÿ V (x)ñóùåñòâóåò.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
