С.С. Марченков - Избранные главы дискретной математики (1124120), страница 15
Текст из файла (страница 15)
Òàêæå íåòðóäíî óáåäèòüñÿ, ÷òî ìàøèíà M5 ïðàâèëüíî âû÷èñëÿåòôóíêöèþ-êîíñòàíòó 0 (ðàññìàòðèâàåìóþ îò îäíîé ïåðåìåííîé). ÌàøèíàM5 ïðîáåãàåò â ñîñòîÿíèè q1 ñëåâà íàïðàâî âåñü ìàññèâ èç åäèíèö è68çàìåíÿåò èõ íóëÿìè. Ïîñëå ýòîãî âìåñòî ïåðâîãî ñïðàâà ñèìâîëà 0 îíàñòàâèò 1 è îñòàíàâëèâàåòñÿ.Ðàññìîòðèì ÷óòü áîëåå ñëîæíûé ïðèìåð ôóíêöèèx −· 1 =0,åñëè x = 0,x − 1 â îñòàëüíûõ ñëó÷àÿõ.Ìàøèíà Òüþðèíãà M6 çàìåíÿåò ïåðâóþ åäèíèöó îñíîâíîãî êîäà íóëåì,ïåðåõîäèò â ñîñòîÿíèå q2 è ñäâèãàåò ãîëîâêó âïðàâî. Íàõîäÿñü â ñîñòîÿíèè q2 , îíà çàïèñûâàåò âî âòîðóþ êëåòêó 1 è îñòàíàâëèâàåòñÿ.
Ïðî÷åðêâ îäíîé èç êëåòîê òàáëèöû äëÿ ìàøèíû M6 óêàçûâàåò íà òî, ÷òî ýòóêëåòêó ìîæíî çàïîëíèòü ïðîèçâîëüíûì îáðàçîì.Èç ïðîñòûõ âû÷èñëèìûõ ôóíêöèé îñòàíîâèìñÿ åùå íàIin (x1 , . . . , xi , . . . , xn ) = xi . Âñå îíè âû÷èñëÿþòñÿ ñõîäíûì îáðàçîì: ãîëîâêà ìàøèíû äâèæåòñÿ ñëåâà íàïðàâî äî i-ãî ìàññèâà èç åäèíèö, ñòèðàÿ ïî ïóòè âñå åäèíèöû (ò.å. çàìåíÿÿ èõ íóëÿìè), îñòàâëÿåòáåç èçìåíåíèÿ i-é ìàññèâ, çàòåì, ïðîäâèãàÿñü äî êîíöà îñíîâíîãî êîäà,ñòèðàåò åäèíèöû îñòàâøèõñÿ ìàññèâîâ.  çàêëþ÷åíèå ãîëîâêà ìàøèíûâîçâðàùàåòñÿ íà ïåðâóþ åäèíèöó áûâøåãî i-ãî ìàññèâà. Ïîñêîëüêó ÷èñëîñîñòîÿíèé ìàøèíû Òüþðèíãà, âû÷èñëÿþùåé ôóíêöèþ Iin , ëèíåéíûì îáðàçîì çàâèñèò îò ïàðàìåòðîâ i, n, ìû ïîñòðîèì ìàøèíó Òüþðèíãà ëèøüäëÿ âû÷èñëåíèÿ ôóíêöèè I23 (x1 , x2 , x3 ).
Ïðîãðàììà ýòîé ìàøèíû ïðåäñòàâëåíà â íèæåñëåäóþùåé òàáëèöå.ñåëåêòîðíûõôóíêöèÿõq1q2q3q4q50 0Rq2 0Rq3 0Lq4 0Lq4 0Rq01 0Rq1 1Rq2 0Rq3 1Lq5 1Lq5òåçèñ Òüþðèíãà.Âñÿêàÿ àëãîðèòìè÷åñêè âû÷èñëèìàÿ ôóíêöèÿ ìîæåò áûòü âû÷èñëåíàíà ïîäõîäÿùåé ìàøèíå Òüþðèíãà. çàêëþ÷åíèå ïàðàãðàôà ñôîðìóëèðóåìÓÏÐÀÆÍÅÍÈßÄîêàçàòü, ÷òî äëÿ âñÿêîé ìàøèíû Òüþðèíãà ñóùåñòâóåò ýêâèâàëåíòíàÿ åé (ò.å. äàþùàÿ òîò æå ñàìûé ðåçóëüòàò) ìàøèíà Òüþðèíãà,ïðîãðàììà êîòîðîé íå ñîäåðæèò êîìàíä ñ ñèìâîëîì S .2. Ïîñòðîèòü ìàøèíó Òüþðèíãà, ïðàâèëüíî âû÷èñëÿþùóþ ôóíêöèþx + y.3. Ìîæåò ëè îäíà è òà æå ìàøèíà Òüþðèíãà ïðàâèëüíî âû÷èñëÿòüäâå ðàçëè÷íûå ôóíêöèè?1.69Ïóñòü ïðîãðàììà ìàøèíû Òüþðèíãà M0 ïîëó÷åíà èç ïðîãðàììûìàøèíû M çàìåíîé âñåõ ñèìâîëîâ L ñèìâîëàìè R è âñåõ ñèìâîëîâ Rñèìâîëàìè L. Ìîæíî ëè â êàêîì-ëèáî ñìûñëå óòâåðæäàòü, ÷òî ìàøèíàM0 âû÷èñëÿåò òå æå ôóíêöèè, ÷òî è ìàøèíà M?4. 2.
Êîìïîçèöèÿ è èòåðàöèÿ ìàøèí ÒüþðèíãàÎáû÷íî ïðè ïîñòðîåíèè äîñòàòî÷íî ñëîæíûõ ìàøèí Òüþðèíãà ïðèáåãàþò ê èçâåñòíîìó íà ïðàêòèêå ïðèåìó: ðàçáèâàþò àëãîðèòì, ðåàëèçóåìûé ìàøèíîé Òüþðèíãà, íà îòäåëüíûå ïðîñòûå ÷àñòè, ñòðîÿò äëÿ íèõìàøèíû Òüþðèíãà è çàòåì ¾ñîáèðàþò¿ èç ïîëó÷åííûõ ¾ìàëûõ¿ ìàøèíÒüþðèíãà òðåáóåìóþ ìàøèíó Òüþðèíãà. Åñëè ðàçáèåíèå àëãîðèòìà íà÷àñòè è ïîñòðîåíèå äëÿ íèõ ìàøèí Òüþðèíãà åñòü ïðîöåññ â çíà÷èòåëüíîé ñòåïåíè òâîð÷åñêèé, òî ïîñëåäóþùàÿ ¾ñáîðêà¿ ìàøèí Òüþðèíãà ÿâëÿåòñÿ äåëîì âåñüìà ðóòèííûì. Çäåñü ñóùåñòâóþò äâà îñíîâíûõ ïðèåìàêîíñòðóèðîâàíèÿ èç îäíèõ ìàøèí Òüþðèíãà äðóãèõ ìàøèí Òüþðèíãà.Ýòîèìàøèí Òüþðèíãà.Êîìïîçèöèÿ ìàøèí Òüþðèíãà ôîðìàëèçóåò èäåþ ïîñëåäîâàòåëüíîãî âûïîëíåíèÿ äâóõ (ðåæå íåñêîëüêèõ) âû÷èñëèòåëüíûõ ïðîöåññîâ.
Âñàìîì ïðîñòåéøåì ñëó÷àå êîìïîçèöèÿ äâóõ ìàøèí Òüþðèíãà îïðåäåëÿåòñÿ òàê. Ïóñòü M1 , M2 ìàøèíû Òüþðèíãà ñ îäíèì è òåì æå ëåíòî÷íûì àëôàâèòîì. Áóäåì ïðåäïîëàãàòü, ÷òî ìíîæåñòâà ñîñòîÿíèé ìàøèíM1 , M2 íå ïåðåñåêàþòñÿ. Ìû õîòèì ñîçäàòü ìàøèíó Òüþðèíãà M, êîòîðàÿ ðàáîòàåò ñëåäóþùèì îáðàçîì. Íà èñõîäíîì ñëîâå ā íà÷èíàåò ðàáîòàòü ìàøèíà M1 .
Åñëè M1 çàêàí÷èâàåò ñâîþ ðàáîòó, òî ñ ýòîé êîíôèãóðàöèè (ò.å. ñ äîñòèãíóòûìè çàïîëíåíèåì ëåíòû è ïîëîæåíèåì ãîëîâêè íàëåíòå) çàïóñêàåòñÿ ìàøèíà M2 . Ðåçóëüòàò, ïîëó÷åííûé ïðè ýòîì ìàøèíîé M2 , è áóäåò ÿâëÿòüñÿ ðåçóëüòàòîì ïðèìåíåíèÿ ìàøèíû M ê ñëîâó ā.Ðàçóìååòñÿ, åñëè îäíà èç ìàøèí M1 , M2 ðàáîòàåò íåîãðàíè÷åííî äîëãî,òî è ìàøèíà M áóäåò ðàáîòàòü íåîãðàíè÷åííî äîëãî.Äîâîëüíî ïîíÿòíî, êàê èç ïðîãðàìì ìàøèí M1 , M2 ïîëó÷èòü ïðîãðàììó ìàøèíû M. Äëÿ ýòîãî íåîáõîäèìî âî âñåõ êîìàíäàõ ìàøèíûM1 çàìåíèòü çàêëþ÷èòåëüíîå ñîñòîÿíèå íà÷àëüíûì ñîñòîÿíèåì ìàøèíû M2 , à çàòåì îáúåäèíèòü ïîëó÷åííûå ìíîæåñòâà êîìàíä ìàøèí M1è M2 .
Íà÷àëüíûì ñîñòîÿíèåì ìàøèíû M áóäåò ÿâëÿòüñÿ íà÷àëüíîå ñîñòîÿíèå ìàøèíû M1 , à çàêëþ÷èòåëüíûì çàêëþ÷èòåëüíîå ñîñòîÿíèåìàøèíû M2 .êîìïîçèöèÿ èòåðàöèÿ70Âåðíåìñÿ ê ìàøèíå Òüþðèíãà èç ïðåäûäóùåãî ïàðàãðàôà, êîòîðàÿïðàâèëüíî âû÷èñëÿåò ôóíêöèþ I23 (x1 , x2 , x3 ). Åå ìîæíî ïîëó÷èòü â âèäå ïîñëåäîâàòåëüíîé êîìïîçèöèè ìàøèí Òüþðèíãà M1 M5 (ïåðâûéèíäåêñ ó ñîñòîÿíèÿ óêàçûâàåò íà íîìåð ìàøèíû):q110 0Rq101 0Rq11q210 0Rq201 1Rq21q310 0Lq301 0Rq31q410 0Lq411 1Lq40q510 0Rq501 1Lq51M1M2M3M4M5Ìàøèíà M1 ñòèðàåò â îñíîâíîì êîäå íàáîðà (x1 , x2 , x3 ) ïåðâûé ìàññèâ èç åäèíèö, ïðîïóñêàåò ïóñòóþ êëåòêó ìåæäó ïåðâûì è âòîðûì ìàññèâàìè è îñòàíàâëèâàåòñÿ íà ïåðâîé åäèíèöå âòîðîãî ìàññèâà.
ÌàøèíàM2 , íè÷åãî íå èçìåíÿÿ, ïðîáåãàåò âòîðîé ìàññèâ èç åäèíèö, ïðîïóñêàåòñëåäóþùóþ çà íèì ïóñòóþ êëåòêó è îñòàíàâëèâàåòñÿ íà ïåðâîé åäèíèöåòðåòüåãî ìàññèâà. Äåéñòâèÿ ìàøèíû M3 àíàëîãè÷íû äåéñòâèÿì ìàøèíû M1 , çà èñêëþ÷åíèåì ïîñëåäíåãî øàãà, íà êîòîðîì ãîëîâêà ìàøèíûM3 ñìåùàåòñÿ íà îäíó êëåòêó âëåâî.
Ìàøèíà M4 äâèæåòñÿ âëåâî ïîïóñòûì êëåòêàì äî êðàéíåé ïðàâîé åäèíèöû áûâøåãî âòîðîãî ìàññèâà èîñòàíàâëèâàåòñÿ â ñîñåäíåé ñ íåé êëåòêå. Íàêîíåö, ìàøèíà M5 ïðîáåãàåòñïðàâà íàëåâî îñòàâøèéñÿ ìàññèâ èç åäèíèö, âûõîäèò íà ïðèìûêàþùóþê íåìó ïóñòóþ êëåòêó, âîçâðàùàåòñÿ íà îäíó êëåòêó íàçàä è îñòàíàâëèâàåòñÿ.Òîò òèï êîìïîçèöèè, êîòîðûé ìû îïèñàëè âûøå, ìîæíî áûëî áû íàçâàòü áåçóñëîâíîé êîìïîçèöèåé ìàøèí Òüþðèíãà. Îäíàêî ñóùåñòâóþòçàäà÷è, ãäå íåîáõîäèìî âîñïîëüçîâàòüñÿ áîëåå ñëîæíûìè ôîðìàìè êîìïîçèöèè. Ïðåäïîëîæèì, íàïðèìåð, ÷òî ìû õîòèì ïîëó÷èòü èç äàííûõìàøèí Òüþðèíãà M1 , M2 òàêóþ ìàøèíó Òüþðèíãà M, êîòîðàÿ â íåêîòîðûõ ñëó÷àÿõ ðàáîòàåò êàê ìàøèíà M1 , à â äðóãèõ êàê êîìïîçèöèÿìàøèí M1 è M2 . Äëÿ ýòîãî, èñõîäÿ èç ñîäåðæàòåëüíûõ ñîîáðàæåíèé,ìû âûäåëèì ñðåäè çàêëþ÷èòåëüíûõ êîìàíä (ò.å.
êîìàíä, ñîäåðæàùèõçàêëþ÷èòåëüíîå ñîñòîÿíèå) ìàøèíû M1 òàêèå êîìàíäû, êîòîðûå îòâå÷àþò âòîðîé èç ðàññìàòðèâàåìûõ âîçìîæíîñòåé. À äàëåå, êàê è âûøå,çàìåíèì â íèõ çàêëþ÷èòåëüíîå ñîñòîÿíèå íà÷àëüíûì ñîñòîÿíèåì ìàøèíû M2 . Âñå îñòàëüíûå êîìàíäû îáåèõ ìàøèí îñòàâèì áåç èçìåíåíèÿ.Åùå îäèí òèï êîìïîçèöèè ìàøèí Òüþðèíãà ñîîòâåòñòâóåò ñëó÷àþ,êîãäà íåîáõîäèìî îñóùåñòâèòü âûáîð èç äâóõ èëè áîëåå àëüòåðíàòèâ.Ïóñòü M1 , M2 , M3 ìàøèíû Òüþðèíãà ñ ïîïàðíî íå ïåðåñåêàþùèìèñÿìíîæåñòâàìè ñîñòîÿíèé.
È ïóñòü ñîäåðæàòåëüíî ìàøèíà M1 ðàñïîçíàåò71íåêîòîðîå ñâîéñòâî (ïðåäèêàò) p. Ïðè ýòîì â ñëó÷àå âûïîëíåíèÿ ñâîéñòâà p ìû áû õîòåëè çàïóñòèòü ìàøèíó M2 , à â ñëó÷àå íåâûïîëíåíèÿ ìàøèíó M3 . Ôîðìàëüíî ñâîéñòâî p õàðàêòåðèçóåòñÿ çàêëþ÷èòåëüíûìè êîìàíäàìè ìàøèíû M1 : ÷àñòü çàêëþ÷èòåëüíûõ êîìàíä ñîîòâåòñòâóåò âûïîëíåíèþ ñâîéñòâà p, îñòàëüíàÿ ÷àñòü íåâûïîëíåíèþ ñâîéñòâàp. Îáîçíà÷èì çàêëþ÷èòåëüíîå ñîñòîÿíèå èç ïåðâîé ÷àñòè çàêëþ÷èòåëüíûõ êîìàíä ìàøèíû M1 ÷åðåç q00 , èç âòîðîé ÷àñòè ÷åðåç q000 . Òîãäàóêàçàííîå ¾ðàçâåòâëåíèå¿ ìàøèí Òüþðèíãà M1 , M2 , M3 âûïîëíÿåòñÿ òàê: âñå çàêëþ÷èòåëüíûå ñîñòîÿíèÿ q00 ìàøèíû M1 çàìåíÿþòñÿ íà÷àëüíûì ñîñòîÿíèåì ìàøèíû M2 , à âñå çàêëþ÷èòåëüíûå ñîñòîÿíèÿ q000 íà÷àëüíûì ñîñòîÿíèåì ìàøèíû M3 .
Çàêëþ÷èòåëüíûìè ñîñòîÿíèìèïîëó÷åííîé ìàøèíû Òüþðèíãà ÿâëÿþòñÿ çàêëþ÷èòåëüíîå ñîñòîÿíèå ìàøèíû M2 è çàêëþ÷èòåëüíîå ñîñòîÿíèå ìàøèíû M3 .Ðàññìîòðèì ïðèìåð êîìïîçèöèè ìàøèí Òüþðèíãà ïîñëåäíåãî òèïà.Èñïîëüçóÿ ýòîò òèï êîìïîçèöèè, ïîñòðîèì ìàøèíó Òüþðèíãà, êîòîðàÿïðàâèëüíî âû÷èñëÿåò ôóíêöèþrm(x, 2) =0, åñëè x ÷åòíî,1, åñëè x íå÷åòíî.Îïðåäåëèì ìàøèíû M6 , M7 , M8 .q11q120000 0Sq10 0Sq101 0Rq12 0Rq11M6q210 1Sq201M7q31q320 1Rq32 1Lq301M8Ìàøèíà M6 , íàõîäÿñü â íà÷àëüíîì ñîñòîÿíèè q11 íà ïåðâîé åäèíèöåìàññèâà èç x + 1 åäèíèö, äâèæåòñÿ ïî ìàññèâó âïðàâî, ñòèðàåò âñå åäèíèöû è ïîî÷åðåäíî ïðîõîäèò ÷åðåç ñîñòîÿíèÿ q11 , q12 .  ñëó÷àå ÷åòíîñòè÷èñëà x (òîãäà ïðîáåãàåìûé ìàññèâ ñîñòîèò èç íå÷åòíîãî ÷èñëà åäèíèö)ìàøèíà M6 âûõîäèò íà ïåðâóþ ïóñòóþ êëåòêó â ñîñòîÿíèè q12 è îñòà0íàâëèâàåòñÿ â çàêëþ÷èòåëüíîì ñîñòîÿíèè q10.
 ñëó÷àå íå÷åòíîñòè ÷èñëà00x àíàëîãè÷íûé ïðîöåññ çàêàí÷èâàåòñÿ â çàêëþ÷èòåëüíîì ñîñòîÿíèè q10.000Òàêèì îáðàçîì, ñ ïîìîùüþ ñîñòîÿíèé q10 , q10 ìàøèíà M6 ¾ðàñïîçíàåò¿÷åòíîñòü ÷èñëà x.Ìàøèíà M7 çàïèñûâàåò â ïóñòóþ êëåòêó 1 (îñíîâíîé êîä ÷èñëà 0) èîñòàíàâëèâàåòñÿ. Ìàøèíà M8 çàïèñûâàåò â äâóõ ïóñòûõ êëåòêàõ åäèíèöû, âîçâðàùàåòñÿ íà ïåðâóþ åäèíèöó è îñòàíàâëèâàåòñÿ. Ïðî÷åðêè â72òàáëèöàõ äëÿ ìàøèí M7 , M8 îçíà÷àþò, ÷òî ñîîòâåòñòâóþùèå êëåòêèìîãóò áûòü çàïîëíåíû ïðîèçâîëüíûì îáðàçîì.Îáðàçóåì òåïåðü êîìïîçèöèþ M ìàøèí M6 , M7 , M8 òàê, ÷òîáû ìàøèíà M7 íà÷èíàëà ðàáîòó ïðè ïîïàäàíèè ìàøèíû M6 â çàêëþ÷èòåëü000.
Ñî, à ìàøèíà M8 â çàêëþ÷èòåëüíîå ñîñòîÿíèå q10íîå ñîñòîÿíèå q10îòâåòñòâóþùàÿ òàáëèöà äëÿ ìàøèíû M áóäåò âûãëÿäåòü ñëåäóþùèìîáðàçîì:q11q12q21q31q320 0Sq31 0Sq21 1Sq20 1Rq32 1Lq301 0Rq12 0Rq11Èòåðàöèÿ ìàøèíû Òüþðèíãà ôîðìàëèçóåò èäåþ ìíîãîêðàòíîãî ðåãóëèðóåìîãî ïðèìåíåíèÿ îäíîãî è òîãî æå àëãîðèòìà. Ïóñòü çàäàíà ìàøèíà Òüþðèíãà M è ìû õîòèì ìíîãîêðàòíî ïðèìåíÿòü ýòó ìàøèíó (âäóõå êîìïîçèöèè ìàøèí Òüþðèíãà) äî òåõ ïîð, ïîêà íå áóäåò âûïîëíåíîíåêîòîðîå óñëîâèå (ïðåäèêàò) p.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
