1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 13
Текст из файла (страница 13)
äëÿ ëþáîãî íàáîðà x1 , . . . , xk ∈ N òàêîãî, ÷òî çíà÷åíèå f (x1 , . . . , xk )îïðåäåëåíî, âûïîëíÿåòñÿ0q1 1x1 +1 0 . . . 01xk +1 0 VM 0q0 1f (x1 ,...,xk )+1 0 . . . 0.2. äëÿ ëþáîãî íàáîðà x1 , . . . , xk ∈ N òàêîãî, ÷òî çíà÷åíèå f (x1 , . . .
, xk )íå îïðåäåëåíî, ìàøèíà Òüþðèíãà M , íà÷àâ ñâîþ ðàáîòó ñ êîíôèãóðàöèè 0q1 1x1 +1 0 . . . 01xk +1 0, íèêîãäà íå îñòàíîâèòñÿ ïðàâèëüíî(òî åñòü, ëèáî ïðîèçîéäåò íåïðàâèëüíàÿ îñòàíîâêà M ëèáî Mâîîáùå íèêîãäà íå îñòàíîâèòñÿ).Ìû ãîâîðèì, ÷òî ÷àñòè÷íàÿ ôóíêöèÿ ïðàâèëüíî âû÷èñëèìà íà ìàøèíåÒüþðèíãà, åñëè íåêîòîðàÿ ìàøèíà Òüþðèíãà åå ïðàâèëüíî âû÷èñëÿåò.Íàïðèìåð, ôóíêöèÿ f (x) = x + 1 ïðàâèëüíî âû÷èñëèìà íà ìàøèíåÒüþðèíãà ñî ñëåäóþùåé ïðîãðàììîé:q1 1 → q1 1R, q1 0 → q2 1L, q2 1 → q2 1L, q2 0 → q0 0R.Óïðàæíåíèå. Óáåäèòüñÿ, ÷òî ýòî èìåííî òàê.74Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÒåîðåìà 3.5.2 Êëàññ ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà, ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.Ìû íå áóäåì ïðèâîäèòü äîêàçàòåëüñòâî ýòîé òåîðåìû. Áóäó÷è âåñüìà ãðîìîçäêî òåõíè÷åñêè, îíî âåñüìà ïðîñòî ïî ñâîåé èäåå è ñëåäóåò òîéæå ñàìîé ñõåìå, ÷òî è äîêàçàòåëüñòâî ñîâïàäåíèÿ êëàññîâ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé è ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ ؼíôèëäà.Ïîäðîáíîå èçëîæåíèå äîêàçàòåëüñòâà ìîæíî íàéòè â [2].Ìû äàäèì îäíàêî, èäåþ äîêàçàòåëüñòâà. Òàê ÷òîáû äîêàçàòü, ÷òî ëþáàÿ ÷àñòè÷íîðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà íà ìàøèíå Òüþðèíãà, äîñòàòî÷íî ïðîâåðèòü, ÷òîâñå ïðîñòåéøèå ôóíêöèè âû÷èñëèìû íà ìàøèíå Òüþðèíãà, è ÷òî ïðèìåíåíèå îïåðàòîðîâ S, R, M ê ôóíêöèÿì, âû÷èñëèìûì íà ìàøèíàõ Òüþðèíãà ñíîâà äàåò ôóíêöèè,âû÷èñëèìûå íà ìàøèíå Òüþðèíãà. Ýòî òðåáóåò íàïèñàíèÿ ðÿäà ïðîãðàìì.Ïðèâåäåì ñõåìó äîêàçàòåëüñòâà òåîðåìû â äðóãóþ ñòîðîíó, òî åñòü äîêàæåì, ÷òîëþáàÿ âû÷èñëèìàÿ íà ìàøèíå Òüþðèíãà ôóíêöèÿ ÷àñòè÷íî ðåêóðñèâíà.Îïðåäåëèì êîäèðîâàíèå ïðîãðàìì äëÿ ìàøèí Òüþðèíãà ñëåäóþùèì îáðàçîì.Ïóñòüêîä (Λ) = 0, êîä (L) = 1, êîä (R) = 2 èêîä (qi aj → qk al S) = hi, j, k, l, êîä (S)i .Òîãäà êîä ïðîãðàììû, ñîñòîÿùåé èç êîìàíä c1 , .
. . , cs îïðåäåëèì, êàê íàòóðàëüíîå÷èñëî hêîä (c1 ), . . . , êîä (cs )i. Íàçîâåì êîäîì êîíôèãóðàöèè ìàøèíû Òüþðèíãà, îïèñûâàåìîé ñëîâîì ai1 , . . . , qj aip , . . . , air ÷èñëî hi1 , . . . , ip , . . . , ir , j, pi. Äëÿ íàñ çäåñü âàæíî,÷òî ñàìà êîíôèãóðàöèÿ îäíîçíà÷íî âîññòàíàâëèâàåòñÿ ïî åå êîäó.
Ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé w0 , w1 , . . . , wu , â êîòîðûõ ïîñëåäîâàòåëüíî íàõîäèòñÿ ìàøèíàM,w 0 ⇒ M w1 ⇒ M . . . ⇒ M w uíàçîâåì âû÷èñëåíèåì åñëè â ïîñëåäíåé êîíôèãóðàöèè wu ñîäåðæèòñÿ çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 , òî åñòü âû÷èñëåíèå ïðàâèëüíî çàêîí÷èëîñü íà êîíôèãóðàöèè wu .Êîäîì âû÷èñëåíèÿ w0 , w1 , . . . , wu íàçîâåì ÷èñëîhêîä (w0 ), êîä (w1 ), . . . , êîä (wu )i .Äàëåå äîêàçûâàåòñÿ, ÷òî îòíîøåíèåTk0 (e, x1 , .
. . , xk , y) y êîä âû÷èñëåíèÿ íà ìàøèíå Òüþðèíãà ñ ïðîãðàììîé, íîìåð êîòîðîé ðàâåí e, íà÷àòîãî â êîíôèãóðàöèè 0q1 1x1 +1 0 . . . 01xk +1 0ðåêóðñèâíî, è ÷òîñóùåñòâóåò îáùåðåêóðñèâíàÿ ôóíêöèÿ U1 (y), êîòîðàÿ ïî ëþáîìó êîäó yâû÷èñëåíèÿ, îêàí÷èâàþùåãîñÿ íà êîíôèãóðàöèþ âèäà 0q0 1z+1 0β âûäàåòðåçóëüòàò ýòîãî âû÷èñëåíèÿ z(Åñëè âñïîìíèòü îïðåäåëåíèå âû÷èñëèìîñòè ôóíêöèè íà ìàøèíå Òüþðèíãà, òî ìîæíî óâèäåòü, ÷òî U1 (y) ðàâíî ðåçóëüòàòó âû÷èñëåíèÿ y ). Òåïåðü îñòàåòñÿ çàìåòèòü, ÷òîäëÿ ëþáîé âû÷èñëèìîé íà ìàøèíå Òüþðèíãà ïî ïðîãðàììå ñ íîìåðîì e ÷àñòè÷íîéôóíêöèè f : Nk → N ñïðàâåäëèâî ðàâåíñòâî:f (x1 , . . .
, xk ) ' U1 (µyTk0 (e, x1 , . . . , xk , y)).3.5. Ìàøèíû Òüþðèíãà75Îòñþäà ñëåäóåò, ÷òî ëþáàÿ âû÷èñëèìàÿ íà ìàøèíå Òüþðèíãà ôóíêöèÿ ÷àñòè÷íîðåêóðñèâíà. ¤Óïðàæíåíèÿ.1. Íàïèñàòü ïðîãðàììû ìàøèí Òüþðèíãà R0 , R1 , L0 , L1 òàêèõ, ÷òîäëÿ âñåõ x ∈ N ñïðàâåäëèâîq1 1x 0 VR0 1x q0 0 (ïîèñê 0 âïðàâî)q1 0x 1 VR1 0x q0 1 (ïîèñê 1 âïðàâî)10x q1 0 VL1 q0 10x 0 (ïîèñê 1 âëåâî)01x q1 1 VL0 q0 01x 1 (ïîèñê 0 âëåâî)2. Íàïèñàòü ïðîãðàììû äëÿ ìàøèíû Òüþðèíãà M+ , êîòîðàÿ, íà÷àâñâîþ ðàáîòó â ëþáîé êîíôèãóðàöèè â ñîñòîÿíèè q1 ñäâèãàåò ãîëîâêó íà îäíó ÿ÷åéêó âïðàâî è ïîñëå ýòîãî îñòàíàâëèâàåòñÿ.3. Íàïèñàòü ïðîãðàììû äëÿ ìàøèíû Òüþðèíãà M− , êîòîðàÿ, íà÷àâñâîþ ðàáîòó â ëþáîé êîíôèãóðàöèè â ñîñòîÿíèè q1 ñäâèãàåò ãîëîâêó íà îäíó ÿ÷åéêó âëåâî è ïîñëå ýòîãî îñòàíàâëèâàåòñÿ.4.
Óêàçàòü ìåòîä, ïîçâîëÿþùèé ïî ëþáûì äâóì ìàøèíàì ÒüþðèíãàM0 è M1 ïîëó÷àòü íîâóþ ìàøèíó Òüþðèíãà M òàêóþ, ÷òî äëÿëþáûõ ñëîâ α0 , α1 , β0 , β1 , γ0 , γ1 , åñëèα0 q1 α1 VM0 β0 q0 β1èβ0 q1 β1 VM1 γ0 q0 γ1 ,òîα0 q1 α1 VM γ0 q0 γ1 .Åñëè æå ðåçóëüòàò ðàáîòû õîòÿ áû îäíîé èç ìàøèí íåîïðåäåëåí,òî è ðåçóëüòàò ðàáîòû ìàøèíû M íå îïðåäåëåí. Ïîëó÷èâøóþñÿâ ðåçóëüòàòå ìàøèíó M íàçîâåì êîìïîçèöèåé ìàøèí M0 è M1 èáóäåì îáîçíà÷àòü M0 · M1 .Óêàçàíèå. Çàìåíèì â ïðîãðàììå ìàøèíû M1 âñå âõîæäåíèÿ ñîñòîÿíèé q1 , q2 ,. .
. (èñêëþ÷àÿ çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 ) ñîîòâåòñòâåííî íà íîâûå ñîñòîÿíèÿ q10 , q20 , . . ., íå âñòðå÷àþùèåñÿ â ïðîãðàììå ìàøèíû M0 . Çàòåì çàìåíèì âïðîãðàììå ìàøèíû M0 âñå âõîæäåíèÿ ñîñòîÿíèÿ q0 íà q10 . Îáúåäèíèì ïîëó÷åííûå ïðîãðàììû. Ïîëó÷åííàÿ ïðîãðàììà ñíà÷àëà áóäåò ðàáîòàòü òàê, êàêåñëè áû ýòî áûëà ìàøèíà M0 . Òàê áóäåò ïðîäîëæàòüñÿ äî òåõ ïîð, ïîêà M076Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàíå ïîïàäåò â ñîñòîÿíèå q0 . Íàøà æå ïðîãðàììà â ýòîò ìîìåíò ïîïàäåò â ñîñòîÿíèå q10 è ïðîäîëæèò ðàáîòó òàê, êàê åñëè áû ýòî áûëà ïðîãðàììà M1 ñòîé ëèøü ðàçíèöåé, ÷òî âìåñòî ñîñòîÿíèé qi íàøà ìàøèíà áóäåò íàõîäèòñÿ âòå æå ìîìåíòû âðåìåíè â ñîñòîÿíèÿõ qi0 . Çàòåì íàøà ìàøèíà îñòàíîâèòñÿ âçàêëþ÷èòåëüíîì ñîñòîÿíèè q0 , ïðîäåëàâ ðàáîòó ìàøèíû M1 .5. Óêàçàòü ìåòîä, ïîçâîëÿþùèé ïî ëþáûì äâóì ìàøèíàì ÒüþðèíãàM0 , M1 è M2 ïîëó÷àòü íîâóþ ìàøèíó Òüþðèíãà M , êîòîðàÿ äëÿëþáûõ α0 è α1 äåëàåò òî æå ñàìîå, ÷òî è ñëåäóþùàÿ ïðîöåäóðà:çàïóñêàåì M0 èç êîíôèãóðàöèè α0 q1 α1 . Åñëè α0 q1 α1 VM0 β0 q0 β1 , èïðè ýòîì óêàçàòåëü íàõîäèòñÿ íàä 0, òî çàïóñêàåì M1 èç êîíôèãóðàöèè β0 q1 β1 , åñëè æå íå íàä 0, òî çàïóñêàåì M2 èç òîé æå êîíôèãóðàöèè.
Ïîëó÷åííûé òàêèì îáðàçîì ðåçóëüòàò ðàâåí ðåçóëüòàòóðàáîòû ìàøèíû M . Åñëè õîòÿ áû îäíà èç çàïóùåííûõ ïðè ýòîììàøèí íå äàåò ðåçóëüòàòà, òî è M íå âûäàåò íèêàêîãî ðåçóëüòàòà.Óêàçàíèå. Äåéñòâóéòå â äóõå ðåøåíèÿ ïðåäûäóùåé çàäà÷è.6.∗Äîêàçàòü ñóùåñòâîâàíèå ìàøèíû Òüþðèíãà, îñóùåñòâëÿþùåéêîïèðîâàíèå íåòðèâèàëüíûõ ìàññèâîâ èç 1, à èìåííî, òàêîé, ÷òîäëÿ ëþáîãî x ∈ N âûïîëíåíî0q1 1x+1 0 V 0q0 1x+1 01x+1 0.Âàæíî çàìåòèòü, ÷òî èç ýòîãî óñëîâèÿ ñëåäóåò, ÷òî ìàøèíà íå äîñòðàèâàåò ÿ÷ååê íè ñëåâà íè ñïðàâà.Óêàçàíèå.
Ñì. [2].7.∗Äîêàçàòü ñóùåñòâîâàíèå ìàøèíû Òüþðèíãà, îñóùåñòâëÿþùåé ïåðåñòàíîâêó íåòðèâèàëüíûõ ìàññèâîâ èç 1, à èìåííî, òàêîé, ÷òî äëÿëþáûõ x, y ∈ N âûïîëíåíî0q1 1x+1 01y+1 0 V 0q0 1y+1 01x+1 0.Âàæíî çàìåòèòü, ÷òî èç ýòîãî óñëîâèÿ ñëåäóåò, ÷òî ìàøèíà íå äîñòðàèâàåò ÿ÷ååê íè ñëåâà íè ñïðàâà.Óêàçàíèå. Ñì. [2].8.∗Äîêàçàòü, ÷òî ëþáàÿ ÷àñòè÷íî ðåêóðñèâíàÿ ôóíêöèÿ ïðàâèëüíîâû÷èñëèìà íà ìàøèíå Òüþðèíãà. Äëÿ ýòîãî äîêàæèòå, ÷òî âñå ïðîñòåéøèå ôóíêöèè ïðàâèëüíî âû÷èñëèìû íà ìàøèíå Òüþðèíãà, à3.6. Íîðìàëüíûå àëãîðèôìû Ìàðêîâà77òàêæå, ÷òî ðåçóëüòàò ïðèìåíåíèÿ îïåðàòîðîâ S , R è M ê ôóíêöèÿì, ïðàâèëüíî âû÷èñëèìûì íà ìàøèíå Òüþðèíãà òîæå ïðàâèëüíîâû÷èñëèìû íà ìàøèíå Òüþðèíãà.Óêàçàíèå.
Ñì. [2].9.∗Ïóñòü A íåïóñòîé êîíå÷íûé àëôàâèò. Ïðåäïîëàãàåòñÿ, ÷òî/ A.0, 1, (, ), ∗, ¤ ∈Îáîçíà÷èì A0 = A ∪ {0, 1, (, ), ∗, ¤}. Äîêàçàòü ñóùåñòâîâàíèå ìàøèíû Òüþðèíãà M , ðàñïîçíàþùåé ðåãóëÿðíûå âûðàæåíèÿ íàä A,à èìåííî, òàêîé ìàøèíû, ÷òî åñëè w ∈ (A0 )∗ ðåãóëÿðíîå âûðàæåíèå íàä A, òîq1 ¤w¤ VM q0 1,à åñëè w ∈ (A0 )∗ íå ðåãóëÿðíîå âûðàæåíèå íàä A, òîq1 ¤w¤ VM q0 0.3.6 Íîðìàëüíûå àëãîðèôìû ÌàðêîâàÍîðìàëüíûå àëãîðèôìû Ìàðêîâà åùå îäíà èç ôîðìàëèçàöèé ïîíÿòèÿâû÷èñëèìîñòè. Óïîòðåáëåíèå áóêâû `ô' â ýòîì ñëîâå äàíü òðàäèöèè. ýòîì ïîäõîäå èñïîëüçîâàíà ïðîñòàÿ èäåÿ î òîì, ÷òî ëþáîå äàííîå èëèíàáîð äàííûõ, ó÷àñòâóþùèå â âû÷èñëåíèÿõ, ìîãóò áûòü â êîíöå êîíöîâçàïèñàíû â âèäå íåêîòîðûõ òåêñòîâ, è äàæå â âèäå öåïî÷åê ñèìâîëîâ, òîåñòü ñëîâ (åñëè ñ÷èòàòü ïðîáåëû ìåæäó ñëîâàìè è ñèìâîëû, îáîçíà÷àþùèå ïåðåõîä íà íîâóþ ñòðîêó, ïîëíîïðàâíûìè ñèìâîëàìè àëôàâèòà),à ñàì àëãîðèòì ìîæåò áûòü ðàññìîòðåí, êàê ïðîöåññ ïðåîáðàçîâàíèÿòàêèõ ñëîâ.Íîðìàëüíûé àëãîðèôì Ìàðêîâà íàä àëôàâèòîì A ýòî êîíå÷íûéóïîðÿäî÷åííûé íàáîð ðåäóêöèé ñëåäóþùèõ äâóõ âèäîâ: α → β (îáû÷íàÿðåäóêöèÿ) è α →• β , ãäå α, β ∈ A∗ (çàêëþ÷èòåëüíàÿ ðåäóêöèÿ).Ïóñòü w ∈ A∗ .
Åñëè ðåäóêöèÿ α → β èëè α → • β òàêîâà, ÷òî ååëåâàÿ ÷àñòü α ÿâëÿåòñÿ ïîäñëîâîì w, òî ìû ãîâîðèì, ÷òî ýòà ðåäóêöèÿïðèìåíèìà ê w, è îïðåäåëÿåì ðåçóëüòàò w0 åå ïðèìåíåíèÿ ê ñëîâó w,êàê ðåçóëüòàò çàìåíû ñàìîãî ëåâîãî âõîæäåíèÿ α â w íà ïîäñëîâî β . Ìûáóäåì çàïèñûâàòü ýòî òàê: w →A w0 .  ïðîòèâíîì ñëó÷àå áóäåì ãîâîðèòü,÷òî äàííàÿ ðåäóêöèÿ íå ïðèìåíèìà ê ñëîâó w.Ïðèìåð. Ïóñòü A = 00 → 1. Òîãäà 002200 →A 12200.78Ãëàâà 3.
Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÍîðìàëüíûé àëãîðèôì A ïðåîáðàçóåò ñëîâî w ∈ A ïî øàãàì ñëåäóþùèì îáðàçîì:ñíà÷àëà èùåì ñàìóþ ïåðâóþ ðåäóêöèþ â óïîðÿäî÷åííîì ñïèñêå A, êîòîðàÿ ïðèìåíèìà ê w è ïðèìåíÿåì åå, ïîëó÷èâ íîâîåñëîâî w0 . Åñëè óïîìÿíóòàÿ ðåäóêöèÿ ÿâëÿåòñÿ çàêëþ÷èòåëüíîé, òî ïðîöåññ íà ýòîì îñòàíàâëèâàåì, åñëè íåò, òî ñíîâàèùåì ñàìóþ ïåðâóþ ðåäóêöèþ â óïîðÿäî÷åííîì ñïèñêå A,êîòîðàÿ ïðèìåíèìà ê ïîëó÷åííîìó ðåçóëüòàòó, ïðèìåíÿåì ååê w0 è ò.ä.Ýòîò ïðîöåññ ìîæåò çàêîí÷èòñÿ ïî îäíîé èç äâóõ ïðè÷èí: ëèáî áóäåò âûïîëíåíà çàêëþ÷èòåëüíàÿ ðåäóêöèÿ ëèáî íå îäíà ðåäóêöèÿ èç Aíå áóäåò ïðèìåíèìà ê ïîëó÷åííîìó â ðåçóëüòàòå ñëîâó.
 ýòîì ñëó÷àåáóäåì ãîâîðèòü, ÷òî ñàìîå ïîñëåäíåå èç ïîëó÷åííûõ ñëîâ w∗ åñòü ðåçóëüòàò ïðèìåíåíèÿ A ê w è çàïèñûâàòü ýòî òàê: A(w) = w∗ . Åñëè æåýòîò ïðîöåññ íèêîãäà íå çàêîí÷èòñÿ, òî áóäåì ãîâîðèòü, ÷òî íîðìàëüíûéàëãîðèôì A íå äàåò ðåçóëüòàòà íà w.Ïðèìåðû.1. Ïóñòü A = 0 → 11; 2 →• 0. Òîãäà 0020 →A 11020 →A 111120 →A111100 è A(0020) = 111100.2. Ïóñòü A = Λ → 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
