4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки (1162495)
Текст из файла
Ìîäåëè âû÷èñëåíèéÂ.À. Çàõàðîâ, Ð.È. Ïîäëîâ÷åíêîËåêöèÿ 4.1. Ìàøèíû Òüþðèíãà.2. Ðåêóðñèâíûå è ðåêóðñèâíîïåðå÷èñëèìûå ÿçûêè3. Âàðèàöèè ìàøèí Òüþðèíãà4. Ñâîéñòâà çàìêíóòîñòè5. Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó6. Ìàññîâûå àëãîðèòìè÷åñêèå ïðîáëåìûÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ0Ïðîãðàììà1111011110- q1Êîìàíäû:?óâèäåâ "1" , ñòåðåòü åãî, çàïèñàòü "0" è ñäâèíóòüñÿ âïðàâîÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ0Ïðîãðàììà111001- q2Êîìàíäû:?1110ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ0Ïðîãðàììà1110011110- q2Êîìàíäû:?óâèäåâ "0" , ñòåðåòü åãî, çàïèñàòü "1" è ñäâèíóòüñÿ âëåâîÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ0Ïðîãðàììà11101- q3Êîìàíäû:?11110ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÏóñòü çàäàíû êîíå÷íûå âõîäíîé àëôàâèòΣ = {a1 , a2 , .
. . , an } è ëåíòî÷íûé àëôàâèòΓ, Σ ⊆ Γ , â êîòîðîì îñîáî âûäåëåí ïóñòîéñèìâîë 0, 0 ∈/ Σ .Âõîäíûì ñëîâîì (ëåíòî÷íûì ñëîâîì ) áóäåìíàçûâàòü âñÿêîå ñëîâî â àëôàâèòå Σ(ñîîòâåòñòâåííî Γ ).Ïóñòü çàäàí êîíå÷íûé àëôàâèò ñîñòîÿíèéQ = {q−1 , q0 , q1 , q2 , . . . , qm }, Q ∩ Γ = ∅ , âêîòîðîì îñîáî âûäåëåíû íà÷àëüíîå ñîñòîÿíèå q1 ,äîïóñêàþùåå ñîñòîÿíèå q0 , îòâåðãàþùååñîñòîÿíèå q−1 .ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÌàøèíîé Òüþðèíãà (ÌÒ) íàçûâàåòñÿ ñèñòåìàM = (Σ, Γ, Q, q1 , q0 , q−1 , T ) , ãäåT : Q \ {q0 , q−1 } × Γ → Γ × Q × {L, R}âñþäó îïðåäåëåííàÿ ôóíêöèÿ ïåðåõîäîâ .Ôóíêöèþ ïåðåõîäîâ ÌÒ óäîáíî ïðåäñòàâëÿòü ââèäå ìíîæåñòâà íàáîðîâ{(q, x : y , q 0 , D) : T (q, x) = (y , q 0 , D), q ∈ Q, x ∈ Γ},êîòîðûå áóäåì íàçûâàòü êîìàíäàìè ÌÒ.ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàæäóþ êîìàíäó (q, x : y , q0, D) íóæíî ïîíèìàòüòàê:åñëè ÌÒ íàõîäèòñÿ â ñîñòÿíèè q è îáîçðåâàåòñèìâîë x , òî çàïèñàòü â îáîçðåâàåìóþ ÿ÷åéêóñèìâîë y , ïåðåéòè â ñîñòîÿíèå q0 è ñäâèíóòüñ÷èòûâàþùóþ ãîëîâêó íà îäíó ÿ÷åéêó âíàïðàâëåíèè D .ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÌÒ ðàáîòàåò íà áåñêîíå÷íîé ëåíòå, â êîòîðîé ïî÷òè âñå ÿ÷åéêèçàïîëíåíû ïóñòûì ñèìâîëîì 0 .
Âû÷èñëåíèÿ ÌÒ ìîæíîîïèñàòü â òåðìèíàõ ëåíòî÷íûõ êîíôèãóðàöèé.Ëåíòî÷íîé êîíôèãóðàöèåé ÌÒ M íàçûâàåòñÿ âñÿêîå ñëîâî(w 0 qxw 00 ) , ãäå w 0 , w 00 ∈ Γ∗ , q ∈ Q , x ∈ Γ . Òàêàÿ êîíôèãóðàöèÿñîäåðæàòåëüíî îçíà÷àåò, ÷òîI q ýòî òî ñîñòîÿíèå, â êîòîðîì íàõîäèòñÿ ÌÒ,I x ýòî áóêâà, êîòîðàÿ çàïèñàíà â òîé ÿ÷åéêå ëåíòû,êîòîðóþ îáîçðåâàåò ñ÷èòûâàþùàÿ ãîëîâêà ÌÒ,I w 0 ýòî ëåíòî÷íîå ñëîâî, ñîñòàâëåííîå èç ñèìâîëîâ,çàïèñàííûõ ñëåâà îò îáîçðåâàåìîé ÿ÷åéêè,I w 00 ýòî ëåíòî÷íîå ñëîâî, ñîñòàâëåííîå èç ñèìâîëîâ,çàïèñàííûõ ñïðàâà îò îáîçðåâàåìîé ÿ÷åéêè.Ïî óìîë÷àíèþ ñ÷èòàåòñÿ, ÷òî âî âñåõ îñòàëüíûõ ÿ÷åéêàõ ëåíòûçàïèñàíû ïóñòûå ñèìâîëû.ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ011110111q1Ëåíòî÷íàÿ êîíôèãóðàöèÿ: 0111q1 101111010ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀËåíòî÷íàÿ êîíôèãóðàöèÿ âèäà u q1 x víàçûâàåòñÿ íà÷àëüíîé êîíôèãóðàöèåé .Ëåíòî÷íàÿ êîíôèãóðàöèÿ âèäà u q0 x víàçûâàåòñÿ äîïóñêàþùåé êîíôèãóðàöèåé .Ëåíòî÷íàÿ êîíôèãóðàöèÿ âèäà u q−1 x víàçûâàåòñÿ îòâåðãàþùåé êîíôèãóðàöèåé .ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàæäàÿ êîìàíäà K çàäàåò îòíîøåíèå ïåðåõîäàK−→ íà ìíîæåñòâå ëåíòî÷íûõ êîíôèãóðàöèé:Kα −→ βÎíî îïðåäåëÿåòñÿ òàê:åñëè α = uzqxv è K = qx : yq0L , òî β = uq0zyv ,åñëè α = qxv è K = qx : yq0L , òî β = q00yv ,åñëè α = uqxzv è K = qx : yq0R , òî β = uyq0zv ,åñëè α = uqx è K = qx : yq0R , òî β = uyq00 .ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàæäàÿ êîìàíäà K çàäàåò îòíîøåíèå ïåðåõîäàK−→ íà ìíîæåñòâå ëåíòî÷íûõ êîíôèãóðàöèé:Kα −→ βÎíî îïðåäåëÿåòñÿ òàê:åñëè α = uzqxv è K = qx : yq0L , òî β = uq0zyv ,åñëè α = qxv è K = qx : yq0L , òî β = q00yv ,åñëè α = uqxzv è K = qx : yq0R , òî β = uyq0zv ,åñëè α = uqx è K = qx : yq0R , òî β = uyq00 .MÏðîãðàììà M çàäàåò îòíîøåíèå ïåðåõîäîâ −→íà ìíîæåñòâå ëåíòî÷íûõ êîíôèãóðàöèé:M−→=[K ∈TK−→ .ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÂû÷èñëåíèåì MT M èç íà÷àëüíîé êîíôèãóðàöèèα0 íàçûâàåòñÿ ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèéMMMM(α0 ) = α0 −→ α1 −→ α2 −→ · · ·êîòîðàÿ ëèáî ÿâëÿåòñÿ áåñêîíå÷íîé, ëèáîçàâåðøàåòñÿ äîïóñêàþùåé èëè îòâåðãàþùåéêîíôèãóðàöèåé.Âû÷èñëåíèå, îêàí÷èâàþùååñÿ äîïóñêàþùåéêîíôèãóðàöèåé, íàçûâàåòñÿ äîïóñêàþùèì .Âû÷èñëåíèå, îêàí÷èâàþùååñÿ îòâåðãàþùåéêîíôèãóðàöèåé, íàçûâàåòñÿ îòâåðãàþùèì .ÐÅÊÓÐÑÈÂÍÛÅ è ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈßçûê ÌÒ M ýòî ìíîæåñòâî L(M) âñåõ ñëîâw , w ∈ Σ∗ , äëÿ êîòîðûõ âû÷èñëåíèå èç íà÷àëüíîéêîíôèãóðàöèè α0 = q1w 0 ÿâëÿåòñÿ äîïóñêàþùèì:Mα0 = q1 w 0 −→∗ αN = uq0 v .ÐÅÊÓÐÑÈÂÍÛÅ è ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈßçûê ÌÒ M ýòî ìíîæåñòâî L(M) âñåõ ñëîâw , w ∈ Σ∗ , äëÿ êîòîðûõ âû÷èñëåíèå èç íà÷àëüíîéêîíôèãóðàöèè α0 = q1w 0 ÿâëÿåòñÿ äîïóñêàþùèì:Mα0 = q1 w 0 −→∗ αN = uq0 v .ßçûê L íàçûâàåòñÿ ðåêóðñèâíî ïåðå÷èñëèìûì ,åñëè L = L(M) äëÿ íåêîòîðîé ÌÒ M .ßçûê L íàçûâàåòñÿ ðåêóðñèâíûì, åñëè L = L(M)äëÿ íåêîòîðîé ÌÒ M , êîòîðàÿ îáëàäàåòñâîéñòâîì òîòàëüíîñòè , ò.å.
äëÿ ëþáîãî âõîäíîãîñëîâà w , w ∈ Σ∗ , âû÷èñëåíèå M èç íà÷àëüíîéêîíôèãóðàöèè α0 = q1w 0 ÿâëÿåòñÿ êîíå÷íûì.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÐåêóðñèâíîñòü ÿçûêà L îçíà÷àåò, ÷òî åñòü òàêàÿÌÒ M , êîòîðàÿ äëÿ êàæäîãî âõîäíîãî ñëîâàw , w ∈ Σ∗ , ìîæåò ñïóñòÿ êîíå÷íîå ÷èñëî øàãîââû÷èñëåíèÿ ïðàâèëüíî îòâåòèòü íà âîïðîñ,ïðèíàäëåæèò ëè w ÿçûêó L ëèáî óòâåðäèòåëüíî(âû÷èñëåíèå M(q0w 0) äîïóñêàþùåå), ëèáîîòðèöàòåëüíî (âû÷èñëåíèå M(q0w 0) îòâåðãàþùåå), ò.å. äàòü àëãîðèòìè÷åñêîå ðåøåíèåçàäà÷è ïðîâåðêè ïðèíàäëåæíîñòè ñëîâà ÿçûêó.Ïîòîìó ðåêóðñèâíûå ÿçûêè òàêæå íàçûâàþò(àëãîðèòìè÷åñêè) ðàçðåøèìûìè .ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈðåêóðñèâíûõ ÿçûêîâè L = Σ∗ ;Ïðèìåðû1.
L = ∅ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈðåêóðñèâíûõ ÿçûêîâ1. L = ∅ è L = Σ∗ ;2. ëþáîé ðåãóëÿðíûé ÿçûê L ;ÏðèìåðûÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈðåêóðñèâíûõ ÿçûêîâ1. L = ∅ è L = Σ∗ ;2. ëþáîé ðåãóëÿðíûé ÿçûê L ;3. L = {ww : w ∈ Σ∗} ;ÏðèìåðûÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈðåêóðñèâíûõ ÿçûêîâ1. L = ∅ è L = Σ∗ ;2. ëþáîé ðåãóëÿðíûé ÿçûê L ;3. L = {ww : w ∈ Σ∗} ;4. L = {ap : p ïðîñòîå ÷èñëî} ;ÏðèìåðûÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈðåêóðñèâíûõ ÿçûêîâ1. L = ∅ è L = Σ∗ ;2. ëþáîé ðåãóëÿðíûé ÿçûê L ;3.
L = {ww : w ∈ Σ∗} ;4. L = {ap : p ïðîñòîå ÷èñëî} ;5. L = {w : w ñèíòàêñè÷åñêè êîððåêòíûéòåêñò Ñ-ïðîãðàììû}ÏðèìåðûÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÐåêóðñèâíàÿ ïåðå÷èñëèìîñòü ÿçûêà L îçíà÷àåò,÷òî åñòü òàêàÿ ÌÒ M , êîòîðàÿ äëÿ êàæäîãîâõîäíîãî ñëîâà w , w ∈ Σ∗ , ñïóñòÿ êîíå÷íîå ÷èñëîøàãîâ âû÷èñëåíèÿ äàåò óòâåðäèòåëüíûé îòâåò íàâîïðîñ, ïðèíàäëåæèò ëè w ÿçûêó L â òîì èòîëüêî òîì ñëó÷àå, åñëè w ∈ L .Îäíàêî äëÿ òåõ ñëîâ, êîòîðûå íå ïðèíàäëåæàòÿçûêó L , ÌÒ M íå îáÿçàíà äàâàòüîòðèöàòåëüíûé îòâåò; â ýòèõ ñëó÷àÿõ îíà ìîæåòèìåòü áåñêîíå÷íîå âû÷èñëåíèå (çàöèêëèâàåòñÿ).ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÏîñêîëüêó â ñëó÷àå L = L(M) MT M ãàðàíòèðóåò ëèøü ÷àñòè÷íîå (òîëüêî óòâåðäèòåëüíîå)ðåøåíèå çàäà÷è î ïðèíàäëåæíîñòè ñëîâà ÿçûêó,ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè òàêæåíàçûâàþòñÿ ïîëóðàçðåøèìûìè ÿçûêàìè.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÏîñêîëüêó â ñëó÷àå L = L(M) MT M ãàðàíòèðóåò ëèøü ÷àñòè÷íîå (òîëüêî óòâåðäèòåëüíîå)ðåøåíèå çàäà÷è î ïðèíàäëåæíîñòè ñëîâà ÿçûêó,ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè òàêæåíàçûâàþòñÿ ïîëóðàçðåøèìûìè ÿçûêàìè.Èç îïðåäåëåíèÿ ðåêóðñèâíûõ è ðåêóðñèâíîïåðå÷èñëèìûõ ÿçûêîâ ÿñíî âèäíî, ÷òî êàæäûéðåêóðñèâíûé ÿçûê ÿâëÿåòñÿ ðåêóðñèâíîïåðå÷èñëèìûì.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÍî åñòü òàêæå âàæíûå âîïðîñû, îòâåòû íàêîòîðûõ íåî÷åâèäíû.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÍî åñòü òàêæå âàæíûå âîïðîñû, îòâåòû íàêîòîðûõ íåî÷åâèäíû.Ñóùåñòâóþò ëè ÿçûêè, íå ÿâëÿþùèåñÿðåêóðñèâíî ïåðå÷èñëèìûìè?Ñóùåñòâóþò ëè ðåêóðñèâíî ïåðå÷èñëèìûåÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíûìè?ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÍà ïåðâûé âîïðîñ ìîæíî äàòü óòâåðäèòåëüíûé îòâåò, íåïðèâëåêàÿ ãëóáîêèõ èññëåäîâàíèé.Òåîðåìà 4.1.
Ñóùåñòâóþò ÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíîïåðå÷èñëèìûìè.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÍà ïåðâûé âîïðîñ ìîæíî äàòü óòâåðäèòåëüíûé îòâåò, íåïðèâëåêàÿ ãëóáîêèõ èññëåäîâàíèé.Òåîðåìà 4.1. Ñóùåñòâóþò ÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíîïåðå÷èñëèìûìè.Äîêàçàòåëüñòâî. 1). Êàæäûé ðåêóðñèâíî ïåðå÷èñëèìûé ÿçûêL ñîñòîèò èç âñåõ ñëîâ, äîïóñêàåìûõ íåêîòîðîé ÌÒ M .Êàæäàÿ ÌÒ M ïîëíîñòüþ îïèñûâàåòñÿ íàáîðîì êîìàíä TMýòîé ìàøèíû, è ýòîò íàáîð êîìàíä ïðåäñòàâëÿåò ñîáîé ñëîâîíåêîòîðîãî ôèêñèðîâàííîãî êîíå÷íîãî àëôàâèòà.Çíà÷èò, êàæäûé ðåêóðñèâíî ïåðå÷èñëèìûé ÿçûê îïèñûâàåòñÿíåêîòîðûì ñëîâîì êîíå÷íîãî àëôàâèòà.Èç òåîðèè ìíîæåñòâ èçâåñòíî, ÷òî ìíîæåñòâî âñåõ ñëîâêîíå÷íîãî àëôàâèòà ñ÷åòíî. Òàêèì îáðàçîì, ñóùåñòâóåò òîëüêîñ÷åòíîå ìíîæåñòâî ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈ2).
ßçûê ýòî ïðîèçâîëüíîå ïîäìíîæåñòâîìíîæåñòâà âõîäíûõ ñëîâ Σ∗ .Èç òåîðèè ìíîæåñòâ èçâåñòíî, ÷òî ìíîæåñòâî âñåõ ñëîâ Σ∗ñ÷åòíî. Èç òåîðèè ìíîæåñòâ òàêæå èçâåñòíî, ÷òî ñåìåéñòâîâñåõ ïîäìíîæåñòâ ñ÷åòíîãî ìíîæåñòâà, íå ÿâëÿåòñÿ ñ÷åòíûì.Òàêèì îáðàçîì, ìíîæåñòâî âñåõ ÿçûêîâ íåñ÷åòíî.Äîêàçàòåëüñòâî.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈ2).
ßçûê ýòî ïðîèçâîëüíîå ïîäìíîæåñòâîìíîæåñòâà âõîäíûõ ñëîâ Σ∗ .Èç òåîðèè ìíîæåñòâ èçâåñòíî, ÷òî ìíîæåñòâî âñåõ ñëîâ Σ∗ñ÷åòíî. Èç òåîðèè ìíîæåñòâ òàêæå èçâåñòíî, ÷òî ñåìåéñòâîâñåõ ïîäìíîæåñòâ ñ÷åòíîãî ìíîæåñòâà, íå ÿâëÿåòñÿ ñ÷åòíûì.Òàêèì îáðàçîì, ìíîæåñòâî âñåõ ÿçûêîâ íåñ÷åòíî.Çíà÷èò, èç ñðàâíåíèÿ ìîùíîñòè ñåìåéñòâà âñåõ ÿçûêîâ èñåìåéñòâà ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ ñëåäóåò, ÷òîñóùåñòâóþò ÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíî ïåðå÷èñëèìûìè.QEDÄîêàçàòåëüñòâî.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÀ âîò äëÿ îòâåòà íà âòîðîé âîïðîñÑóùåñòâóþò ëè ðåêóðñèâíî ïåðå÷èñëèìûåÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíûìè?ìàòåìàòèêàì ïðèøëîñü ñîçäàòü öåëóþ òåîðèþ,êîòîðàÿ ñóùåñòâåííî ïîâëèÿëà íà ðàçâèòèå íàøåéöèâèëèçàöèè.ÐÅÊÓÐÑÈÂÍÛÅ È ÐÅÊÓÐÑÈÂÍÎÏÅÐÅ×ÈÑËÈÌÛÅ ßÇÛÊÈÀ âîò äëÿ îòâåòà íà âòîðîé âîïðîñÑóùåñòâóþò ëè ðåêóðñèâíî ïåðå÷èñëèìûåÿçûêè, íå ÿâëÿþùèåñÿ ðåêóðñèâíûìè?ìàòåìàòèêàì ïðèøëîñü ñîçäàòü öåëóþ òåîðèþ,êîòîðàÿ ñóùåñòâåííî ïîâëèÿëà íà ðàçâèòèå íàøåéöèâèëèçàöèè.Íî âíà÷àëå ïîïðîáóåì âûÿñíèòü, íàñêîëüêîñóùåñòâåííî èçìåíÿþòñÿ âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèí Òüþðèíãà ïðè âíåñåíèèíåêîòîðûõ èçìåíåíèé â èõ óñòðîéñòâî.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÏîïðîáóåì âíà÷àëå îñëàáèòü âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèí Òüþðèíãà, óïðîùàÿ èõóñòðîéñòâî.Ðàññìîòðèì âû÷èñëèòåëüíîå óñòðîéñòâî,îòëè÷àþùååñÿ îò ¾îáû÷íîé¿ ìàøèíû Òüþðèíãàëèøü òåì, ÷òî ëåíòà, íà êîòîðîé ðàáîòàåò ýòîóñòðîéñòâî, áåñêîíå÷íà ëèøü â îäíó ñòîðîíó(íàïðèìåð, âïðàâî).
Íàçîâåì ýòî óñòðîéñòâîîäíîñòîðîííåé ìàøèíîé Òüþðèíãà .Äëÿ îäíîñòîðîííèõ ÌÒ ìîæíî òàêæå îïðåäåëèòüÿçûê, ñîñòîÿùèé èç âõîäíûõ ñëîâ, íà êîòîðûõ ÌÒçàâåðøàåò âû÷èñëåíèå â äîïóñêàþùåì ñîñòîÿíèè.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒåîðåìà 4.2.1). Äëÿ ëþáîé 1-ñòîðîííåé ÌÒ M1 ñóùåñòâóåòòàêàÿ 2-ñòîðîííÿÿ ÌÒ M2 , ÷òî L(M1) = L(M2) .2). Äëÿ ëþáîé 2-ñòîðîííåé ÌÒ M2 ñóùåñòâóåòòàêàÿ 1-ñòîðîííÿÿ ÌÒ M1 , ÷òî L(M2) = L(M1) .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒåîðåìà 4.2.1). Äëÿ ëþáîé 1-ñòîðîííåé ÌÒ M1 ñóùåñòâóåòòàêàÿ 2-ñòîðîííÿÿ ÌÒ M2 , ÷òî L(M1) = L(M2) .2). Äëÿ ëþáîé 2-ñòîðîííåé ÌÒ M2 ñóùåñòâóåòòàêàÿ 1-ñòîðîííÿÿ ÌÒ M1 , ÷òî L(M2) = L(M1) .Äîêàçàòåëüñòâî.1). Î÷åâèäíî.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2). Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d a d d c b 0 ···⇑ q2ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2).
Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d a d d c b 0 ···⇑ q2Ðàçäåëèì ëåíòó íà äâå ïîëîâèíû...ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2). Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d a d d c b 0 ···⇑ q2` c b a 0 0 0` d a d d c b 0⇑ q2······Ðàçäåëèì ëåíòó íà äâå ïîëîâèíûè ðàçîðâåì åå ïîïîëàì.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2). Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d a d d c b 0 ···⇑ q2c`` dba⇑ q2ad0d0c0b···0 ···Ïîòîì ðàçäâèíåì ñîäåðæèìîå îáåèõ ëåíò è...ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2). Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d a d d c b 0 ···⇑ q2` d c a b d a d 0 c 0 b 0 0 ···⇑ q2Ïîòîì ðàçäâèíåì ñîäåðæèìîå îáåèõ ëåíò èðàçìåñòèì åãî íà îäíîé ëåíòå.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
