5. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем (1162496), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

×òîáû ïðîâåðèòüñàìîïðèìåíèìîñòü ÌÒ M íåîáõîäèìî èäîñòàòî÷íî ïðîâåðèòü òîòàëüíîñòü ÌÒErase; WriteM ; M,ãäå Erase ýòî ÌÒ, êîòîðàÿ ñòèðàåò âõîäíîåñëîâî.QEDÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÓòâåðæäåíèå 5.6.ßçûêEQ = {code(M1 )#code(M2 ) : L(M1 ) = L(M2 )}(ïðîáëåìà ýêâèâàëåíòíîñòè ÌÒ) íåðåêóðñèâåí.ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÓòâåðæäåíèå 5.6.ßçûêEQ = {code(M1 )#code(M2 ) : L(M1 ) = L(M2 )}(ïðîáëåìà ýêâèâàëåíòíîñòè ÌÒ) íåðåêóðñèâåí.Äîêàçàòåëüñòâî.

×òîáû ïðîâåðèòü òîòàëüíîñòüÌÒ M íåîáõîäèìî è äîñòàòî÷íî ïðîâåðèòüýêâèâàëåíòíîñòü ÌÒ M è ÌÒ M0 , ïðîãðàììàêîòîðîé ñîñòîèò òîëüêî èç êîìàíä(q1 x : xq0 L), x ∈ Γ .QEDÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÓòâåðæäåíèå 5.6.ßçûêEQ = {code(M1 )#code(M2 ) : L(M1 ) = L(M2 )}(ïðîáëåìà ýêâèâàëåíòíîñòè ÌÒ) íåðåêóðñèâåí.Äîêàçàòåëüñòâî. ×òîáû ïðîâåðèòü òîòàëüíîñòüÌÒ M íåîáõîäèìî è äîñòàòî÷íî ïðîâåðèòüýêâèâàëåíòíîñòü ÌÒ M è ÌÒ M0 , ïðîãðàììàêîòîðîé ñîñòîèò òîëüêî èç êîìàíä(q1 x : xq0 L), x ∈ Γ .QEDÀ íåëüçÿ ëè âñå ïîäîáíûå àëãîðèòìè÷åñêèåïðîáëåìû, êàñàþùèåñÿ ñâîéñòâ âû÷èñëåíèé ÌÒ,ðåøèòü ðàç è íàâñåãäà ¾â îáùåì âèäå¿?ÒÅÎÐÅÌÀ ÐÀÉÑÀÌÎÆÍÎ!!!Ðàññìîòðèì ìíîæåñòâî âñåõ ñëîâ, ÿâëÿþùèõñÿêîäàìè ÌÒ: CODE = {code(M) : M ýòî ÌÒ} .Áóäåì íàçûâàòü ÿçûê Prop, Prop ⊆ CODEñåìàíòè÷åñêèì ñâîéñòâîì ÌÒ (îòíîñèòåëüíîêîäèðîâàíèÿ code MT), åñëè ýòîò ÿçûêóäîâëåòâîðÿåò ñëåäóþùåìó òðåáîâàíèþ:∀M1 ,M2(L(M1 ) = L(M2 )∧code(M1 ) ∈ Prop ⇒ code(M1 ) ∈ Prop)ÒÅÎÐÅÌÀ ÐÀÉÑÀÌÎÆÍÎ!!!Ðàññìîòðèì ìíîæåñòâî âñåõ ñëîâ, ÿâëÿþùèõñÿêîäàìè ÌÒ: CODE = {code(M) : M ýòî ÌÒ} .Áóäåì íàçûâàòü ÿçûê Prop, Prop ⊆ CODEñåìàíòè÷åñêèì ñâîéñòâîì ÌÒ (îòíîñèòåëüíîêîäèðîâàíèÿ code MT), åñëè ýòîò ÿçûêóäîâëåòâîðÿåò ñëåäóþùåìó òðåáîâàíèþ:∀M1 ,M2(L(M1 ) = L(M2 )∧code(M1 ) ∈ Prop ⇒ code(M1 ) ∈ Prop)Ñâîéñòâî ÌÒ Prop, Prop ⊆ CODE , íàçûâàåòñÿíåòðèâèàëüíûì , åñëè Prop 6= ∅ è Prop 6= CODE .ÒÅÎÐÅÌÀ ÐÀÉÑÀÍàïðèìåð,I(ïðîáëåìàîñòàíîâà íà ïóñòîé ëåíòå) íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : ε ∈ L(M)}ÒÅÎÐÅÌÀ ÐÀÉÑÀÍàïðèìåð,II(ïðîáëåìàîñòàíîâà íà ïóñòîé ëåíòå) íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : |L(M)| = 99} íåòðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : ε ∈ L(M)}ÒÅÎÐÅÌÀ ÐÀÉÑÀÍàïðèìåð,III(ïðîáëåìàîñòàíîâà íà ïóñòîé ëåíòå) íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : |L(M)| = 99} íåòðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;∅ òðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : ε ∈ L(M)}ÒÅÎÐÅÌÀ ÐÀÉÑÀÍàïðèìåð,IIII(ïðîáëåìàîñòàíîâà íà ïóñòîé ëåíòå) íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : |L(M)| = 99} íåòðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;∅ òðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;{code(M) : |code(M)| = 99} íåòðèâèàëüíîå íåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : ε ∈ L(M)}ÒÅÎÐÅÌÀ ÐÀÉÑÀÍàïðèìåð,IIIII(ïðîáëåìàîñòàíîâà íà ïóñòîé ëåíòå) íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî;K = {code(M) : |L(M)| = 99} íåòðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;∅ òðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâî;{code(M) : |code(M)| = 99} íåòðèâèàëüíîå íåñåìàíòè÷åñêîå ñâîéñòâî;S = {code(M) : code(M) ∈ L(M)} íåòðèâèàëüíîå íåñåìàíòè÷åñêîå ñâîéñòâî.K = {code(M) : ε ∈ L(M)}ÒÅÎÐÅÌÀ ÐÀÉÑÀËþáîå íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî ÌÒ íåðåêóðñèâíî.Òåîðåìà 5.7.

[Ðàéñà]ÒÅÎÐÅÌÀ ÐÀÉÑÀËþáîå íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî ÌÒ íåðåêóðñèâíî.Äîêàçàòåëüñòâî. Ïóñòü Prop íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî. Âîçüìåì ëþáóþ òàêóþÌÒ M0 , ÷òî L(M0) = ∅ . Áóäåì ïîëàãàòü (äëÿîïðåäåëåííîñòè), ÷òî code(M0) ∈/ Prop .  ñëó÷àåcode(M0 ) ∈ Prop âñå ïîñëåäóþùèå ðàññóæäåíèÿïðîâîäÿòñÿ àíàëîãè÷íî.Òåîðåìà 5.7.

[Ðàéñà]ÒÅÎÐÅÌÀ ÐÀÉÑÀËþáîå íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî ÌÒ íåðåêóðñèâíî.Äîêàçàòåëüñòâî. Ïóñòü Prop íåòðèâèàëüíîåñåìàíòè÷åñêîå ñâîéñòâî. Âîçüìåì ëþáóþ òàêóþÌÒ M0 , ÷òî L(M0) = ∅ . Áóäåì ïîëàãàòü (äëÿîïðåäåëåííîñòè), ÷òî code(M0) ∈/ Prop .  ñëó÷àåcode(M0 ) ∈ Prop âñå ïîñëåäóþùèå ðàññóæäåíèÿïðîâîäÿòñÿ àíàëîãè÷íî.Ïîñêîëüêó Prop íåòðèâèàëüíîå ñâîéñòâî ÌÒ,ñóùåñòâóåò è òàêàÿ ÌÒ M1 , ÷òî code(M1) ∈ Prop .Òåîðåìà 5.7.

[Ðàéñà]ÒÅÎÐÅÌÀ ÐÀÉÑÀÏîêàæåì, ÷òî ÿçûê K (ïðîáëåìà îñòàíîâà ÌÒ íà ïóñòîé ëåíòå)m-ñâîäèì ê ÿçûêó Prop .ÒÅÎÐÅÌÀ ÐÀÉÑÀÏîêàæåì, ÷òî ÿçûê K (ïðîáëåìà îñòàíîâà ÌÒ íà ïóñòîé ëåíòå)m-ñâîäèì ê ÿçûêó Prop .×òîáû ïðîâåðèòü âêëþ÷åíèå code(M) ∈ K äëÿ ïðîèçâîëüíîéc , êîòîðàÿ íà âñÿêîì âõîäíîìÌÒ M òðàíñëèðóåì åå â ÌÒ Mñëîâå w ðàáîòàåò òàê:c 1 w 0) = if ε ∈ L(M) then M1 (q1 w 0) else loop.M(qÒÅÎÐÅÌÀ ÐÀÉÑÀÏîêàæåì, ÷òî ÿçûê K (ïðîáëåìà îñòàíîâà ÌÒ íà ïóñòîé ëåíòå)m-ñâîäèì ê ÿçûêó Prop .×òîáû ïðîâåðèòü âêëþ÷åíèå code(M) ∈ K äëÿ ïðîèçâîëüíîéc , êîòîðàÿ íà âñÿêîì âõîäíîìÌÒ M òðàíñëèðóåì åå â ÌÒ Mñëîâå w ðàáîòàåò òàê:c 1 w 0) = if ε ∈ L(M) then M1 (q1 w 0) else loop.M(qc âèäíî, ÷òîÈç îïèñàíèÿ ÌÒ Mc íà ëþáîì âõîäíîì ñëîâå wI åñëè code(M) ∈ K , òî ÌÒ Mc = L(M1 ) ;ðàáîòàåò êàê ÌÒ M1 ; â ýòîì ñëó÷àå L(M)ÒÅÎÐÅÌÀ ÐÀÉÑÀÏîêàæåì, ÷òî ÿçûê K (ïðîáëåìà îñòàíîâà ÌÒ íà ïóñòîé ëåíòå)m-ñâîäèì ê ÿçûêó Prop .×òîáû ïðîâåðèòü âêëþ÷åíèå code(M) ∈ K äëÿ ïðîèçâîëüíîéc , êîòîðàÿ íà âñÿêîì âõîäíîìÌÒ M òðàíñëèðóåì åå â ÌÒ Mñëîâå w ðàáîòàåò òàê:c 1 w 0) = if ε ∈ L(M) then M1 (q1 w 0) else loop.M(qc âèäíî, ÷òîÈç îïèñàíèÿ ÌÒ Mc íà ëþáîì âõîäíîì ñëîâå wI åñëè code(M) ∈ K , òî ÌÒ Mc = L(M1 ) ;ðàáîòàåò êàê ÌÒ M1 ; â ýòîì ñëó÷àå L(M)I åñëè code(M) ∈/ K , òî íà ëþáîì âõîäíîì ñëîâå wc çàöèêëèâàåòñÿ; ïîýòîìó L(M)c = L(M0 ) .âû÷èñëåíèåÌÒ MÒÅÎÐÅÌÀ ÐÀÉÑÀÏîêàæåì, ÷òî ÿçûê K (ïðîáëåìà îñòàíîâà ÌÒ íà ïóñòîé ëåíòå)m-ñâîäèì ê ÿçûêó Prop .×òîáû ïðîâåðèòü âêëþ÷åíèå code(M) ∈ K äëÿ ïðîèçâîëüíîéc , êîòîðàÿ íà âñÿêîì âõîäíîìÌÒ M òðàíñëèðóåì åå â ÌÒ Mñëîâå w ðàáîòàåò òàê:c 1 w 0) = if ε ∈ L(M) then M1 (q1 w 0) else loop.M(qc âèäíî, ÷òîÈç îïèñàíèÿ ÌÒ Mc íà ëþáîì âõîäíîì ñëîâå wI åñëè code(M) ∈ K , òî ÌÒ Mc = L(M1 ) ;ðàáîòàåò êàê ÌÒ M1 ; â ýòîì ñëó÷àå L(M)I åñëè code(M) ∈/ K , òî íà ëþáîì âõîäíîì ñëîâå wc çàöèêëèâàåòñÿ; ïîýòîìó L(M)c = L(M0 ) .âû÷èñëåíèåÌÒ MÏîñêîëüêó ñâîéñòâî ÌÒ Prop ñåìàíòè÷åñêîå ècode(M0 ) ∈/ Prop , code(M1 ) ∈ Prop , ïðèõîäèì ê âûâîäóc ∈ Propcode(M) ∈ K ⇔ code(M)QED .ÒÅÎÐÅÌÀ ÐÀÉÑÀÈç òåîðåìû Ðàéñà ñëåäóåò, ÷òî ÂÑÅ çàäà÷èàíàëèçà ïîâåäåíèÿ êîìïüþòåðíûõ ïðîãðàìì,âêëþ÷àÿïðîâåðêó çàâåðøàåìîñòè (îòñóòñòâèÿçàöèêëèâàíèÿ);ïðîâåðêó êîððåêòíîñòè ðåçóëüòàòà;îïòèìèçàöèþ;ïðîâåðêó îòñòóòñòâèÿ óòå÷êè ïàìÿòè;ïðîâåðêó îòñóòñòâèÿ íåäåêëàðèðóåìûõâîçìîæíîñòåé;è ìíîãèå-ìíîãèå-ìíîãèå äðóãèå,àëãîðèòìè÷åñêè íåðàçðåøèìû .IIIIIÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÅñòü î÷åíü âàæíûé àñïåêò, î êîòîðîì ÷àñòî çàáûâàþò ïðè èçó÷åíèè àëãîðèòìè÷åñêè íåðàçðåøèìûõñâîéñòâ ïîâåäåíèÿ ÌÒ êîäèðîâàíèè ÌÒ.Ðàññìîòðåííîåíàìèêîäèðîâàíèå code(M) ïðîñòîåè ðàçóìíîå, íî íå åäèíñòâåííî âîçìîæíîå.ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÅñòü î÷åíü âàæíûé àñïåêò, î êîòîðîì ÷àñòî çàáûâàþò ïðè èçó÷åíèè àëãîðèòìè÷åñêè íåðàçðåøèìûõñâîéñòâ ïîâåäåíèÿ ÌÒ êîäèðîâàíèè ÌÒ.Ðàññìîòðåííîåíàìèêîäèðîâàíèå code(M) ïðîñòîåè ðàçóìíîå, íî íå åäèíñòâåííî âîçìîæíîå.Ìîæíî âçÿòü äðóãîå êîäèðîâàíèå code 0 , êîòîðîåîïèñûâåò êàæäóþ ÌÒ M ñëîâîì code(M)δ , ãäåδ = 1 åñëè ÌÒ M îñòàíàâëèâàåòñÿ íà ïóñòîéëåíòå; â ïðîòèâíîì ñëó÷àå δ = 0 .Òîãäà íåòðèâèàëüíîå ñåìàíòè÷åñêîå ñâîéñòâîK 0 = {code 0 (M) : ε ∈ L(M)} , î÷åâèäíî,ðåêóðñèâíî! Âîïðåêè òåîðåìå Ðàéñà!!! Ïî÷åìó?ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà íå äëÿ âñÿêîãîêîäèðîâàíèÿ ÌÒ.ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà íå äëÿ âñÿêîãîêîäèðîâàíèÿ ÌÒ.Êîäèðîâàíèå ìàøèí Òüþðèíãà enc íàçûâàåòñÿâû÷èñëèìûì , åñëè äëÿ ýòîãî êîäèðîâàíèÿìîæíî ïîñòðîèòü óíèâåðñàëüíóþ ìàøèíóÒüþðèíãà Uenc :w ∈ L(M) ⇔ w #enc(M) ∈ L(Uenc ) ;IÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà íå äëÿ âñÿêîãîêîäèðîâàíèÿ ÌÒ.Êîäèðîâàíèå ìàøèí Òüþðèíãà enc íàçûâàåòñÿâû÷èñëèìûì , åñëè äëÿ ýòîãî êîäèðîâàíèÿìîæíî ïîñòðîèòü óíèâåðñàëüíóþ ìàøèíóÒüþðèíãà Uenc :w ∈ L(M) ⇔ w #enc(M) ∈ L(Uenc ) ;ãëàâíûì , åñëè äëÿ ëþáîãî âû÷èñëèìîãîêîäèðîâàíèÿ enc 0 ñóùåñòâóåò òàêàÿ òîòàëüíàÿÒ-âû÷èñëèìàÿ ôóíêöèÿ ψ : Σ∗ → Σ∗ , ÷òî äëÿëþáîé ÌÒ Mw ∈ L(M) ⇔ w #ψ(enc 0 (M)) ∈ L(Uenc ) ;IIÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒî æå ñàìîå â òåðìèíàõ ïðîñòîãîïðîãðàììèðîâàíèÿ.êîäèðîâàíèå ÌÒ ýòî ñèñòåìàïðîãðàììèðîâàíèÿ;IÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒî æå ñàìîå â òåðìèíàõ ïðîñòîãîïðîãðàììèðîâàíèÿ.êîäèðîâàíèå ÌÒ ýòî ñèñòåìàïðîãðàììèðîâàíèÿ;âû÷èñëèìîå êîäèðîâàíèå ýòî ñèñòåìàïðîãðàììèðîâàíèÿ, äëÿ êîòîðîé ìîæíîïîñòðîèòü àïïàðàòíûé èíòåðïðåòàòîð(àðèôìåòèêî-ëîãè÷åñêîå óñòðîéñòâî,ïðîöåññîð);IIÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÒî æå ñàìîå â òåðìèíàõ ïðîñòîãîïðîãðàììèðîâàíèÿ.êîäèðîâàíèå ÌÒ ýòî ñèñòåìàïðîãðàììèðîâàíèÿ;âû÷èñëèìîå êîäèðîâàíèå ýòî ñèñòåìàïðîãðàììèðîâàíèÿ, äëÿ êîòîðîé ìîæíîïîñòðîèòü àïïàðàòíûé èíòåðïðåòàòîð(àðèôìåòèêî-ëîãè÷åñêîå óñòðîéñòâî,ïðîöåññîð);ãëàâíîå êîäèðîâàíèå ýòî ñèñòåìàïðîãðàììèðîâàíèÿ, â êîòîðóþ ìîæíîòðàíñëèðîâàòü ëþáóþ äðóãóþ ñèñòåìóïðîãðàììèðîâàíèÿ, èìåþùóþ èíòåðïðåòàòîð.IIIÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà òîëüêî äëÿãëàâíûõ âû÷èñëèìûõ êîäèðîâàíèé ÌÒ.ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà òîëüêî äëÿãëàâíûõ âû÷èñëèìûõ êîäèðîâàíèé ÌÒ.Íàïðèìåð, êîäèðîâàíèå code(M) ÿâëÿåòñÿâû÷èñëèìûì è ãëàâíûì.À êîäèðîâàíèå code 0(M) = code(M)δ ÿâëÿåòñÿâû÷èñëèìûì, íî íåãëàâíûì.ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÎêàçûâàåòñÿ, òåîðåìå Ðàéñà âåðíà òîëüêî äëÿãëàâíûõ âû÷èñëèìûõ êîäèðîâàíèé ÌÒ.Íàïðèìåð, êîäèðîâàíèå code(M) ÿâëÿåòñÿâû÷èñëèìûì è ãëàâíûì.À êîäèðîâàíèå code 0(M) = code(M)δ ÿâëÿåòñÿâû÷èñëèìûì, íî íåãëàâíûì.Âñå ¾åñòåñòâåííûå ñèñòåìû¿ ïðîãðàììèðîâàíèÿñîîòâåòñòâóþò ãëàâíûì âû÷èñëèìûìêîäèðîâàíèÿì.ÊÎÄÈÐÎÂÀÍÈß ÌÀØÈÍ ÒÜÞÐÈÍÃÀÃäå â äîêàçàòåëüñòâåòåîðåìû Ðàéñà íåÿâíî èñïîëüçóåòñÿ òîîáñòîÿòåëüñòâî, ÷òî code(M) ÿâëÿåòñÿ ãëàâíûìâû÷èñëèìûì êîäèðîâàíèå ÌÒ?Çàäà÷à 5.2.

Äîêàæèòå, ÷òî êîäèðîâàíèåcode 0 (M) = code(M)δ ÿâëÿåòñÿ âû÷èñëèìûì, íîíåãëàâíûì?Çàäà÷à 5.1. [Òðóäíàÿ]ÊÎÍÅÖ ËÅÊÖÈÈ 5.

Характеристики

Список файлов лекций