В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 5
Текст из файла (страница 5)
Òî÷íåå ñêàæåì, â âîåííûõ èëè28Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåèíûõ ÷ðåçâû÷àéíûõ óñëîâèÿõ èíà÷å, ïîðîé, è íåò âîçìîæíîñòè ïîñòóïèòü. À â áîëåå ìèðíîå âðåìÿ? Ïîïðîáóåì ¾ñîáëþäàòüÊÇÎÒ¿ è îáîéòèñü áåç ñîêðàùåíèé.Ñíîâà:ÏðàâèëàÂèä ïîëó÷àåìîé öåïî÷êèS 0 → BSEBSES → CSD | CDB C nDn ECD → DCABC n−1 (DA)n C E (ïðîøëî ïåðâîå C )CA → ACB (DAn )n C n E (ïðîøëè âñå C )BD → aaBa2 BAn (DAn )n−1 C n EBA → AB(a2 An )n B C nE (óøëè âñå D)CE → Eaa(a2 An )n B Ea2n (óøëè âñå C )A→aan∗n+2n BE a2nBE → aaaaan2+4n+42= a(n+2)S → ε | a | a4(âîñïîëíèëè ÷àñòíûå ðåøåíèÿ)Èòàê, åñëè ñîêðàùàòü íåëüçÿ, äîñòðàèâàåì ñëîâî äî áëèæàéøåãî ïîäõîäÿùåãî êâàäðàòà.  äàííîì ñëó÷àå óäîáíåå äîñòðîèòü22ñëîâî äî a(n+2) , ò.ê. äëÿ äîñòðîéêè äî a(n+1) íàì áû ïîòðåáîâàëîñü ïåðåâåñòè BE → a, ò.å.
îïÿòü ÷òî-òî ñîêðàòèòü. Íàïîìíèì,÷òî â ÊÇ-ãðàììàòèêàõ äîïóñêàåòñÿ ïåðåõîä àêñèîìû â ïóñòóþöåïî÷êó (ε), åñëè àêñèîìà íèãäå áîëåå íå âñòðå÷àåòñÿ â ïðàâûõ÷àñòÿõ ïðàâèë (ò.å. êîãäà èç íà÷àëüíîãî íè÷åãî ïîëó÷àþò äðóãîåíè÷åãî).Ìû ïîëó÷èëè íåñîêðàùàþùóþ ãðàììàòèêó. Íî øèðîêî èñïîëüçóåìûå ïðè å¼ ïîñòðîåíèè ïðàâèëà âèäà AB → BA (ABC →CBA è ò.ï.), î÷åâèäíî, íå ïîäõîäÿò ïîä îïðåäåëåíèå ÍÑãðàììàòèêè (óáåäèòåñü!). Òàêèå ¾ðîêèðîâêè¿, îäíàêî, ëåãêî ðàñêðûòü ÷åðåç öåïî÷êó ïðàâèë âèäàAB → A0 B → A0 B 0 → BB 0 → BA,ãäå A0 è B 0 - íèãäå áîëåå â ãðàììàòèêå íå èñïîëüçóåìûå âñïîìîãàòåëüíûå çíàêè. Îòìåòèì, ÷òî çàìåíó íà ïðîìåæóòî÷íûå çíàêèè îáðàòíî íà èñõîäíûå íóæíî îñóùåñòâëÿòü â îäíîì è òîì æåïîðÿäêå (ñëåâà-íàïðàâî èëè, íàîáîðîò, òîëüêî ñïðàâà-íàëåâî),èíà÷å â îáùåì ñëó÷àå (êîãäà íàçíà÷åíèå A è B â ãðàììàòèêåðàçëè÷íî) âîçíèêàþò ëèøíèå öåïî÷êè.Òàê, ïðèìåíåíèå çàìåíûAB → A0 B → A0 B 0 → A0 A → BAÌàøèíû Òüþðèíãà29(íàðóøåí ïîðÿäîê çàìåí) ïðè íàëè÷èè ñîîòâåòñòâóþùåãî ïðîâîêàöèîííîãî îêðóæåíèÿ äîïóñêàåò ïîäìåíó B íà A:∗∗∗x = AABB → AA0 AB → AA0 BA → ABAA = y ,(|x|A = |x|B = 2,à |y|A = 3 è |y|B = 1)!Çàìåíà AB íà BA â ðàìêàõ ÍÑ-ãðàììàòèêè êîðîòêî îáîçíà∗÷àåòñÿ, êàê è îáû÷íûé âûâîä: AB → BA.Òàêèì îáðàçîì, îäèí èç âîçìîæíûõ íàáîðîâ ïðàâèë èñêîìîéÍÑ-ãðàììàòèêè èìååò ñëåäóþùèé âèä:Ïðàâèëà0Âèä ïîëó÷àåìîé öåïî÷êè4S → ε | a | a | BSEBSES → CSD | CDB C nDn E∗BC n−1 DCA D n−1 E∗BC n−1 (DA)n CECD → DCACA → ACB(DAn )n C n E∗a2 BAn (DAn )n−1 C n EBA → AB∗(a2 An )n B C nE∗CE → Eaa(a2 An )n B Ea2nA→aan∗n+2n BE a2nBD → aaB∗BE → a42an+4n+42= a(n+2)2.4.
Ìàøèíû ÒüþðèíãàÔîðìàëüíî ìàøèíà Òüþðèíãà (T m) - ýòî T m =(Q, Γ, Σ, D, q0 , F ), ãäåQ - êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé;F ⊆ Q - ìíîæåñòâî çàêëþ÷èòåëüíûõ ñîñòîÿíèé;Γ - ìíîæåñòâî äîïóñòèìûõ ëåíòî÷íûõ ñèìâîëîâ;îäèí èç íèõ, îáû÷íî îáîçíà÷àåìûé B , - ïóñòîé ñèìâîëΣ ìíîæåñòâî âõîäíûõ ñèìâîëîâ, ïîäìíîæåñòâî Γ, íåâêëþ÷àþùåå B ,D ôóíêöèÿ ïåðåõîäîâ, îòîáðàæåíèå èç (Q − F )× Γ →Q×Γ×{L, R}; äëÿ íåêîòîðûõ àðãóìåíòîâ ôóíêöèÿ D ìîæåòáûòü íå îïðåäåëåíà.q0 - íà÷àëüíîå ñîñòîÿíèå.30Ãëàâà 2.0.a1a2...aißçûêè è èõ ïðåäñòàâëåíèå...anBB...6Êîíå÷íîåóïðàâëåíèåÐèñ. 2.2.
Ìàøèíà ÒüþðèíãàÒàê îïðåäåë¼ííàÿ ìàøèíà Òüþðèíãà íàçûâàåòñÿ äåòåðìèíèðîâàííîé. Íåäåòåðìèíèðîâàííàÿ ìàøèíà Òüþðèíãàäëÿ êàæäîé ïàðû (Q − F ) × Γ ìîæåò èìåòü íåñêîëüêî âîçìîæíûõ ïåðåõîäîâ.  íà÷àëå n ÿ÷ååê ëåíòû ñîäåðæàò âõîäw ∈ (Γ − {B})∗ , îñòàëüíàÿ ÷àñòü ëåíòû ñîäåðæèò ïóñòûåñèìâîëû. Îáîçíà÷èì êîíôèãóðàöèþ ìàøèíû Òüþðèíãà êàê(q, w, i), ãäå q ∈ Q - òåêóùåå ñîñòîÿíèå, i - âûäåëåííûéýëåìåíò ñòðîêè, ¾ïîëîæåíèå ãîëîâêè¿, w - òåêóùåå ñîäåðæèìîå çàíÿòîãî ó÷àñòêà ëåíòû.
Åñëè ãîëîâêà ñäâèãàåòñÿ ñÿ÷åéêè, ìàøèíà äîëæíà çàïèñàòü â íå¼ ñèìâîë, òàê ÷òî ëåíòà âñåãäà ñîñòîèò èç ó÷àñòêà, ñîñòîÿùåãî èç êîíå÷íîãî ÷èñëà íåïóñòûõ ñèìâîëîâ è áåñêîíå÷íîãî êîëè÷åñòâà ïóñòûõñèìâîëîâ.Øàã T m îïðåäåëèì ñëåäóþùèì îáðàçîì.Ïóñòü (q, A1 , A2 , ... An , i) êîíôèãóðàöèÿ T m,ãäå 1 6 i 6 n + 1.Åñëè 1 6 i 6 n è D(q, Ai ) = (p, A, R)(R îò àíãë. Right), òî A 6= B è(q, A1 A2 ... An , i)|−T m (p, A1 A2 ... Ai−1 AAi+1 ... An , i + 1).Òî åñòü T m ïå÷àòàåò ñèìâîë A è ïåðåäâèãàåòñÿ âïðàâî.Åñëè 2 6 i 6 n è D(q, Ai ) = (p, A, L)(L îò àíãë. Left), òî åñëè i = n, òî äîïóñòèìî A = B è(q, A1 A2 ... An , i)|−T m (p, A1 A2 ...
Ai−1 AAi+1 ... An , i − 1).T m ïå÷àòàåò A è ïåðåäâèãàåòñÿ âëåâî, íî íå çà êîíåöëåíòû.Åñëè i = n + 1, ãîëîâêà ïðîñìàòðèâàåò ïóñòîé ñèìâîë B .Ìàøèíû Òüþðèíãà31Åñëè D(q, B) = (p, A, R), òî A 6= B è(q, A1 A2 ... An , n + 1)|−T m (p, A1 A2 ... An A, n + 2).Åñëè D(q, B) = (p, A, L), òî äîïóñòèìî A=B è(q, A1 A2 ... An , n + 1)|−T m (p, A1 A2 ... An A, n).Åñëè äâå êîíôèãóðàöèè ñâÿçàíû îòíîøåíèåì |−T m , òîìû ãîâîðèì, ÷òî âòîðàÿ ïîëó÷àåòñÿ èç ïåðâîé çà îäèí øàã.Åñëè âòîðàÿ ïîëó÷àåòñÿ èç ïåðâîé çà êîíå÷íîå, âêëþ÷àÿíîëü, ÷èñëî øàãîâ, òî òàêîå îòíîøåíèå áóäåì îáîçíà÷àòü|−T m∗ .ßçûê, äîïóñêàåìûé T m, ýòî ìíîæåñòâî òàêèõ ñëîâ èçT ∗ , êîòîðûå áóäó÷è ðàñïîëîæåíû â ëåâîì êîíöå ëåíòû ïåðåâîäÿò T m èç íà÷àëüíîãî ñîñòîÿíèÿ q0 ñ íà÷àëüíûì ïîëîæåíèåì ãîëîâêè â ñàìîì ëåâîì êîíöå ëåíòû â êîíå÷íîåñîñòîÿíèå. Ôîðìàëüíî, ÿçûê, äîïóñêàåìé T m, ýòîL = {w | w ∈ Σ∗ è (q0 , w, 1)|−T m∗ (q, u, i) äëÿ íåêîòîðûõq ∈ F , u ∈ Γ∗ è öåëîãî i}.Åñëè T m ðàñïîçíà¼ò L, òî T m îñòàíàâëèâàåòñÿ, òî åñòüíå èìååò ïåðåõîäîâ ïîñëå òîãî, êàê ñëîâî äîïóùåíî.
Îäíàêî, åñëè ñëîâî íå äîïóùåíî, âîçìîæíî, ÷òî T m íå îñòàíàâëèâàåòñÿ.ßçûê, äîïóñêàåìûé íåêîòîðîé T m, íàçûâàåòñÿ ðåêóðñèâíî ïåðå÷èñëèìûì. Åñëè T m îñòàíàâëèâàåòñÿ íà âñåõâõîäàõ, òî ãîâîðÿò, ÷òî T m çàäà¼ò àëãîðèòì è ÿçûê íàçûâàåòñÿ ðåêóðñèâíûì.Ñóùåñòâóåò ìàøèíà Òüþðèíãà, êîòîðàÿ ïî íåêîòîðîìóîïèñàíèþ ïðîèçâîëüíîé T m è êîäèðîâàíèþ ñëîâà x ìîäåëèðóåò ïîâåäåíèå T m ñî âõîäîì x.
Òàêàÿ ìàøèíà Òüþðèíãàíàçûâàåòñÿ óíèâåðñàëüíîé ìàøèíîé Òüþðèíãà.2.4.1. Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâàÏðîáëåìà îñòàíîâà äëÿ ìàøèíû Òüþðèíãà ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: ìîæíî ëè îïðåäåëèòü ïî äàííîéìàøèíå Òüþðèíãà â ïðîèçâîëüíîé êîíôèãóðàöèè ñî ñòðîêîé êîíå÷íîé äëèíû íåïóñòûõ ñèìâîëîâ íà ëåíòå îñòàíîâèòñÿ ëè îíà? Ãîâîðÿò, ÷òî ýòà ïðîáëåìà ðåêóðñèâíî íåðàç-32Ãëàâà 2.0.ßçûêè è èõ ïðåäñòàâëåíèåðåøèìà, ÷òî îçíà÷àåò, ÷òî íå ñóùåñòâóåò àëãîðèòìà, êîòîðûé äëÿ ëþáîé T m â ïðîèçâîëüíîé êîíôèãóðàöèè îïðåäåëÿë áû îñòàíîâèòñÿ ëè â êîíöå êîíöîâ T m.Ïåðåíóìåðóåì âñå ìàøèíû Òüþðèíãà è âñå âîçìîæíûåâõîäû íàä àëôàâèòîì Σ.
Ðàññìîòðèì ÿçûêL1 = {xi | xi íå äîïóñêàåòñÿ Ti }ßñíî, ÷òî L1 íå äîïóñêàåòñÿ íèêàêîé T m. Äîïóñòèì, ÷òîýòî íå òàê. Ïóñòü L1 äîïóñêàåòñÿ Tj . Òîãäà xj ∈ L1 òîãäàè òîëüêî òîãäà, êîãäà xj íå äîïóñêàåòñÿ Tj . Íî ïîñêîëüêó Tj äîïóñêàåò L1 , xj ∈ L1 òîãäà è òîëüêî òîãäà, êîãäàäîïóñêàåòñÿ Tj , - ïðîòèâîðå÷èå. Òàê ÷òî L1 - íå ÿâëÿåòñÿðåêóðñèâíî ïåðå÷èñëèìûì ìíîæåñòâîì.Ïðåäïîëîæèì, ÷òî ìû èìååì àëãîðèòì (òî åñòü ìàøèíóÒüþðèíãà, êîòîðàÿ âñåãäà îñòàíàâëèâàåòñÿ) äëÿ îïðåäåëåíèÿ, îñòàíîâèòñÿ ëè ìàøèíà Òüþðèíãà â äàííîé êîíôèãóðàöèè.
Òîãäà ñëåäóþùèì îáðàçîì ìîæíî ïîñòðîèòü ìàøèíó Òüþðèíãà T , äîïóñêàþùóþ L1 .1. Åñëè äàíî ñëîâî x, T ïåðå÷èñëÿåò ñëîâà x1 , x2 , ... ïîêàíå áóäåò xi = x.2. T ãåíåðèðóåò êîäèðîâêó ìàøèíû Òüþðèíãà Ti .3. Óïðàâëåíèå ïåðåäà¼òñÿ ãèïîòåòè÷åñêîé ìàøèíå, êîòîðàÿ îïðåäåëÿåò îñòàíàâëèâàåòñÿ ëè Ti íà âõîäå xi .4.
Åñëè âûÿñíÿåòñÿ, ÷òî Ti íå îñòàíàâëèâàåòñÿ íà âõîäåxi , òî T îñòàíàâëèâàåòñÿ è äîïóñêàåò xi .5. Åñëè âûÿñíÿåòñÿ, ÷òî Ti îñòàíàâëèâàåòñÿ íà âõîäå xi ,òî óïðàâëåíèå ïåðåäà¼òñÿ óíèâåðñàëüíîé ìàøèíå Òüþðèíãà, êîòîðàÿ ìîäåëèðóåò Ti íà âõîäå xi . Ïîñêîëüêó Ti â êîíöåêîíöîâ îñòàíàâëèâàåòñÿ, óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãàâ êîíöå êîíöîâ îñòàíàâëèâàåòñÿ è îïðåäåëÿåò äîïóñêàåò ëèTi ñëîâî xi . ëþáîì ñëó÷àå T îñòàíàâëèâàåòñÿ, äîïóñêàÿ xi â òîìñëó÷àå, êîãäà Ti îòâåðãàåò xi , è îòâåðãàÿ xi , êîãäà Ti äîïóñêàåò xi .Òàêèì îáðàçîì, èç íàøåãî ïðåäïîëîæåíèÿ, ÷òî ñóùåñòâóåò ìàøèíà Òüþðèíãà, êîòîðàÿ îïðåäåëÿåò, îñòàíàâëèâàåòñÿ ëè ïðîèçâîëüíàÿ ìàøèíà Òüþðèíãà, ñëåäóåò, ÷òî L1äîïóñêàåòñÿ íåêîòîðîé ìàøèíîé Òüþðèíãà, à ýòî ïðîòèâî-Ìàøèíû Òüþðèíãà33ðå÷èò äîêàçàííîìó âûøå.
Ýòî, â ñâîþ î÷åðåäü, äà¼ò òåîðåìó:Òåîðåìà 2.2. Íå ñóùåñòâóåò àëãîðèòìà äëÿ îïðåäåëåíèÿ òîãî, îñòàíîâèòñÿ ëè ïðîèçâîëüíàÿ ìàøèíà Òüþðèíãà â ïðîèçâîëüíîé êîíôèãóðàöèè.2.4.2. Êëàññ ðåêóðñèâíûõ ìíîæåñòâÒåïåðü ìîæíî ïîêàçàòü, ÷òî êëàññ ðåêóðñèâíûõ ìíîæåñòâ ÿâëÿåòñÿ ñîáñòâåííûì ïîäêëàññîì êëàññà ðåêóðñèâíî ïåðå÷èñëèìûõ ìíîæåñòâ. Òî åñòü ñóùåñòâóåò ìíîæåñòâî,ñëîâà êîòîðîãî ìîãóò áûòü ðàñïîçíàíû ìàøèíîé Òüþðèíãà,êîòîðàÿ íå îñòàíàâëèâàåòñÿ íà íåêîòîðûõ ñëîâàõ, íå ïðèíàäëåæàùèõ ìíîæåñòâó, íî íå ìîæåò áûòü ðàñïîçíàíî íèêàêîé ìàøèíîé Òüþðèíãà, êîòîðàÿ îñòàíàâëèâàåòñÿ íà âñåõñëîâàõ.
Ïðèìåðîì òàêîãî ìíîæåñòâà ÿâëÿåòñÿ äîïîëíåíèåê L1 .Ëåììà 2.1. Åñëè ìíîæåñòâî ðåêóðñèâíî, òî è åãî äîïîëíåíèå ðåêóðñèâíî.Äîêàçàòåëüñòâî. Åñëè L - ðåêóðñèâíîå ìíîæåñòâî, L ⊆T ∗ , òî ñóùåñòâóåò T m äîïóñêàþùàÿ L è ãàðàíòèðîâàííîîñòàíàâëèâàþùàÿñÿ. Ìîæíî ñ÷èòàòü, ÷òî ïîñëå äîïóñêà T míå äåëàåò áîëüøå øàãîâ. Ïîñòðîèì T m1 ïî T m, äîáàâèâíîâîå ñîñòîÿíèå q êàê åäèíñòâåííîå äîïóñêàþùåå ñîñòîÿíèå T m1 . Ïðàâèëà T m1 âêëþ÷àþò âñå ïðàâèëà T m, òàê÷òî T m1 ñèìóëèðóåò T m. Êðîìå òîãî, äëÿ êàæäîé ïàðû,ñîñòàâëåííîé èç íåäîïóñêàþùåãî ñîñòîÿíèÿ è ëåíòî÷íîãîñèìâîëà T m, äëÿ êîòîðûõ ó T m ïåðåõîä íå îïðåäåë¼í, T m1ïåðåõîäèò â ñîñòîÿíèå q è çàòåì îñòàíàâëèâàåòñÿ.Òàêèì îáðàçîì T m1 ñèìóëèðóåò T m âïëîòü äî îñòàíîâêè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
