4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки (1162495), страница 2
Текст из файла (страница 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Ïîëó÷èì îäíîëåíòî÷íóþ ÌÒ M1 , êîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2). Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c d c d d c b 0 ···⇑ q3` d c c b d a d 0 c 0 b 0 0 ···⇑ q3Ïîëó÷èì îäíîëåíòî÷íóþ ÌÒ M1 , êîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÌÒ M2 .2).
Ðàññìîòðèì 2-ñòîðîííþþ··· 0 a b c 0 c d d c b 0 ···⇑ q5` 0 c c b d a d 0 c 0 b 0 0 ···⇑ q5Ïîëó÷èì îäíîëåíòî÷íóþ ÌÒ M1 , êîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒàêèì îáðàçîì, îäíîñòðîííèå ìàøèíû Òüþðèíãàîáëàäàþò òî÷íî òàêèìè æå âû÷èñëèòåëüíûìèâîçìîæíîñòÿìè, êàê è äâóñòîðîííèå (¾îáû÷íûå¿)ìàøèíû Òüþðèíãà.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒàêèì îáðàçîì, îäíîñòðîííèå ìàøèíû Òüþðèíãàîáëàäàþò òî÷íî òàêèìè æå âû÷èñëèòåëüíûìèâîçìîæíîñòÿìè, êàê è äâóñòîðîííèå (¾îáû÷íûå¿)ìàøèíû Òüþðèíãà.À òåïåðü ïîïðîáóåì óñèëèòü âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèí Òüþðèíãà.Ðàññìîòðèì âû÷èñëèòåëüíîå óñòðîéñòâî,îòëè÷àþùååñÿ îò ¾îáû÷íîé¿ ìàøèíû Òüþðèíãàëèøü òåì, ÷òî îíî ðàáîòàåò íà íåñêîëüêèõ ëåíòàõ.Íà êàæäîé ëåíòå åñòü ñâîÿ ñ÷èòûâàþùàÿ ãîëîâêà.Êàæäîå ñîñòîÿíèå q òàêîé ÌÒ ïðèïèñàíî ê îäíîéèç ëåíò, è â ýòîì ñîñòîÿíèè ÌÒ óïðàâëÿåòñ÷èòûâàþùåé ãîëîâêîé ñîîòâåòñòâóþùåé ëåíòû.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÌàøèíû Òüþðèíãà òàêîãî âèäà íàçûâàþòñÿìíîãîëåíòî÷íûìè ÌÒ.Îäíà èç ëåíò ìíîãîëåíòî÷íîé ìàøèíû âûäåëåíàêàê âõîäíàÿ ëåíòà.
 íà÷àëå âû÷èñëåíèÿ íàâõîäíîé ëåíòå çàïèñûâàåòñÿ âõîäíîå ñëîâî.Îñòàëüíûå ëåíòû íàçûâàþòñÿ ðàáî÷èìè ; â íà÷àëåâû÷èñëåíèÿ ðàáî÷èå ëåíòû çàïîëíåíû ïóñòûìèáóêâàìè.Äëÿ ìíîãîëåíòî÷íûõ ÌÒ ìîæíî òàêæåîïðåäåëèòü ÿçûê, ñîñòîÿùèé èç âõîäíûõ ñëîâ, íàêîòîðûõ ÌÒ çàâåðøàåò âû÷èñëåíèå âäîïóñêàþùåì ñîñòîÿíèè.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒåîðåìà 4.3.1). Äëÿ ëþáîé 1-ëåíòî÷íîé ÌÒ M1 ñóùåñòâóåòòàêàÿ n-ëåíòî÷íàÿ ÌÒ Mn , ÷òî L(M1) = L(Mn ) .2). Äëÿ ëþáîé n-ëåíòî÷íàÿ ÌÒ Mn ñóùåñòâóåòòàêàÿ 1-ëåíòî÷íàÿ ÌÒ M1 , ÷òî L(Mn ) = L(M1) .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒåîðåìà 4.3.1).
Äëÿ ëþáîé 1-ëåíòî÷íîé ÌÒ M1 ñóùåñòâóåòòàêàÿ n-ëåíòî÷íàÿ ÌÒ Mn , ÷òî L(M1) = L(Mn ) .2). Äëÿ ëþáîé n-ëåíòî÷íàÿ ÌÒ Mn ñóùåñòâóåòòàêàÿ 1-ëåíòî÷íàÿ ÌÒ M1 , ÷òî L(Mn ) = L(M1) .Äîêàçàòåëüñòâî.1). Î÷åâèäíî.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑12341234123×òîáû ïîñòðîèòü 1-ëåíòî÷íóþ ÌÒ,ðàçîáüåì åå ëåíòó íà 4 ðåøåòêè,41234ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑12a3412b3412câ ÿ÷åéêàõ ðåøåòêè 2 ïîìåñòèìñîäåðæèìîå 1-îé ëåíòû ÌÒ M2 ,3412b34ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑120 a34120 b3412⇑ c34120 b34à â îäíîé èç ÿ÷ååê ðåøåòêè 1 îòìåòèì ïîëîæåíèåñ÷èòûâàþùåé ãîëîâêè íà 1-îé ëåíòû ÌÒ M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑12341234123412340 a 0 x 0 b ⇑ x ⇑ c 0 y 0 b 0 zÒî æå ñàìîå ïðîäåëàåì íà ðåøåòêàõ 3 è 4äëÿ ñîäåðæèìîãî 2-îé ëåíòû ÌÒ M2ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b c b ···⇑ q2··· x x y z ···⇑12341234123412340 a 0 x 0 b ⇑ x ⇑ c 0 y 0 b 0 z⇑ q2ÌÒ M1 ,Ïîëó÷èì îäíîëåíòî÷íóþêîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b d b ···⇑··· x x y z ···⇑ q712341234123412340 a 0 x 0 b ⇑ x ⇑ c 0 y 0 b 0 z⇑ q2ÌÒ M1 ,Ïîëó÷èì îäíîëåíòî÷íóþêîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b d b ···⇑··· x x y z ···⇑ q712341234123412340 a 0 x ⇑ b ⇑ x 0 d 0 y 0 b 0 z⇑ q0Ïîëó÷èì îäíîëåíòî÷íóþ ÌÒ M1 , êîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .2ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ2) Ðàññìîòðèì 2-ëåíòî÷íóþ ÌÒ M2 .··· a b d b ···⇑··· x x y z ···⇑ q712341234123412340 a 0 x ⇑ b ⇑ x 0 d 0 y 0 b 0 z⇑ q7Ïîëó÷èì îäíîëåíòî÷íóþ ÌÒ M1 , êîòîðàÿìîæåò ñèìóëèðîâàòü âû÷èñëåíèÿ MT M2 .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÊàê âèäíî, âû÷èñëèòåëüíûå âîçìîæíîñòè âñåõn-ëåíòî÷íûõ ÌÒ îäèíàêîâû äëÿ ëþáûõ n, n ≥ 1.Ïîýòîìó äàëåå áóäåì ðàâíîïðàâíî èñïîëüçîâàòüâñå ýòè âàðèàíòû ÌÒ.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÊàê âèäíî, âû÷èñëèòåëüíûå âîçìîæíîñòè âñåõn-ëåíòî÷íûõ ÌÒ îäèíàêîâû äëÿ ëþáûõ n, n ≥ 1.Ïîýòîìó äàëåå áóäåì ðàâíîïðàâíî èñïîëüçîâàòüâñå ýòè âàðèàíòû ÌÒ.Âîñïîëüçóåìñÿ ýòîé âîçìîæíîñòüþ, ÷òîáûäîêàçàòü ñëåäóþùèå òåîðåìû, óñòàíàâëèâàþùèåâçàèìîñâÿçü ìåæäó ðåêóðñèâíûìè è ðåêóðñèâíîïåðå÷èñëèìûìè ÿçûêàìè.Òåîðåìà 4.4.
ßçûê L ÿâëÿåòñÿ ðåêóðñèâíûìòîãäà è òîëüêî òîãäà, êîãäà îáà ÿçûêà L è Σ∗ \ Lÿâëÿþòñÿ ðåêóðñèâíî ïåðå÷èñëèìûìè.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî. (⇒ ) Åñëè L = L(M) è M òîòàëüíàÿ ÌÒ,òî ïîìåíÿâ â íåé ìåñòàìè äîïóñêàþùåå è îòâåðãàþùååñîñòîÿíèÿ q0 è q−1 , ïîëó÷èì ÌÒ, ðàñïîçíàþùóþ ÿçûê Σ∗ \ L .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî. (⇒ ) Åñëè L = L(M) è M òîòàëüíàÿ ÌÒ,òî ïîìåíÿâ â íåé ìåñòàìè äîïóñêàþùåå è îòâåðãàþùååñîñòîÿíèÿ q0 è q−1 , ïîëó÷èì ÌÒ, ðàñïîçíàþùóþ ÿçûê Σ∗ \ L .(⇐ ) Ïðåäïîëîæèì, ÷òî L = L(M1) è Σ∗ \ L = L(M2) .Ïîñòðîèì 3-ëåíòî÷íóþ òîòàëüíóþ ÌÒ M0 , ðàñïîçíàþùóþÿçûê L .
Ýòà ìàøèíà ðàáîòàåò òàê.1. Êîïèðóåò ñîäåðæèìîå âõîäíîé ëåíòû íà äâå ðàáî÷èåëåíòû.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî. (⇒ ) Åñëè L = L(M) è M òîòàëüíàÿ ÌÒ,òî ïîìåíÿâ â íåé ìåñòàìè äîïóñêàþùåå è îòâåðãàþùååñîñòîÿíèÿ q0 è q−1 , ïîëó÷èì ÌÒ, ðàñïîçíàþùóþ ÿçûê Σ∗ \ L .(⇐ ) Ïðåäïîëîæèì, ÷òî L = L(M1) è Σ∗ \ L = L(M2) .Ïîñòðîèì 3-ëåíòî÷íóþ òîòàëüíóþ ÌÒ M0 , ðàñïîçíàþùóþÿçûê L . Ýòà ìàøèíà ðàáîòàåò òàê.1. Êîïèðóåò ñîäåðæèìîå âõîäíîé ëåíòû íà äâå ðàáî÷èåëåíòû.2. Çàïóñêàåò íà ðàáî÷èõ ëåíòàõ ÌÒ M1 è M2 è ÷åðåäóåòøàãè âû÷èñëåíèÿ ýòèõ ìàøèí.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî. (⇒ ) Åñëè L = L(M) è M òîòàëüíàÿ ÌÒ,òî ïîìåíÿâ â íåé ìåñòàìè äîïóñêàþùåå è îòâåðãàþùååñîñòîÿíèÿ q0 è q−1 , ïîëó÷èì ÌÒ, ðàñïîçíàþùóþ ÿçûê Σ∗ \ L .(⇐ ) Ïðåäïîëîæèì, ÷òî L = L(M1) è Σ∗ \ L = L(M2) .Ïîñòðîèì 3-ëåíòî÷íóþ òîòàëüíóþ ÌÒ M0 , ðàñïîçíàþùóþÿçûê L .
Ýòà ìàøèíà ðàáîòàåò òàê.1. Êîïèðóåò ñîäåðæèìîå âõîäíîé ëåíòû íà äâå ðàáî÷èåëåíòû.2. Çàïóñêàåò íà ðàáî÷èõ ëåíòàõ ÌÒ M1 è M2 è ÷åðåäóåòøàãè âû÷èñëåíèÿ ýòèõ ìàøèí.3. Åñëè ÌÒ M1 çàâåðøàåò ñâîå âû÷èñëåíèå â äîïóñêàþùåìñîñòîÿíèè, òî ÌÒ M0 ïåðåõîäèò â äîïóñêàþùååñîñòîÿíèå.
Åñëè â äîïóñêàþùåì ñîñòîÿíèè çàâåðøàåò ñâîåâû÷èñëåíèå ÌÒ M2 , òî ÌÒ M0 ïåðåõîäèò â îòâåðãàþùååñîñòîÿíèå.QEDÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÏóñòü # ∈/ Σ . Îáîçíà÷èì çàïèñüþ Σ∗#Σ∗ìíîæåñòâî ñëîâ {u#v : u, v ∈ Σ∗} .ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÏóñòü # ∈/ Σ . Îáîçíà÷èì çàïèñüþ Σ∗#Σ∗ìíîæåñòâî ñëîâ {u#v : u, v ∈ Σ∗} .Òåîðåìà 4.5. ßçûê L ÿâëÿåòñÿ ðåêóðñèâíîïåðå÷èñëèìûì òîãäà è òîëüêî òîãäà, êîãäàñóùåñòâóåò òàêîé ðåêóðñèâíûé ÿçûê Lb ⊆ Σ∗#Σ∗ ,äëÿ êîòîðîãî âåðíî ðàâåíñòâîb .L = {w : ∃u w #u ∈ L}Äîêàçàòåëüñòâî. (⇒) Ïóñòü L = L(M) . Äëÿ êàæäîãî ñëîâàw , w ∈ L, îáîçíà÷èì çàïèñüþ t(w ) ÷èñëî òàêòîâ âû÷èñëåíèÿÌÒ M ïðè ðàáîòå íà âõîäíîì ñëîâå w .Ðàññìîòðèì ÿçûê Lb = {w #u : w ∈ L, |u| > t(w )} .Äîêàçàòåëüñòâî. (⇒) Ïóñòü L = L(M) . Äëÿ êàæäîãî ñëîâàw , w ∈ L, îáîçíà÷èì çàïèñüþ t(w ) ÷èñëî òàêòîâ âû÷èñëåíèÿÌÒ M ïðè ðàáîòå íà âõîäíîì ñëîâå w .Ðàññìîòðèì ÿçûê Lb = {w #u : w ∈ L, |u| > t(w )} .b .Î÷åâèäíî, ÷òî L = {w : ∃u w #u ∈ L}Äîêàçàòåëüñòâî.
(⇒) Ïóñòü L = L(M) . Äëÿ êàæäîãî ñëîâàw , w ∈ L, îáîçíà÷èì çàïèñüþ t(w ) ÷èñëî òàêòîâ âû÷èñëåíèÿÌÒ M ïðè ðàáîòå íà âõîäíîì ñëîâå w .Ðàññìîòðèì ÿçûê Lb = {w #u : w ∈ L, |u| > t(w )} .b .Î÷åâèäíî, ÷òî L = {w : ∃u w #u ∈ L}c ðàáîòàåò òàê.3-ëåíòî÷íàÿ ÌÒ M1. Ïîëó÷èâ âõîäíîå ñëîâî wb = w #u , êîïèðóåò ñëîâà w è uíà äâå ðàáî÷èå ëåíòû.Äîêàçàòåëüñòâî. (⇒) Ïóñòü L = L(M) . Äëÿ êàæäîãî ñëîâàw , w ∈ L, îáîçíà÷èì çàïèñüþ t(w ) ÷èñëî òàêòîâ âû÷èñëåíèÿÌÒ M ïðè ðàáîòå íà âõîäíîì ñëîâå w .Ðàññìîòðèì ÿçûê Lb = {w #u : w ∈ L, |u| > t(w )} .b .Î÷åâèäíî, ÷òî L = {w : ∃u w #u ∈ L}c ðàáîòàåò òàê.3-ëåíòî÷íàÿ ÌÒ M1. Ïîëó÷èâ âõîäíîå ñëîâî wb = w #u , êîïèðóåò ñëîâà w è uíà äâå ðàáî÷èå ëåíòû.2.
Çàïóñêàåò íà ïåðâîé ðàáî÷åé ëåíòå ÌÒ M è ñ êàæäûìòàêòîì åå ðàáîòû ñòèðàåò îäíó áóêâó â ñëîâå u .Äîêàçàòåëüñòâî. (⇒) Ïóñòü L = L(M) . Äëÿ êàæäîãî ñëîâàw , w ∈ L, îáîçíà÷èì çàïèñüþ t(w ) ÷èñëî òàêòîâ âû÷èñëåíèÿÌÒ M ïðè ðàáîòå íà âõîäíîì ñëîâå w .Ðàññìîòðèì ÿçûê Lb = {w #u : w ∈ L, |u| > t(w )} .b .Î÷åâèäíî, ÷òî L = {w : ∃u w #u ∈ L}c ðàáîòàåò òàê.3-ëåíòî÷íàÿ ÌÒ M1. Ïîëó÷èâ âõîäíîå ñëîâî wb = w #u , êîïèðóåò ñëîâà w è uíà äâå ðàáî÷èå ëåíòû.2.
Çàïóñêàåò íà ïåðâîé ðàáî÷åé ëåíòå ÌÒ M è ñ êàæäûìòàêòîì åå ðàáîòû ñòèðàåò îäíó áóêâó â ñëîâå u .3. Åñëè ÌÒ M çàâåðøàåò âû÷èñëåíèå íà ïåðâîé ðàáî÷åéëåíòå â äîïóñêàþùåì ñîñòîÿíèè è ïðè ýòîì âòîðàÿc äîïóñêàåò ñëîâî wb.ðàáî÷àÿ ëåíòà íåïóñòà, òî ÌÒ MÅñëè ÌÒ M çàâåðøàåò âû÷èñëåíèå íà ïåðâîé ðàáî÷åéëåíòå â îòâåðãàþùåì ñîñòîÿíèè èëè âòîðàÿ ëåíòàc îòâåðãàåò ñëîâî wb.îïóñòîøàåòñÿ, òî ÌÒ Mcc = Lb .Íåòðóäíî âèäåòü, ÷òî M òîòàëüíàÿ ÌÒ, è L(M)Äîêàçàòåëüñòâî.
(⇐c .) Ïóñòü Lb = L(M)3-ëåíòî÷íàÿ ÌÒ M , ïîëó÷èâ âõîäíîå ñëîâî w , âûïîëíÿåòáåñêîíå÷íûé öèêë.Äîêàçàòåëüñòâî. (⇐c .) Ïóñòü Lb = L(M)3-ëåíòî÷íàÿ ÌÒ M , ïîëó÷èâ âõîäíîå ñëîâî w , âûïîëíÿåòáåñêîíå÷íûé öèêë.1. Íà ïåðâîé ðàáî÷åé ëåíòå M ïîðîæäàåò âñå ñëîâà âàëôàâèòå Σ ïîî÷åðåäíî â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå,ïî îäíîìó ñëîâó u íà êàæäîé èòåðàöèè öèêëà.Äîêàçàòåëüñòâî.
(⇐c .) Ïóñòü Lb = L(M)3-ëåíòî÷íàÿ ÌÒ M , ïîëó÷èâ âõîäíîå ñëîâî w , âûïîëíÿåòáåñêîíå÷íûé öèêë.1. Íà ïåðâîé ðàáî÷åé ëåíòå M ïîðîæäàåò âñå ñëîâà âàëôàâèòå Σ ïîî÷åðåäíî â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå,ïî îäíîìó ñëîâó u íà êàæäîé èòåðàöèè öèêëà.2. Ïîñëå òîãî, êàê íà î÷åðåäíîé èòåðàöèè öèêëà ÌÒ Mñãåíåðèðîâàëà íà ðàáî÷åé ëåíòå ñëîâî u , îíà ôîðìèðóåòíà âòîðîé ðàáî÷åé ëåíòå ñëîâî wb = w #u è çàïóñêàåò íàc .
Åñëè Mc äîïóñêàåò ñëîâî wb , òî ÌÒ Mýòîì ñëîâå ÌÒ Mçàâåðøàåò ðàáîòó è ïåðåõîäèò â äîïóñêàþùåå ñîñòîÿíèå.c îòâåðãàåò ñëîâî wb , òî ÌÒ M ïðîäîëæàåòÅñëè Mâûïîëíåíèå öèêëà è ïîðîæäàåò íà ïåðâîé ðàáî÷åé ëåíòåî÷åðåäíîå ñëîâî.b = L.Íåòðóäíî âèäåòü, ÷òî L(M) = {w : ∃u w #u ∈ L}QEDÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàæèòå, ÷òî âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèíû Òüþðèíãà íå èçìåíÿþòñÿ,åñëè åå âìåñòî áåñêîíå÷íîé ëåíòû ñíàáäèòü1. äâóìÿ áåñêîíå÷íûìè ñòåêàìè (ìàãàçèíàìè);2. áåñêîíå÷íîé ïëîñêîñòüþ, ðàçáèòîé íà ÿ÷åéêè,ïîäîáíî ëåíòå.Çàäà÷à 4.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
