С.С. Марченков - Избранные главы дискретной математики (1124120), страница 16
Текст из файла (страница 16)
Ñàìî óñëîâèå p, êàê è ðàíåå, ìîæíî çàäàòü ñ ïîìîùüþ íåêîòîðûõ çàêëþ÷èòåëüíûõ êîìàíä ìàøèíû M. ×òîáûâûäåëèòü ýòè çàêëþ÷èòåëüíûå êîìàíäû, îáîçíà÷èì ñîäåðæàùååñÿ â íèõçàêëþ÷èòåëüíîå ñîñòîÿíèå ÷åðåç q00 . Âñå îñòàëüíûå âõîæäåíèÿ çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ â ïðîãðàììó ìàøèíû M îáîçíà÷èì ÷åðåç q000 . Òåïåðüíàøå íàìåðåíèå èòåðèðîâàòü ðàáîòó ìàøèíû Òüþðèíãà M ìîæíî âûðàçèòü áîëåå òî÷íî. Çàïóñêàåì ìàøèíó M â íà÷àëüíîì ñîñòîÿíèè q1 .Åñëè ÷åðåç íåêîòîðîå êîëè÷åñòâî òàêòîâ îíà ïîïàäàåò â çàêëþ÷èòåëüíîå ñîñòîÿíèå q000 , òî ¾âîçâðàùàåì¿ åå âíîâü â íà÷àëüíîå ñîñòîÿíèå q1 èò.ä.
Ôîðìàëüíî èòåðàöèÿ ìàøèíû M îòíîñèòåëüíî óñëîâèÿ p ïîëó÷àåòñÿ çàìåíîé âñåõ âõîæäåíèé çàêëþ÷èòåëüíîãî ñîñòîÿíèÿ q000 íà÷àëüíûìñîñòîÿíèåì q1 .Ïóñòü, íàïðèìåð, ìàøèíà M çàäàåòñÿ òàáëèöåé 1.q1q2q3q4000Rq2 0Sq0 0Lq41 0Rq2 0Rq3 0Lq4 1Sq000q1q2q3q4000Rq2 0Sq0 0Lq41 0Rq2 0Rq3 0Lq4 1Sq1Òàáë. 1Òàáë. 2Ïðîàíàëèçèðóåì ðàáîòó ìàøèíû M.
Ïðåäïîëîæèì, ÷òî â íà÷àëüíûé ìîìåíò âðåìåíè íà ëåíòå ìàøèíû M çàïèñàí îñíîâíîé êîä íàáîðà(x1 , x2 ), à ãîëîâêà ìàøèíû óñòàíîâëåíà íà êðàéíþþ ïðàâóþ åäèíèöóïåðâîãî ìàññèâà. Íà÷èíàÿ ðàáîòó â ýòîé ïîçèöèè, ìàøèíà M ñîâåðøàåòñëåäóþùèå äåéñòâèÿ.73Îíà çàìåíÿåò îáîçðåâàåìóþ åäèíèöó íóëåì, ñäâèãàåòñÿ âïðàâî äî ïåðâîé åäèíèöû âòîðîãî ìàññèâà è òàêæå çàìåíÿåò åå íóëåì. Åñëè x2 = 0,òî ìàøèíà M îñòàíàâëèâàåòñÿ â ñëåäóùåé ñïðàâà êëåòêå â ñîñòîÿíèè q00 . ïðîòèâíîì ñëó÷àå ìàøèíà M çàìåíÿåò âòîðóþ åäèíèöó âòîðîãî ìàññèâà íóëåì è âîçâðàùàåòñÿ (åñëè x1 6= 0) íà êðàéíþþ ïðàâóþ åäèíèöóïåðâîãî ìàññèâà, ãäå è îñòàíàâëèâàåòñÿ â ñîñòîÿíèè q000 .Îáðàçóåì èòåðàöèþ ìàøèíû M çàìåíèì â åå ïðîãðàììå çàêëþ÷èòåëüíîå ñîñòîÿíèå q000 íà÷àëüíûì ñîñòîÿíèåì q1 (ñì.
òàáë. 2). Ïîëó÷èììàøèíó Òüþðèíãà M0 . Íåòðóäíî ïîíÿòü, êàê áóäåò ðàáîòàòü ìàøèíàM0 . Îíà äîñòèãàåò çàêëþ÷èòåëüíîå ñîñòîÿíèå q00 â òîì è òîëüêî òîì ñëó÷àå, êîãäà x2 = 2y è x1 > y .  îñòàëüíûõ ñëó÷àÿõ ìàøèíà M0 ðàáîòàåòíåîãðàíè÷åííî äîëãî.ÓÏÐÀÆÍÅÍÈßÏðåäñòàâèòü â âèäå êîìïîçèöèè áîëåå ïðîñòûõ ìàøèí Òüþðèíãàìàøèíû, ïðàâèëüíî âû÷èñëÿþùèå ôóíêöèè5.sg(x) =1, åñëè x = 0,0, åñëè x = 0,sg(x) =0, åñëè x > 0,1, åñëè x > 0,0,åñëè x 6 3,3 −· x =x − 3, åñëè x > 3,Ïðèìåíèâ èòåðàöèþ ìàøèíû Òüþðèíãà, ïîñòðîèòü ìàøèíó, ïðàâèëüíî âû÷èñëÿþùóþ ôóíêöèþ [x/2] (öåëàÿ ÷àñòü îò äåëåíèÿ x íà 2).6. 3.
Ìîäåëèðîâàíèå ìàøèí Òüþðèíãà òåîðèè àëãîðèòìîâ äîâîëüíî ðàñïðîñòðàíåííûì ÿâëÿåòñÿ ïðèåì, êîãäà ñ ïîìîùüþ îäíîãî âû÷èñëèòåëüíîãî óñòðîéñòâà ìîäåëèðóåòñÿ ðàáîòàäðóãîãî âû÷èñëèòåëüíîãî óñòðîéñòâà. Çäåñü ìû ðàññìîòðèì ëèøü ìîäåëèðîâàíèå ìàøèí Òüþðèíãà, ðàáîòàþùèõ â àëôàâèòå {0, 1, a2 , .
. . , ak },ãäå k > 2, ìàøèíàìè Òüþðèíãà, èìåþùèìè ëåíòî÷íûé àëôàâèò {0, 1}.Áîëåå òîãî, íàñ áóäóò èíòåðåñîâàòü òîëüêî ôóíêöèè, ïðàâèëüíî âû÷èñëèìûå òåìè è äðóãèìè ìàøèíàìè Òüþðèíãà. Ìû óñòàíîâèì, ÷òî ýòèêëàññû ôóíêöèé ñîâïàäàþò.Èäåÿ ìîäåëèðîâàíèÿ ìàøèíû Òüþðèíãà, ðàáîòàþùåé â àëôàâèòå A ={0, 1, a2 , . . . , ak }, ÷ðåçâû÷àéíî ïðîñòà. Íåîáõîäèìî çàêîäèðîâàòü áóêâû74àëôàâèòà A ñëîâàìè â àëôàâèòå {0, 1} è çàòåì îïåðèðîâàòü ñ ýòèìèêîäàìè òàê æå, êàê èñõîäíàÿ ìàøèíà Òüþðèíãà îïåðèðóåò ñ áóêâàìè0, 1, a2 , . . . , ak .Èç áîëüøîãî êîëè÷åñòâî ðàçíîîáðàçíûõ êîäèðîâàíèé ìû âûáåðåìáëî÷íîå (ðàâíîìåðíîå) êîäèðîâàíèå, êîãäà êàæäîé áóêâå àëôàâèòà Añîïîñòàâëÿåòñÿ äâîè÷íîå ñëîâî (áëîê) îäíîé è òîé æå äëèíû l.
Ïîíÿòíî, ÷òî äëÿ îäíîçíà÷íîñòè ïîñëåäóþùåãî äåêîäèðîâàíèÿ ÷èñëî l äîëæíîóäîâëåòâîðÿòü íåðàâåíñòâó 2l > k + 1. Òåïåðü êàæäîé áóêâå a àëôàâèòàA ìîæíî ñîïîñòàâèòü äâîè÷íîå ñëîâî ν(a) äëèíû l, ïðè÷åì ðàçíûì áóêâàì a ðàçëè÷íûå ñëîâà ν(a).  äàëüíåéøåì íàì áóäåò óäîáíî ñ÷èòàòü,÷òî êîäèðîâàíèå ν ñòàâèò â ñîîòâåòñòâèå áóêâå 0 ñëîâî èç l íóëåé, à áóêâå1 ñëîâî èç l åäèíèö.Ïóñòü M ïðîèçâîëüíàÿ ìàøèíà Òüþðèíãà ñ ëåíòî÷íûì àëôàâèòîìA è ìíîæåñòâîì ñîñòîÿíèé {q0 , q1 , . . .
, qr }. Ìû õîòèì ñíà÷àëà âûïîëíèòüöåíòðàëüíóþ ÷àñòü ìîäåëèðîâàíèÿ ðàáîòû ìàøèíû M ïîñòðîèòü ìàøèíó Òüþðèíãà M1 ñ ëåíòî÷íûì àëôàâèòîì {0, 1}, êîòîðàÿ ðàáîòàåòíàä êîäàìè ñëîâ òàê æå, êàê ìàøèíà M ðàáîòàåò íàä èñõîäíûìè ñëîâàìè â àëôàâèòå A.
Ñ ýòîé öåëüþ ê ñîñòîÿíèÿì q0 , q1 , . . . , qr ìàøèíû Mäîáàâèì åùå òðè ãðóïïû ñîñòîÿíèé.Ñîñòîÿíèÿ ïåðâîé ãðóïïû áóäåì äëÿ íàãëÿäíîñòè çàïèñûâàòü â âèäå[b1 . . . bp , j], ãäå 1 6 p 6 l, 1 6 j 6 r è b1 , . . . , bp ñèìâîëû 0 èëè 1. Âñîñòîÿíèÿõ ïåðâîé ãðóïïû ìàøèíà M1 ïðîâîäèò ¾ðàñøèôðîâêó¿ êîäîâν(a), ¾ïîìíÿ¿ ïðè ýòîì òåêóùåå ñîñòîÿíèå ìàøèíû M.Ïðåäïîëîæèì, ÷òî â íåêîòîðûé ìîìåíò âðåìåíè ìàøèíà M1 , ìîäåëèðóÿ ðàáîòó ìàøèíû M, íàõîäèòñÿ â ñîñòîÿíèè qj (òàê æå, êàê è ìàøèíàM), à åå ãîëîâêà îáîçðåâàåò ïåðâóþ áóêâó êîäà íåêîòîðîé áóêâû àëôàâèòà A.
Òîãäà ñëåäóþùèå êîìàíäû â ïðîãðàììå ìàøèíû M1 îáåñïå÷èâàþò÷òåíèå ýòîãî êîäà:bqj → bR[b, j],b[b1 . . . bp , j] → bR[b1 . . . bp b, j] (1 6 p 6 l − 2),b[b1 . . . bl−1 , j] → bS[b1 . . . bl−1 b, j](çäåñü b, bi ñèìâîëû 0 èëè 1).Ïóñòü òåïåðü â ïðîãðàììå ìàøèíû M èìååòñÿ êîìàíäà (4.1), ν(ai ) =b1 . . . bl , ν(ar ) = c1 . . . cl è ìàøèíà M1 â íåêîòîðûé ìîìåíò âðåìåíè íàõîäèòñÿ íà ïîñëåäíåé áóêâå bl êîäà ν(ai ) â ñîñòîÿíèè [b1 . . . bl , j]. Ñîñòîÿíèÿâòîðîé ãðóïïû, êîòîðûå ìû îáîçíà÷èì êàê [b1 .
. . bp , i, j], ïðåäíàçíà÷åíûäëÿ ìîäåëèðîâàíèÿ ¾ïîëîâèíû¿ âûïîëíåíèÿ ìàøèíîé M êîìàíäû (4.1),75êîòîðîå ñîñòîèò â çàìåíå êîäà b1 . . . bl êîäîì c1 . . . cl . Ñ ýòèìè ñîñòîÿíèÿìè ñâÿçàíû ñëåäóþùèå êîìàíäû ïðîãðàììû ìàøèíû M1 :bl [b1 . . . bl , j] → cl L[b1 . . . bl−1 , i, j],bp [b1 . . . bp , i, j] → cp L[b1 . . . bp−1 , i, j] (2 6 p 6 l − 1),b1 [b1 , i, j] → c1 S{D, s}(çäåñü ñèìâîëû D, s âçÿòû èç ïðàâîé ÷àñòè êîìàíäû (4.1), à {D, s} åñòüîáîçíà÷åíèå íîâîãî ñîñòîÿíèÿ, êîòîðîå ìû îòíåñåì ê òðåòüåé ãðóïïå).Òåïåðü, íàõîäÿñü â ñîñòîÿíèè {D, s}, ìàøèíà M1 äîëæíà ïðîìîäåëèðîâàòü âûïîëíåíèå îñòàâøåéñÿ ÷àñòè êîìàíäû (4.1), ò.å. M1 äîëæíàñäâèíóòüñÿ íà l êëåòîê âëåâî (åñëè D = L) èëè âïðàâî (åñëè D = R) èïåðåéòè â ñîñòîÿíèå qs .
 ñëó÷àå D = S ìàøèíà M1 , íå ñäâèãàÿ ãîëîâêó,ñðàçó ïåðåõîäèò â ñîñòîÿíèå qs . Äëÿ âûïîëíåíèÿ ýòèõ äåéñòâèé ñëóæàòñîñòîÿíèÿ òðåòüåé ãðóïïû è ñîîòâåòñòâóþùèå êîìàíäû:b{L, s} → bL{L, s, 1}, b{L, s, p} → bL{L, s, p + 1} (1 6 p 6 l − 1),b{L, s, l} → bSqs ;b{R, s} → bR{R, s, 1}, b{R, s, p} → bR{R, s, p + 1} (1 6 p 6 l − 1),b{R, s, l} → bRqs ;b{S, s} → bSqs .×òîáû ïîëíîñòüþ ïðîìîäåëèðîâàòü ðàáîòó ìàøèíû M, íåîáõîäèìîîïðåäåëèòü åùå äâå ìàøèíû Òüþðèíãà M0 è M2 . Ìàøèíà M0 ¾ðàñòÿãèâàåò¿ îñíîâíîé êîä èñõîäíîãî íàáîðà â l ðàç, à ìàøèíà M2 , íàîáîðîò, ¾ñæèìàåò¿ îñíîâíîé êîä ÷èñëà â l ðàç. Ïîñêîëüêó äåéñòâèÿ ìàøèíM0 , M2 â èçâåñòíîì ñìûñëå îáðàòíû äðóã äðóãó, ìû ðàññìîòðèì ëèøüìàøèíó M0 .Èòàê, ìàøèíà M0 äîëæíà ¾ðàñòÿíóòü¿ îñíîâíîé êîä ëþáîãî íàáîðàâ l ðàç. Ýòî çíà÷èò, ÷òî êàæäàÿ åäèíèöà îñíîâíîãî êîäà äîëæíà áûòüçàìåíåíà l åäèíèöàìè, à êàæäûé íóëü, ñòîÿùèé ìåæäó ìàññèâàìè èçåäèíèö, l íóëÿìè.
Äëÿ ïðîñòîòû îãðàíè÷èìñÿ ñëó÷àåì, êîãäà ìàøèíàM âû÷èñëÿåò ôóíêöèþ îò îäíîé ïåðåìåííîé.Ìàøèíó Òüþðèíãà M0 ìîæíî ïðåäñòàâèòü â âèäå êîìïîçèöèè è èòåðàöèè ñëåäóþùèõ ìàøèí M3 M6 . Ìàøèíà M3 , íàõîäÿñü íà ïåðâîéåäèíèöå îñíîâíîãî êîäà ÷èñëà x, ñäâèãàåòñÿ âïðàâî íà îäíó êëåòêó èàíàëèçèðóåò ñîäåðæàùèéñÿ â íåé ñèìâîë a. Åñëè a = 0, òî çàïóñêàåòñÿìàøèíà M4 , êîòîðàÿ äîïèñûâàåò ê èìåþùåéñÿ íà ëåíòå åäèíèöå åùål − 1 åäèíèö è îñòàíàâëèâàåòñÿ. Åñëè a = 1, òî çàïóñêàåòñÿ ìàøèíà M5 ,êîòîðàÿ ñòèðàåò ïåðâóþ åäèíèöó îñíîâíîãî ìàññèâà, ñäâèãàåòñÿ âëåâî íà76îäíó êëåòêó è çàïèñûâàåò ìàññèâ èç l åäèíèö.
Äàëåå äåéñòâóåò ìàøèíàM6 , êîòîðàÿ áóäåò ïîäâåðãíóòà èòåðàöèè.Ìàøèíà M6 ïðîáåãàåò ñëåâà íàïðàâî ìàññèâ èç åäèíèö, çàòåì ìàññèâèç íóëåé, âñòðå÷àåò ïåðâóþ åäèíèöó ñëåäóþùåãî ìàññèâà è àíàëèçèðóåò ñèìâîë a, ñòîÿùèé íåïîñðåäñòâåííî ñïðàâà îò ýòîé åäèíèöû. Åñëèa = 1, òî ñòèðàåòñÿ ïåðâàÿ åäèíèöà âòîðîãî ìàññèâà, ìàøèíà M6 äâèæåòñÿ äàëåå íàëåâî, ïðîáåãàåò ìàññèâ èç íóëåé, çàòåì ìàññèâ èç åäèíèöè ïðèïèñûâàåò ê ïîñëåäíåìó ìàññèâó ñëåâà íîâûå l åäèíèö. Ïîñëå ÷åãîM6 ïåðåõîäèò â íà÷àëüíîå ñîñòîÿíèå (öèêë èòåðàöèè). Åñëè æå a = 0,òî ìàøèíà M6 äåéñòâóåò àíàëîãè÷íî äî ìîìåíòà ïåðåõîäà â íà÷àëüíîåñîñòîÿíèå.
Ïîñëå ÷åãî ìàøèíà M6 äîëæíà çàâåðøèòü ðàáîòó â çàêëþ÷èòåëüíîì ñîñòîÿíèè.Ïîñòðîåíèå ìàøèí M3 M6 íå ïðåäñòàâëÿåò áîëüøîé òðóäíîñòè, èìû åãî îïóñêàåì.ÓÏÐÀÆÍÅÍÈß7.Ïîñòðîèòü ïðîãðàììó ìàøèíû Òüþðèíãà M6 . 4. Îïåðàöèè ñóïåðïîçèöèè, ïðèìèòèâíîé ðåêóðñèè èìèíèìèçàöèèÄëÿ áîëåå ãëóáîêîãî èçó÷åíèÿ êëàññà ôóíêöèé, âû÷èñëèìûõ íà ìàùèíàõ Òüþðèíãà, íàì íåîáõîäèìî ââåñòè òðè îïåðàöèè íàä (âîîáùå ãîâîðÿ,÷àñòè÷íûìè) ôóíêöèÿìè.Ñ îïåðàöèåéìû óæå ïîçíàêîìèëèñü â ïðåäûäóùèõ ãëàâàõ. Çäåñü íàì áóäåò äîñòàòî÷íî ðàññìàòðèâàòü ñóïåðïîçèöèþ äîâîëüíîñïåöèàëüíîãî âèäà ¾ðåãóëÿðíóþ¿ ñóïåðïîçèöèþ.
Ïóñòü èìåþòñÿ ôóíêöèèñóïåðïîçèöèèg0 (y1 , . . . , ym ), g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn ).(4.2)Îáðàçóåì èç íèõ ôóíêöèþ f :f (x1 , . . . , xn ) = g0 (g1 (x1 , . . . , xn ), . . . , gm (x1 , . . . , xn )).(4.3)Î ôóíêöèè f áóäåì ãîâîðèòü, ÷òî îíà ïîëó÷åíà èç ôóíêöèé (4.2) ñ ïîìîùüþ(èëè êîðî÷å:(4.3)).Ïîñêîëüêó â äàëüíåéøåì íàì ïðèäåòñÿ ïðèìåíÿòü îïåðàöèþ ñóïåðïîçèöèè ê ÷àñòè÷íî îïðåäåëåííûì ôóíêöèÿì, íåîáõîäèìî óòî÷íèòü, êàêäåéñòâóåò îïåðàöèÿ ñóïåðïîçèöèè â ýòîì ñëó÷àå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
