6. Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы (1162497)
Текст из файла
Ìîäåëè âû÷èñëåíèéÂ.À. Çàõàðîâ, Ð.È. Ïîäëîâ÷åíêîËåêöèÿ 6.1. Ïðîáëåìà ñîîòâåòñòâèé Ïîñòà2. Ìíîãîëîâî÷íûå êîíå÷íûå àâòîìàòû3. Àññîöèàòèâíûå èñ÷èñëåíèÿ. ÑèñòåìûÒóý4. Äðóãèå àëãîðèòìè÷åñêèíåðàçðåøèìûå ìàòåìàòè÷åñêèåïðîáëåìûÀËÃÎÐÈÒÌÈ×ÅÑÊÈ ÍÅÐÀÇÐÅØÈÌÛÅÌÀÒÅÌÀÒÈ×ÅÑÊÈÅ ÇÀÄÀ×ÈÌû ðàññìîòðèì íåñêîëüêî èçâåñòíûõìàòåìàòè÷åñêèõ çàäà÷ èç ðàçíûõ îáëàñòåé êîìáèíàòîðèêè, àëãåáðû, òåîðèè àâòîìàòîâ, èäîêàæåì èõ àëãîðèòìè÷åñêóþ íåðàçðåøèìîñòü.Äëÿ êàæäîé èç ýòèõ çàäà÷ åå àëãîðèòìè÷åñêàÿíåðàçðåøèìîñòü äîêàçûâàåòñÿ îäíèì è òåì æåñïîñîáîì: ñâåäåíèåì ê ýòîé çàäà÷å ïðîáëåìûîñòàíîâà ìàøèíû Òüþðèíãà íà ïóñòîé ëåíòå.Ïîñëå ýòîãî ñòàíîâèòñÿ ïîíÿòíî, êàêîå áîëüøîåçíà÷åíèå äëÿ ðàçâèòèÿ ìàòåìàòèêè èìååò òåîðåìàî íåðàçðåøèìîñòè ïðîáëåìû îñòàíîâà,óñòàíîâëåííàÿ Àëàíîì Òüþðèíãîì.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏóñòü èìååòñÿ íåêîòîðûé êîíå÷íûé àëôàâèò Σ èêîíå÷íîå ìíîæåñòâî ïàð ñëîâ â ýòîì àëôàâèòåP = {(u1 , v1 ), (u2 , v2 ), .
. . , (uk , vk )}.Ïðîáëåìà ñîîòâåòñòâèé Ïîñòà (ÏÑÏ) ñîñòîèò âòîì, ÷òîáû âûÿñíèòü, ñóùåñòâóåò ëè òàêàÿêîíå÷íàÿ ïîñëåäîâàòåëüíîñòü èíäåêñîâ i1, i2, . . . , in, äëÿ êîòîðîé âûïîëíÿåòñÿ ðàâåíñòâîui1 ui2 . . . uin = vi1 vi2 . . . vinÓêàçàííàÿ ïîñëåäîâàòåëüíîñòü èíäåêñîâi1 , i2 , . . . , in íàçûâàåòñÿ ðåøåíèåì ïðîáëåìûñîîòâåòñòâèé Ïîñòà äëÿ ñèñòåìû ïàð P .ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏðèìåð 1.Ïðîáëåìà ñîîòâåòñòâèé Ïîñòà äëÿñèñòåìû ïàð P = {(b, babbb), (ab, abba), (abb, ε)}èìååò ðåøåíèå 3, 2, 3, 1 , ïîñêîëüêóabb ab abb b = ε abba εbabbbÏðèìåð 2.Ïðîáëåìà ñîîòâåòñòâèé Ïîñòà äëÿñèñòåìû ïàð P2 = {(b, bab), (ab, aba), (abb, bba)}íå èìååò ðåøåíèé.
(Ïî÷åìó? )Íàñ áóäåò èíòåðåñîâàòü âîïðîñ î ñóùåñòâîâàíèèàëãîðèòìà, êîòîðûé äëÿ ïðîèçâîëüíîé çàäàííîéñèñòåìû ïàð P óñòàíàâëèâàåò, èìååò ÏÑÏðåøåíèå èëè íåò.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÑîäåðæàòåëüíûé ñìûñë ÏÑÏ òàêîâ.Ïðåäïîëîæèì, ÷òî åñòü äâà àëôàâèòíûõêîäèðîâàíèÿ îäíîãî è òîãî æå àëôàâèòàñîîáùåíèéϕ : 1 → u1 , .
. . k → uk ;ψ : 1 → v1 , . . . k → vk .Âîïðîñ: ñóùåñòâóåò ëè òàêîå ñîîáùåíèåi1 , i2 , . . . , in , êîòîðîå êîäèðóåòñÿ îäèíàêîâîñèñòåìàìè êîäèðîâàíèÿ ϕ è ψ , ò.å.ϕ(i1 i2 . . . in ) = ui1 ui2 . . . uin = vi1 vi2 . . . vin = ψ(i1 i2 . . . in )?ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏðîáëåìà ñîîòâåòñòâèé Ïîñòà íàçûâàåòñÿèíèöèàëüíîé (ÈÏÑÏ) â òîì ñëó÷àå, åñëèäîïîëíèòåëüíî òðåáóåòñÿ, ÷òîáû åå ðåøåíèåíà÷èíàëîñü èíäåêñîì 1 .Óòâåðæäåíèå 6.1. ÈÏÑÏ àëãîðèòìè÷åñêèñâîäèìà ê ÏÑÏ.Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî äëÿ ëþáîéñèñòåìû ïàð P ìîæíî ïîñòðîèòü òàêóþ ñèñòåìóïàð Pb , ÷òî ÈÏÑÏ äëÿ P èìååò ðåøåíèå òîãäà èòîëüêî òîãäà, êîãäà ÏÑÏ äëÿ Pb èìååò ðåøåíèå.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏóñòü P = {(u1, v1), .
. . , (uk , vk )} . Ðàññìîòðèìäâå íîâûå áóêâû #,$ , è äëÿ êàæäîé ïàðû ñëîâui = x1 x2 . . . xp , vi = y1 y2 . . . yq ,îïðåäåëèì íîâóþ ïàðó ñëîâubi = x1#x2# . . . #xp#, vbi = #y1#y2# . . . #yq.Êðîìå òîãî, ïîñòðîèì åùå äâå ïàðû ñëîâub0 = #bu1, vb0 = vb1 ,ubk+1 = $, vbk+1 = #$,è ïîëîæèìb = {(bPu0 , vb0 ), (bu1 , vb1 ), . .
. , (buk , vbk ), (buk+1 , vbk+1 )} .ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÅñëè ïîñëåäîâàòåëüíîñòü èíäåêñîâ1, i2 , i3 , . . . , inÿâëÿåòñÿ ðåøåíèåì ÈÏÑÏ äëÿ P , ò.å.u1 ui1 ui2 . . . uin = v1 vi1 vi2 . . . vin ,òî ïîñëåäîâàòåëüíîñòü èíäåêñîâ0, i2 , i3 , . . . , in , k + 1ÿâëÿåòñÿ ðåøåíèåì ÏÑÏ äëÿ Pb , ò.å.#bu1 ubi1 ubi2 .
. . ubin$ = vb1 vbi1 vbi2 . . . vbin#$.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏóñòü ïîñëåäîâàòåëüíîñòü èíäåêñîâ j1, j2, . . . , jmÿâëÿåòñÿ êðàò÷àéøèì ðåøåíèåì ÏÑÏ äëÿ Pb , ò.å.ubj1 ubj2 . . . ubjm = vbj1 vbj2 . . . vbjm .Òîãäà j1 = 0 , ïîñêîëüêó òîëüêî ïàðà ñëîâ ub0, vb0íà÷èíàåòñÿ îäíîé è òîé æå áóêâîé # ,jm = k + 1 , ïîñêîëüêó òîëüêî ïàðà ñëîâ ubk+1 , vbk+1îêàí÷èâàåòñÿ îäíîé è òîé æå áóêâîé $ ,èíäåêñ k + 1 íå âñòðå÷àåòñÿ ñðåäè j2, .
. . , jm−1 ,ïîñêîëüêó ðàññìàòðèâàåìîå ðåøåíèå êðàò÷àéøåå,èíäåêñ 0 íå âñòðå÷àåòñÿ ñðåäè j2, . . . , jm−1 ,ïîñêîëüêó â ñëîâå vbj vbj . . . vbj íåò èäóùèõ ïîäðÿäáóêâ # .12mÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÒàêèì îáðàçîì èç ðàâåíñòâàñëåäóåò, ÷òîubj1 ubj2 . . . ubjm = vbj1 vbj2 . . . vbjm#bu1 ubj2 . . . ubjm−1$ = vbj1 vbj2 . . . vbjm−1 #$à îòñþäà ñëåäóåò ðàâåíñòâîu1 uj2 . . .
ujm−1 = v1 vj2 . . . vjm−1 ,ò.å. ÈÏÑÏ äëÿ P èìååò ðåøåíèå j2, . . . , jm−1 .QEDÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏðîáëåìà îñòàíîâà ìàøèíÒüþðèíãà àëãîðèòìè÷åñêè ñâîäèìà ê ÈÏÑÏ.Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî äëÿ ëþáîé ÌÒM ìîæíî ïîñòðîèòü òàêóþ ñèñòåìó ïàð PM , ÷òîÈÏÑÏ äëÿ PM èìååò ðåøåíèå òîãäà è òîëüêîòîãäà, êîãäà M îñòàíàâëèâàåòñÿ íà ïóñòîé ëåíòå.Èäåÿ ñâåäåíèÿ òàêîâà .Óòâåðæäåíèå 6.2.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏðåäïîëîæèì, ÷òî ÌÒ M èìååò êîíå÷íîåâû÷èñëåíèå íà ïóñòîé ëåíòåα0 = q1 0 −→ α1 −→ · · · −→ αN = w 0 q1 w 00Ïîñòðîèì ÈÏÑÏ PM = P1 ∪ P2 , êîòîðàÿ èìååòðåøåíèå, ïîðîæäàþùåå ïàðó îäèíàêîâûõ ñëîââèäàñòèðàíèåðåçóëüòàòà{z}|$α| 0 $α1 ${z. .
. $αN $}ñèìóëÿöèÿ âû÷èñëåíèÿ. . . $q0 w 00 $ . . . $q0 $$ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÌíîæåñòâî P1 îáðàçóþò ñëåäóþùèå ïàðû ñëîâ, ïîçâîëÿþùèåìîäåëèðîâàòü âû÷èñëåíèå ÌÒ M :1. u1 = $ , v1 = $q00$ . Ýòà ïàðà âñåãäà áóäåò ïåðâîé â ëþáîìðåøåíèè;2. ui = c , vi = c äëÿ âñåõ áóêâ ëåíòî÷íîãî àëôàâèòà;3.
ui = $ , vi = $ ;4. ui = cq0a , vi = q00cb äëÿ êàæäîé êîìàíäû âèäàhq 0 a : bq 00 Li ÌÒ M è ëåíòî÷íîé áóêâû c ;5. ui = $q0a , vi = $q000b äëÿ êàæäîé êîìàíäû âèäàhq 0 a : bq 00 Li ÌÒ M ;6. ui = q0ac , vi = bq00c äëÿ êàæäîé êîìàíäû âèäàhq 0 a : bq 00 Ri ÌÒ M è ëåíòî÷íîé áóêâû c ;7. ui = q0a$ , vi = bq000$ äëÿ êàæäîé êîìàíäû âèäàhq 0 a : bq 00 Ri ÌÒ M .ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀ$q1 0$α2 $α3 $ . . . . . . $αN−1 $$q1 0$α2 $α3 $α4 $ . .
. $αN−1 $w 0 q0 w 00 $Ïîñòðîåíèå ðåøåíèÿ ÈÏÑÏ íà÷èíàåòñÿ ñ ïàðû(u1 , v1 ) .À äàëüøå â ñòðåìëåíèè ñäåëàòü ïåðâóþ ñòðîêóðàâíîé âòîðîé ñòðîêå ìû âûíóæäåíû áóäåìâûáèðàòü ïàðû èç ìíîæåñòâà P1 îäíîçíà÷íî,ìîäåëèðóÿ òåì ñàìûì âû÷èñëåíèå ÌÒ M .È ïðîöåññ ýòîò ìîæåò îñòàíîâèòüñÿ òîãäà è òîëüêîòîãäà, êîãäà âî âòîðîé ñòðîêå áóäåò äîñòèãíóòàçàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ αN = w 0q0w 00.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀ$q1 0$α2 $α3 $ . . .
. . . $αN−1 $w 0 q0 w 00 $ . . . $q0 $$$q1 0$α2 $α3 $α4 $ . . . $αN−1 $w 0 q0 w 00 $ . . . $q0 $$Ïîñëå òîãî, êàê âî âòîðîé ñòðîêå áûëà äîñòèãíóòàçàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ, íóæíî ñóìåòüâûðîâíÿòü îáå ñòðîêè.È äëÿ ýòîãî äîñòàòî÷íî ¾ñòèðàòü¿ ïîî÷åðåäíîâñå ëåíòî÷íûå áóêâû ïðè ïîìîùè ñëåäóþùèõ ïàðñëîâ èç ìíîæåñòâà P28910,äëÿ êàæäîé ëåíòî÷íîé áóêâû a ;ui = $q0 a , vi = $q0 äëÿ êàæäîé ëåíòî÷íîé áóêâû a ;ui = q0 $$ , vi = $ .ui = aq0 vi = q0 ðåçóëüòàòå îáå ñòðîêè ñòàíîâÿòñÿ îäèíàêîâûìè.QEDÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÏðîáëåìà ñîîòâåòñòâèé Ïîñòààëãîðèòìè÷åñêè íåðàçðåøèìà.Äîêàçàòåëüñòâî.
Èç Óòâåðæäåíèé 6.1, 6.2.ìîæíî ñäåëàòü âûâîä î òîì, ÷òî ñóùåñòâóåòàëãîðèòì, êîòîðûé äëÿ ëþáîé ÌÒ M ñòðîèòòàêóþ ñèñòåìó ïàð PbM , ÷òîM îñòàíàâëèâàåòñÿ íà ïóñòîé êîíôèãóðàöèè ⇔ÏÑÏ äëÿ PbM èìååò ðåøåíèå.Òàêèì îáðàçîì, èç àëãîðèòìè÷åñêîéíåðàçðåøèìîñòè ïðîáëåìû îñòàíîâà ìàøèíÒüþðèíãà ñëåäóåò íåðàçðåøèìîñòü ÏÑÏ. QEDÒåîðåìà 6.3.ÏÐÎÁËÅÌÀ ÑÎÎÒÂÅÒÑÒÂÈÉ ÏÎÑÒÀÁóäåò ïðîáëåìà ñîîòâåòñòâèé Ïîñòàîñòàâàòüñÿ àëãîðèòìè÷åñêè íåðàçðåøèìîé, åñëèàëôàâèò Σ , â êîòîðîì çàäàþòñÿ ñëîâà âñåõ ïàðñèñòåìû P , ñîñòîèò èç îäíîé áóêâû?À ÷òî áóäåò, åñëè ýòîò àëôàâèò ñîñòîèò èç äâóõáóêâ?Çàäà÷à 1.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÊîíå÷íûé àâòîìàò ïðåäñòàâëÿåò ñîáîéóñòðîéñòâî, ïðî÷èòûâàþùåå ñëîâî, çàïèñàííîå íàëåíòå.Îáû÷íûé êîíå÷íûé àâòîìàò èìååò òîëüêî îäíóñ÷èòûâàþùóþ ãîëîâêó, êîòîðàÿ äâèæåòñÿ ïî ëåíòåâ îäíó ñòîðîíó.x1 x2 x3 · · ·⇑q0· · · xN a-ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÅñëè àâòîìàòó ðàçðåøèòü ñäâèãàòü ñ÷èòûâàþùóþãîëîâêó â îáå ñòîðîíû...x1 x2 x3 · · ·⇑q0· · · xN aòî, êàê ýòî íè óäèâèòåëüíî, åãî âû÷èñëèòåëüíûåâîçìîæíîñòè íå âîçðàñòóò.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÀ ÷òî ïðîèçîéäåò, åñëè àâòîìàò áóäåò èìåòü ÄÂÅñ÷èòûâàþùèå ãîëîâêè, êîòîðûå ìîãóòïåðåìåùàòüñÿ òîëüêî â îäíó ñòîðîíó, íî ïðè ýòîìíåçàâèñèìî äðóã îò äðóãà?x1 x2 x3 · · ·⇑⇑qi2· · · xN a-Îêàçûâàåòñÿ, ÷òî âû÷èñëèòåëüíûå âîçìîæíîñòèòàêîãî àâòîìàòà óñèëèâàþòñÿ íàñòîëüêî, ÷òî îíñïîñîáåí ìîäåëèðîâàòü ìàøèíû Òüþðèíãà!ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏîêàæèòå ñàìîñòîÿòåëüíî, ÷òî äâóõãîëîâî÷íûéàâòîìàò ñïîñîáåí ðàñïîçíàâàòü ñëåäóþùèå ÿçûêè,íå ÿâëÿþùèåñÿ ðåãóëÿðíûìè:1.
L1 = {an bn : n ≥ 0} ;2. L2 = {an bn c n : n ≥ 0} ;3. L3 = {ww : w ∈ {a, b}∗} ;À ñïîñîáåí ëè äâóõãîëîâî÷íûé àâòîìàòðàñïîçíàâàòü ÿçûê L4 = {ww − : w ∈ {a, b}∗} ?Îêàçûâàåòñÿ, ÷òî íåò!Çàäà÷à 2. Äîêàçàòü, ÷òî ÿçûê L4 íåðàñïîçíàåòñÿ äâóõãîëîâî÷íûìè àâòîìàòàìè.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏî÷åìó æå äâóõãîëîâî÷íûé àâòîìàò ñïîñîáåíìîäåëèðîâàòü ìàøèíû Òüþðèíãà?Ïîòîìó ÷òî âåðíàÒåîðåìà 6.4. Ïðîáëåìà ïóñòîòû ÿçûêîâ,ðàñïîçíàâàåìûõ äâóõãîëîâî÷íûìè àâòîìàòàìè,àëãîðèòìè÷åñêè íåðàçðåøèìà.Íî ïðåæäå ÷åì åå äîêàçûâàòü, äàäèì ôîðìàëüíûåîïðåäåëåíèÿ äâóõãîëîâî÷íûõ àâòîìàòîâ è èõâû÷èñëåíèé.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÄâóõãîëîâî÷íûé äåòåðìèíèðîâàííûé êîíå÷íûé àâòîìàò ýòîñèñòåìà D = (Σ, S, s0, F , T ) , ãäåI Σ ëåíòî÷íûé àëôàâèò,I S êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé,I s0 íà÷àëüíîå ñîñòîÿíèå,I F ïîäìíîæåñòâî ôèíàëüíûõ ñîñòîÿíèé,I T : S × (Σ ∪ {a}) × (Σ ∪ {a}) → S × {0, 1} × {0, 1} ôóíêöèÿ ïåðåõîäîâ.Çäåñü T (s, x1, x2) = (s 0, δ1, δ2) îçíà÷àåò, ÷òî åñëè àâòîìàòïðåáûâàåò â ñîñòîÿíèè s , è åãî ñ÷èòûâàþùèå ãîëîâêèîáîçðåâàþò íà ëåíòå áóêâû èëè ãðàíè÷íûé ìàðêåð x1 è x2 , òîíà ñëåäóþùåì òàêòå âû÷èñëåíèÿ îí ïåðåõîäèò â ñîñòîÿíèå s , èåãî ñ÷èòûâàþùèå ãîëîâêè ñäâèãàþòñÿ âïðàâî íà δ1 è δ2 ÿ÷ååê.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ-êîíôèãóðàöèåé äâóõãîëîâî÷íîãî àâòîìàòàíàçûâàåòñÿ íàáîð âèäà (w a, s, i1, i2) , ãäåw = x1 x2 .
. . xn ∈ Σ∗ ñëîâî, çàïèñàííîå íàëåíòå;s ∈ S òåêóùåå ñîñòîÿíèå àâòîìàòà,i1 , i2 íîìåðà áóêâ (ÿ÷ååê ëåíòû),îáîçðåâàåìûõ ñ÷èòûâàþùèìè ãîëîâêàìèàâòîìàòà, 1 ≤ i1, i2 ≤ n + 1 .Êîíôèãóðàöèÿ (w a, s0, 1, 1) ñ÷èòàåòñÿ íà÷àëüíîé.Âñÿêàÿ êîíôèãóðàöèÿ âèäà (w a, s, n + 1, n + 1) ,ãäå s ∈ F , ñ÷èòàåòñÿ ôèíàëüíîéwIIIÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏðåîáðàçîâàíèå êîíôèãóðàöèé (w a, s, i1, i2) −→ (w a, s 0, j1, j2)àâòîìàòîì D âûïîëíÿåòñÿ â òîì è òîëüêî òîì ñëó÷àå, åñëèI w = x1 x2 . .
. xn ,I T (s, xi , xi ) = (s 0 , δ1 , δ2 ) ,I j1 = i1 + δ1 , j2 = i2 + δ2 .Âû÷èñëåíèåì conf1 −→∗ confN äâóõãîëîâî÷íîãî êîíå÷íîãîàâòîìàòà D íà ñëîâå w íàçûâàåòñÿ âñÿêàÿ ïîñëåäîâàòåëüíîñòüïðåîáðàçîâàíèé w -êîíôèãóðàöèé12conf1 −→ conf2 −→ · · · −→ confN .Ýòî âû÷èñëåíèå ñ÷èòàåòñÿ óñïåøíûì , åñëè conf0 íà÷àëüíàÿ, à confN ôèíàëüíàÿ êîíôèãóðàöèè.ßçûê äâóõãîëîâî÷íîãî àâòîìàòà D ýòî ìíîæåñòâî ñëîâL(D) = {w : ñóùåñòâóåò óñïåøíîå w − âû÷èñëåíèå àâòîìàòà D}.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏðîáëåìà îñòàíîâà ìàøèíÒüþðèíãà àëãîðèòìè÷åñêè ñâîäèìà ê ïðîáëåìåïóñòîòû äâóõãîëîâî÷íûõ äåòåðìèíèðîâàííûõêîíå÷íûõ àâòîìàòîâ.Äîêàçàòåëüñòâî. Ïîêàæåì, ÷òî äëÿ ëþáîé ÌÒM ìîæíî ïîñòðîèòü òàêîé äâóõãîëîâî÷íûéàâòîìàò DM , ÷òîL(PM ) 6= ∅ ⇔ M îñòàíàâëèâàåòñÿ íà ïóñòîéëåíòå.Èäåÿ ñâåäåíèÿ òàêîâà .Óòâåðæäåíèå 6.5.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÏðåäïîëîæèì, ÷òî ÌÒ M èìååò âû÷èñëåíèå íàïóñòîé ëåíòåα0 = q1 0 −→ α1 −→ α2 −→ · · · · · ·Ïîñòðîèì äâóõãîëîâî÷íûé àâòîìàò DM , ÿçûêL(PM ) êîòîðîãî ëèáî ñîäåðæèò òîëüêî îäíî ñëîâîw = $α0 $α1 $ .
. . $αN ,åñëè óêàçàííîå âû÷èñëåíèå ÌÒ M çàâåðøàåòñÿñïóñòÿ N òàêòîâ, ëèáî ÿâëÿåòñÿ ïóñòûì, åñëèóêàçàííîå âû÷èñëåíèå ÌÒ M áåñêîíå÷íî.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÑöåíàðèé ðàáîòû àâòîìàòà DM òàêîâ.1. Íà÷àâ ðàáîòàòü ñ w -êîíôèãóðàöèè$ α0 $ α1 $ . . . $ αN−1 $ αN a,⇑ 1 ⇑2àâòîìàòà DM ïðîäâèãàåò ñ÷èòûâàþùóþ ãîëîâêó⇑1 äî ñëåäóþùåãî ðàçäåëèòåëÿ $ è ïðè ýòîìïðîâåðÿåò, ÷òî ñëîâî α0, ðàñïîëîæåííîå ìåæäóýòèìè ðàçäåëèòåëÿìè ýòî íà÷àëüíàÿêîíôèãóðàöèÿ α0 = q10 ÌÒ:$ α0 $ α1 $ . . . $ αi−1 $ αi $ .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
