1610906281-d25a58898a45262b0b837c281ba962eb (824376), страница 9
Текст из файла (страница 9)
Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÌàøèííîå ñëîâî Aqi aj B ýòî ôîðìàëüíîå ïðåäñòàâëåíèå òåêóùåãî ïîëîæåíèÿâñåõ äåòàëåé ìàøèíû: qi òåêóùåå ñîñòîÿíèå, aj ñîäåðæèìîå ÿ÷åéêè, îáîçðåâàåìîé ãîëîâêîé â äàííûé ìîìåíò, ñëîâî A ñîñòîèò èç âñåõ ñèìâîëîâ, ñîäåðæàùèõñÿâ ÿ÷åéêàõ ñëåâà îò îáîçðåâàåìîé, ñëîâî B ñîñòîèò èç âñåõ ñèìâîëîâ, çàïèñàííûõ âÿ÷åéêàõ ñïðàâà îò îáîçðåâàåìîé. Èñõîäÿ èç òàêîãî èíòóèòèâíîãî ñìûñëà, íåñëîæíî îïðåäåëèòü ôîðìàëüíî, êàê ïðåîáðàçóþòñÿ ìàøèííûå ñëîâà çà îäèí øàã ðàáîòûìàøèíû.Ïóñòü M = Aqi aj B ìàøèííîå ñëîâî. Ãîâîðÿò, ÷òî ìàøèííîå ñëîâîMT , åñëè âûïîëíÿåòñÿîäíî èç óñëîâèé:Îïðåäåëåíèå.MT0ïîëó÷àåòñÿ èççà îäèí øàã ðàáîòû ìàøèíû Òüþðèíãà1) i = 0, MT0 = M .2) i > 0 è âûïîëíÿåòñÿ îäèí èç ñëó÷àåâ:à) T (i, j) èìååò âèä qi aj → qk al , è MT0 = Aqk al B ;á) T (i, j) èìååò âèä qi aj → qk al R, B = as B 0 , è MT0 = Aal qk as B 0 ;â) T (i, j) èìååò âèä qi aj → qk al R, B = Λ, è MT0 = Aal qk a0 (äîñòðàèâàåòñÿíîâàÿ ÿ÷åéêà ñïðàâà);ã) T (i, j) èìååò âèä qi aj → qk al L, A = A0 as , è MT0 = A0 qk as al B ;ä) T (i, j) èìååò âèä qi aj → qk al L, A = Λ, è MT0 = qk a0 al B (äîñòðàèâàåòñÿíîâàÿ ÿ÷åéêà ñëåâà).Îïðåäåëåíèå.(n)MT0(0)(n+1)Ïóñòü M = Aqi aj B ìàøèííîå ñëîâî.
Ïîëîæèì MT = M , MT=äëÿ âñåõ n ∈ ω .Ãîâîðÿò, ÷òî ìàøèíà TMM1(n), è ïèøóò M =⇒ M1 , åñëè ñóùåñòâóåò n ∈ ω òàêîå, ÷òî MT = M1 è ïðèÿ÷ååê ñëåâàïåðåðàáàòûâàåò ñëîâîâ ñëîâîáåç äîñòðàèâàíèÿTýòîì íå èñïîëüçóåòñÿ ïóíêò (ä).Ãîâîðÿò, ÷òî ìàøèíà TMM1(n), è ïèøóò M |=⇒ M1 , åñëè ñóùåñòâóåò n ∈ ω òàêîå, ÷òî MT = M1ÿ÷ååê ñëåâà è ñïðàâàïåðåðàáàòûâàåò ñëîâîâ ñëîâîáåç äîñòðàèâàíèÿTè ïðè ýòîì íå èñïîëüçóþòñÿ ïóíêòû (â) è (ä).âû÷èñëÿåòÃîâîðÿò, ÷òî ìàøèíà Òüþðèíãà T÷àñòè÷íóþ k -ìåñòíóþôóíêöèþ f : dom(f ) ⊆ ω k −→ ω , åñëè äëÿ ëþáûõ x1 , . . . , xk ∈ ω âûïîëíÿþòñÿóñëîâèÿ:Îïðåäåëåíèå.à) åñëè hx1 , .
. . , xk i ∈ dom(f ), òî q1 01x1 0 . . . 01xk 0 =⇒ q0 01f (x1 ,...,xk ) 00s , äëÿ íåêîòîTðîãî s > 0;á) åñëè hx1 , . . . , xk i ∈/ dom(f ), òî ìàøèíà T , íà÷àâ ðàáîòó ñ ìàøèííîãî ñëîâà M =(n)x1xkq1 01 0 . . . 01 0, ðàáîòàåò áåñêîíå÷íî, ò. å. q0 íå âõîäèò â MT íè äëÿ êàêîãîn ∈ ω.âû÷èñëèìîé ïî Òüþðèíãó×àñòè÷íàÿ ôóíêöèÿ f íàçûâàåòñÿ, åñëèñóùåñòâóåò ìàøèíà Òüþðèíãà T , êîòîðàÿ å¼ âû÷èñëÿåò.qiÎïðåäåëåíèå. Åñëè P ïðîãðàììà, òî ÷åðåç Páóäåì îáîçíà÷àòü ìíîæåñòâîqjêîìàíä, ïîëó÷åííûõ èç P çàìåíîé âñåõ âõîæäåíèé qi íà qj .Îïðåäåëåíèå. 11.
Áàçîâûå ìàøèíû Òüþðèíãà37Ïóñòü T1 = hA, Q1 , P1 , q1 , q0 i, T2 = hA, Q2 , P2 , q1 , q0 i ìàøèíû Òüþðèíãà ñ îäíèì è òåì æå âíåøíèì àëôàâèòîì A è àëôàâèòàìè âíóòðåííèõ ñîñòîÿíèéÎïðåäåëåíèå.Q1 = {q0 , q1 , . . . , qr },Q2 = {q0 , q1 , . . . , qs }.Êîìïîçèöèåé ìàøèí T1 è T2 íàçûâàåòñÿT1 ◦ T2 = hA, Q, P, q1 , q0 i, ãäå Q =q ìàøèíàq ,...,q{q0 , q1 , . . . , qr+s } è ïðîãðàììà P = P1 q0r+1 ∪ P2 q1r+1 ,...,qr+s .Êîìïîçèöèÿ T1 ◦ T2 ðàáîòàåò ñëåäóþùèì îáðàçîì. Íà âõîäíûõ äàííûõ ñíà÷àëàçàïóñêàåòñÿ ìàøèíà T1 . Çàòåì íà âûõîäíûõ äàííûõ T1 çàïóñêàåòñÿ ìàøèíà T2 .
Âûõîäíûå äàííûå T2 ñ÷èòàþòñÿ âûõîäîì äëÿ êîìïîçèöèè T1 ◦ T2 . Êîíå÷íîå ñîñòîÿíèåìàøèíû T1 îòîæäåñòâëÿåòñÿ ñ íà÷àëüíûì ñîñòîÿíèåì ìàøèíû T2 .sÏóñòü T1 =hA, Q1 , P1 , q1 , q0 i, T2 =hA, Q2 , P2 , q1 , q0 i, T3 =hA, Q3 , P3 , q1 , q0 i ìàøèíû Òüþðèíãà ñ îäíèì è òåì æå âíåøíèì àëôàâèòîì A è àëôàâèòàìè âíóòðåííèõ ñîñòîÿíèéÎïðåäåëåíèå.Q1 = {q0 , q1 , .
. . , qr },Q2 = {q0 , q1 , . . . , qs },Q3 = {q0 , q1 , . . . , qt }.Ðàçâåòâëåíèåì ìàøèíû T1 íà (T2, T3) ïî (qi, qj ), ãäå qi, qj ∈ Q1, íàçûâàåòñÿ ìàøèíàT1 [qi → T2 |qj → T3 ] = hA, Q, P, q1 , q0 i, ãäå Q = {q0 , q1 , . . . , qr+s+t−2 }, à ïðîãðàììà Pïîëó÷àåòñÿ ñëåäóþùèì îáðàçîì: èç P1 èñêëþ÷àþòñÿ âñå êîìàíäû âèäà qi ak → . . . èâèäà qj ak → . . .; ïîëó÷åííîå ìíîæåñòâî îáîçíà÷èì ÷åðåç P10 . Òîãäàq ,q2 ,...,qsq1 ,q2 ,...,qtP = P10 ∪ P2 q1i ,qr+1∪P.3,...,qr+s−1qj ,qr+s ,...,qr+s+t−2Ðàçâåòâëåíèå ðàáîòàåò ñëåäóþùèì îáðàçîì.
Íà âõîäíûõ äàííûõ çàïóñêàåòñÿ ìàøèíà T1 . Åñëè T1 ïîïàäàåò â ñîñòîÿíèå q0 , òî ïðîèñõîäèò îñòàíîâêà. Åñëè T1 ïîïàäàåòâ ñîñòîÿíèå qi , òî íà òåêóùèõ äàííûõ çàïóñêàåòñÿ ìàøèíà T2 , ïðè ýòîì íà÷àëüíîåñîñòîÿíèå ìàøèíû T2 çàìåíÿåòñÿ íà qi . Åñëè T1 ïîïàäàåò â ñîñòîÿíèå qj , òî íà òåêóùèõ äàííûõ çàïóñêàåòñÿ ìàøèíà T3 , ïðè ýòîì íà÷àëüíîå ñîñòîÿíèå ìàøèíû T3çàìåíÿåòñÿ íà qj . Êîíå÷íûå ñîñòîÿíèÿ ìàøèí T1 , T2 è T3 îòîæäåñòâëÿþòñÿ.Ñóùåñòâóåò íåñêîëüêî ìîäåðíèçàöèé è îáîáùåíèé ìàøèí Òüþðèíãà.Íàèáîëåå èçâåñòíîé è åñòåñòâåííîé ìîäåðíèçàöèåé ÿâëÿåòñÿ ìíîãîëåíòî÷íàÿ ìàøèíà Òüþðèíãà, ò.
å. ìàøèíà, êîòîðàÿ èìååò k (k > 1) ëåíò è òàêîå æå ÷èñëî ñ÷èòûâàþùèõ ãîëîâîê. Îäíàêî âû÷èñëèòåëüíûå âîçìîæíîñòè òàêèõ ìàøèí íå îòëè÷àþòñÿîò âîçìîæíîñòåé îáû÷íûõ ìàøèí Òüþðèíãà.Äðóãîå îáîáùåíèå íåäåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà, ò. å. ìàøèíû,â ïðîãðàììå êîòîðûõ äëÿ íåêîòîðûõ ñîñòîÿíèé qi è íåêîòîðûõ âíåøíèõ ñèìâîëîâaj ìîãóò ïðèñóòñòâîâàòü íåñêîëüêî ðàçëè÷íûõ êîìàíä, íà÷èíàþùèõñÿ ñ ñèìâîëîâqi aj → . . . Ìàøèíû òàêîãî òèïà èñïîëüçóþñÿ â êà÷åñòâå òðàäèöèîííîé ìîäåëè âû÷èñëåíèé â òåîðèè ñëîæíîñòè àëãîðèòìîâ [4], [5], [13].Çàìå÷àíèå. 11.Áàçîâûå ìàøèíû ÒüþðèíãàÄëÿ äîêàçàòåëüñòâà îñíîâíûõ ðåçóëüòàòîâ äàííîé ãëàâû íàì ïîòðåáóþòñÿ ñëåäóþùèé íàáîð òàê íàçûâàåìûõìàøèí Òüþðèíãà.Çàìåòèì, ÷òî åñëè ìàøèíà Òüþðèíãà â íåêîòîðîì ñîñòîÿíèè qi íèêîãäà íå îáîçðåâàåò ñèìâîë aj , òî êîìàíäó âèäà qi aj → . .
. ìîæíî íå ïèñàòü â ïðîãðàììå. Íèæåìû áóäåì èñïîëüçîâàòü äàííîå ñîãëàøåíèå äëÿ óïðîùåíèÿ çàïèñè ïðîãðàìì.áàçîâûõ38Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÏåðåíîñ íóëÿ À:q1 001x 0 |=⇒ q0 01x 00,Àãäå x > 0.Ìàøèíà À èìååò ñëåäóþùóþ ïðîãðàììó:q1 0 → q2 0Rq2 0 → q3 1Rq3 1 → q3 1Rq3 0 → q4 0Lq4 1 → q5 0Lq5 1 → q5 1Lq 5 0 → q0 0Ìàøèíà À ðàáîòàåò ñëåäóþùèì îáðàçîì. Ñíà÷àëà âòîðîé 0 çàìåíÿåòñÿ íà 1 (êîìàíäû q1 0 → q2 0R è q2 0 → q3 1R), çàòåì ìàøèíà ñäâèãàåòñÿ íà 0, ñòîÿùèé ïîñëåìàññèâà 1x (êîìàíäà q3 1 → q3 1R), è çàìåíÿåò ïîñëåäíèé ñèìâîë 1 èç ýòîãî ìàññèâàíà 0 (êîìàíäû q3 0 → q4 0L è q4 1 → q5 0L), ïîñëå ÷åãî ìàøèíà âîçâðàùàåòñÿ âëåâî íàñàìîå íà÷àëî (êîìàíäû q5 1 → q5 1L è q5 0 → q0 0).
Çàìåòèì, ÷òî íîâûå ÿ÷åéêè ñïðàâàè ñëåâà íå äîñòðàèâàþòñÿ.Îáíóëåíèå Î:q1 01x 0 |=⇒ q0 00x 0,Îãäå x > 0.Ìàøèíà Î èìååò ñëåäóþùóþ ïðîãðàììó:q1 0 → q2 0Rq2 1 → q2 1Rq2 0 → q3 0L+Ïðàâûé ñäâèã Á :q1 01x 0 |=⇒ 01x q0 0,Á+q3 1 → q3 0Lq 3 0 → q0 0ãäå x > 0.Ïðîãðàììà äëÿ ìàøèíû Á+ ñîñòîèò èç òð¼õ êîìàíä:q1 0 → q2 0Rq2 1 → q2 1Rq2 0 → q 0 0−Ëåâûé ñäâèã Á :01x q1 0 |=⇒ q0 01x 0,Á−ãäå x > 0.Ïðîãðàììà äëÿ ìàøèíû Á− ñîñòîèò èç òð¼õ êîìàíä:q1 0 → q2 0Lq2 1 → q2 1Lq2 0 → q 0 0Òðàíñïîçèöèÿ Â:01x q1 01y 0 |=⇒ 01y q0 01x 0,Âãäå x, y > 0.Ìàøèíà  ðàáîòàåò ñëåäóþùèì îáðàçîì. Ñíà÷àëà ïðåîáðàçóåì ñëîâî 01x q1 01y 0â ñëîâî 01x q5 1y 00, ðàâíîå ñëîâó 01x−i q5 1y 01i 0 ïðè i = 0.
Çàòåì äëÿ ïðîèçâîëüíîãî iñëîâî 01x−i q5 1y 01i 0 ïðåîáðàçóåì â ñëîâî 01x−(i+1) q5 1y 01i+1 0, åñëè x − i > 0, è â ñëîâî01y q0 01x 0, åñëè x − i = 0.Ïðîãðàììà äëÿ  èìååò ñëåäóþùèé âèä:39 11. Áàçîâûå ìàøèíû Òüþðèíãàq1 0 → q2 0Rq2 1 → q2 1Rq2 0 → q3 0Lq3 1 → q4 0Lq3 0 → q 5 0q4 1 → q4 1Lq4 0 → q 5 1Ïðåîáðàçóåì âõîäíîå ìàøèííîåñëîâî ñëåäóþùèì îáðàçîì:01x q1 01y 0|=⇒ 01x q5 1y 00.q5 1 → q6 1Lq5 0 → q6 0L ñîñòîÿíèè q5 , â êîòîðîì íà÷èíàåòñÿ öèêë,ñäâèãàåìñÿ íà îäíó ÿ÷åéêó âëåâî è ïðîâåðÿåì,åñòü ëè åù¼ åäèíèöû â ìàññèâå 1x−i ,òî åñòü âåðíî ëè, ÷òî x − i = 0.q6 0 → q7 0Rq7 1 → q7 1Rq7 0 → q0 0q6 1 → q8 0Rq8 1 → q8 1Rq8 0 → q9 1Lq9 1 → q10 0Lq9 0 → q 5 0q10 1 → q10 1Lq10 0 → q5 1Åñëè x − i = 0, òî âûõîäèì èç öèêëà:q6 01y 01x 0|=⇒ 01y q0 01x 0.Åñëè x − i > 1 è y > 1, òî ïðåîáðàçóåì01x−(i+1) q6 11y 01i 0|=⇒ 01x−(i+1) q5 1y 01i+1 0.Åñëè x − i > 1 è y = 0, òî ïðåîáðàçóåì01x−(i+1) q6 101i 0|=⇒ 01x−(i+1) q5 01i+1 0.Ïîñëå ýòîãî ïåðåõîäèì ê ñëåäóþùåéèòåðàöèè â öèêëå.ãäåq1 01x 0 =⇒ q0 01x 01x 0,x > 0.ÃÌàøèíà à ðàáîòàåò ñëåäóþùèì îáðàçîì.
Ñíà÷àëà ïðåîáðàçóåì ñëîâî q1 01x 0 âñëîâî 0q2 1x 0, êîòîðîå ñîâïàäàåò ñî ñëîâîì 01i q2 1x−i 01i ïðè i = 0. Çàòåì äëÿ ïðîèçâîëüíîãî i ïðåîáðàçóåì ñëîâî 01i q2 1x−i 01i â ñëîâî 01i+1 q2 1x−(i+1) 01i+1 , åñëè x − i > 0,è ïðåîáðàçóåì â ñëîâî q0 01x 01x 0, åñëè x − i = 0.Ïðîãðàììà äëÿ à èìååò ñëåäóþùèé âèä:Óäâîåíèå Ã:q1 0 → q2 0Rq2 1 → q3 0Rq3 1 → q3 1Rq3 0 → q4 0Rq4 1 → q4 1Rq4 0 → q5 1Lq5 1 → q5 1Lq5 0 → q6 0Lq6 1 → q6 1Lq6 0 → q2 1Rq2 0 → q7 0Rq7 1 → q7 1Rq7 0 → q8 0Lq8 1 → q8 1Lq8 0 → q9 0Lq9 1 → q9 1Lq 9 0 → q0 0Åñëè x − i > 0, òî 01i q2 1x−i 01i =⇒=⇒ 01i 0q3 1x−(i+1) 01i =⇒ 01i 01x−(i+1) 01i q4 0 =⇒=⇒ 01i q6 01x−(i+1) 01i+1 =⇒ 01i+1 q2 1x−(i+1) 01i+1 ,è ïåðåõîäèì ê ñëåäóþùåé èòåðàöèè.Åñëè x − i = 0, òî 01x q2 01x =⇒=⇒ 01x 01x q7 0 =⇒ q0 01x 01x 0.Öèêëè÷åñêèé ñäâèã Ön :q1 01x1 01x2 0 .
. . 01xn 0 |=⇒ q0 01x2 0 . . . 01xn 01x1 0,ôèêñèðîâàííîå íàòóðàëüíîå ÷èñëî.Önãäå n > 1 40Ãëàâà III. Ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèèÌàøèíà Ön ðàáîòàåò ïî ñëåäóþùåé ñõåìå ñ èñïîëüçîâàíèåì áàçîâûõ ìàøèí Á+ ,Á− è Â:q1 01x1 01x2 0 . . . 01xn 0|=⇒ 01x2 qα1 01x1 01x3 0 . . . 01xn 0|=⇒|=⇒ 01x2 01x3 qα2 01x1 01x4 0 . . . 01xn 0|=⇒ . . . |=⇒ 01x2 .
. . 01xn qαn−1 01x1 0|=⇒|=⇒ q0 01x2 0 . . . 01xn 01x1 0.−Òàêèì îáðàçîì, Ön = (Á+ ◦ Â) ◦ . . . ◦ (Á+ ◦ Â) ◦ Á◦ .{z. . ◦ Á−} = (Á+ ◦ Â)n−1 ◦ (Á− )n−1 .|{z} |n−1n−1Êîïèðîâàíèå Ên :q1 01x1 0 . . . 01xn 0 =⇒ q0 01x1 0 . . . 01xn 01x1 0 . . . 01xn 0,ôèêñèðîâàííîå íàòóðàëüíîå ÷èñëî.Ênãäån > 1Ïîñòðîèì ìàøèíó Ên èíäóêöèåé ïî n > 1.1 . Ïðè n = 1 ìàøèíà Ê1 ñîâïàäàåò ñ ìàøèíîé Ã.20 . Ïóñòü n > 1 è ìàøèíà Ên−1 óæå îïðåäåëåíà. Òîãäà ìàøèíà Ên ðàáîòàåò ïîñëåäóþùåé ñõåìå:0q1 01x1 0 . . .
01xn 0 =⇒ 01x1 0 . . . 01xn−1 qα1 01xn 0 =⇒ 01x1 0 . . . 01xn−1 qα2 01xn 01xn 0 =⇒=⇒ qα3 01x1 0 . . . 01xn−1 01xn 01xn 0 =⇒ qα4 01xn 01xn 01x1 0 . . . 01xn−1 0 =⇒=⇒ 01xn 01xn qα5 01x1 0 . . . 01xn−1 0 =⇒ 01xn 01xn qα6 01x1 0 . . . 01xn−1 01x1 0 . . . 01xn−1 0 =⇒Ên−1xnxn=⇒ qα7 01 01 01x1 0 . . . 01xn−1 01x1 0 . . .
01xn−1 0 =⇒=⇒ qα8 01xn 01x1 0 . . . 01xn−1 01x1 0 . . . 01xn−1 01xn 0 =⇒ q0 01x1 0 . . . 01xn 01x1 0 . . . 01xn 0.Òàêèì îáðàçîì, Ên = (Á+ )n−1 ◦ à ◦ (Á− )n−1 ◦ (Ön+1 )n−1 ◦ (Á+ )2 ◦ Ên−1 ◦ (Á− )2 ◦ Ö2n ◦ Ön . 12.×àñòè÷íî ðåêóðñèâíûå ôóíêöèè ýòîì ïàðàãðàôå ìû ðàññìîòðèì äðóãîé ïîäõîä ê ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè. Åãî ìîæíî íàçâàòü àëãåáðàè÷åñêèì, ïîñêîëüêó îïðåäåëÿåìûé çäåñüêëàññ ôóíêöèé áóäåò ïîðîæäàòüñÿ èç íåêîòîðûõ ïðîñòåéøèõ ôóíêöèé ñ ïîìîùüþîïðåäåë¼ííûõ îïåðàöèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
