5. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем (1162496)
Текст из файла
Ìîäåëè âû÷èñëåíèéÂ.À. Çàõàðîâ, Ð.È. Ïîäëîâ÷åíêîËåêöèÿ 5.1. Óíèâåðñàëüíûå ìàøèíû Òüþðèíãà2. Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâà3. Ñâîäèìîñòü àëãîðèòìè÷åñêèõ ïðîáëåì4. Òåîðåìà Ðàéñà5. Êîäèðîâàíèÿ ÌÒÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàê áûëî ïîêàçàíî íà ïðåäûäóùåé ëåêöèè, îäíèÌÒ (íàïðèìåð, 1-ëåíòî÷íûå ÌÒ) ìîãóò ìîäåëèðîâàòü ðàáîòó äðóãèõ ÌÒ (íàïðèìåð, n-ëåíòî÷íûõ).Íî 80 ëåò íàçàä Ê.
Ãåäåëü, À. Òüþðèíã, Ý. Ïîñò,Ñ. Êëèíè, À. ×åð÷ îáíàðóæèëè, ÷òî íåêîòîðûåìîäåëè âû÷èñëåíèé (âêëþ÷àÿ ìàøèíû Òüþðèíãà)îáëàäàþò óäèâèòåëüíîé ñïîñîáíîñòüþ:ìîæíî èìåòü âñåãî ëèøü îäíó ïðîãðàììó,êîòîðàÿ ïîçâîëÿåò ìîäåëèðîâàòü ðàáîòóâñåõ ïðîãðàìì âû÷èñëèòåëüíîé ìîäåëè.ÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàê áûëî ïîêàçàíî íà ïðåäûäóùåé ëåêöèè, îäíèÌÒ (íàïðèìåð, 1-ëåíòî÷íûå ÌÒ) ìîãóò ìîäåëèðîâàòü ðàáîòó äðóãèõ ÌÒ (íàïðèìåð, n-ëåíòî÷íûõ).Íî 80 ëåò íàçàä Ê. Ãåäåëü, À. Òüþðèíã, Ý. Ïîñò,Ñ.
Êëèíè, À. ×åð÷ îáíàðóæèëè, ÷òî íåêîòîðûåìîäåëè âû÷èñëåíèé (âêëþ÷àÿ ìàøèíû Òüþðèíãà)îáëàäàþò óäèâèòåëüíîé ñïîñîáíîñòüþ:ìîæíî èìåòü âñåãî ëèøü îäíó ïðîãðàììó,êîòîðàÿ ïîçâîëÿåò ìîäåëèðîâàòü ðàáîòóâñåõ ïðîãðàìì âû÷èñëèòåëüíîé ìîäåëè.Òàêèåïðîãðàììûíàçûâàþòñÿ óíèâåðñàëüíûìè .ÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàæäàÿ ÌÒ M = (Σ, Γ, Q, q1, q0, q−1, T ) ïîëíîñòüþ îïðåäåëÿåòñÿ îòíîøåíèåì ïåðåõîäà T è òðîéêîé îñîáî âûäåëåííûõñîñòîÿíèé q1, q0, q−1 . Îòíîøåíèå ïåðåõîäîâ ìîæíî ïðåäñòàâèòüêîíå÷íûì ñïèñêîì êîìàíä âèäà K = (q0, a : b, q00, D) .Íàèìåíîâàíèÿ âñåõ ñîñòîÿíèé ÌÒ M , à òàêæå ñèìâîëûñìåùåíèå ñ÷èòûâàþùåé ãîëîâêè ÌÒ L, R ìîæíî çàêîäèðîâàòü(íàïðèìåð, èñïîëüçóÿ áëî÷íîå êîäèðîâàíèå) ñëîâàìè âàëôàâèòå ÌÒ Σ .ÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÊàæäàÿ ÌÒ M = (Σ, Γ, Q, q1, q0, q−1, T ) ïîëíîñòüþ îïðåäåëÿåòñÿ îòíîøåíèåì ïåðåõîäà T è òðîéêîé îñîáî âûäåëåííûõñîñòîÿíèé q1, q0, q−1 .
Îòíîøåíèå ïåðåõîäîâ ìîæíî ïðåäñòàâèòüêîíå÷íûì ñïèñêîì êîìàíä âèäà K = (q0, a : b, q00, D) .Íàèìåíîâàíèÿ âñåõ ñîñòîÿíèé ÌÒ M , à òàêæå ñèìâîëûñìåùåíèå ñ÷èòûâàþùåé ãîëîâêè ÌÒ L, R ìîæíî çàêîäèðîâàòü(íàïðèìåð, èñïîëüçóÿ áëî÷íîå êîäèðîâàíèå) ñëîâàìè âàëôàâèòå ÌÒ Σ .Òîãäà îïèñàíèåì êàæäîé êîìàíäû K = (q0, a : b, q00, D) áóäåòñëîâîcode(K ) = code(q 0 ) a b code(q 00 )code(D),à îïèñàíèåì ÌÒ M ñëîâîcode(M) = code(K1 )code(K2 ) . . . code(KN )code(q1 )code(q0 )code(q−1 ).ÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÓíèâåðñàëüíîé ìàøèíîé Òüþðèíãà (ÓÌÒ)íàçûâàåòñÿ ÌÒ U , îáëàäàþùàÿ ñëåäóþùèìñâîéñòâîì:äëÿ ëþáîé ÌÒ M è äëÿ ëþáîãî ñëîâà w ÓÌÒ U ,èìåÿ íà âõîäíîé ëåíòå íà÷àëüíóþ êîíôèãóðàöèþq1 code(M)#w , ïðîâîäèò âû÷èñëåíèå, êîòîðîåÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÓíèâåðñàëüíîé ìàøèíîé Òüþðèíãà (ÓÌÒ)íàçûâàåòñÿ ÌÒ U , îáëàäàþùàÿ ñëåäóþùèìñâîéñòâîì:äëÿ ëþáîé ÌÒ M è äëÿ ëþáîãî ñëîâà w ÓÌÒ U ,èìåÿ íà âõîäíîé ëåíòå íà÷àëüíóþ êîíôèãóðàöèþq1 code(M)#w , ïðîâîäèò âû÷èñëåíèå, êîòîðîåçàâåðøàåòñÿ â äîïóñêàþùåì ñîñòîÿíèè òîãäà èòîëüêî òîãäà, êîãäà ÌÒ M äîïóñêàåò ñëîâî w ;IÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÓíèâåðñàëüíîé ìàøèíîé Òüþðèíãà (ÓÌÒ)íàçûâàåòñÿ ÌÒ U , îáëàäàþùàÿ ñëåäóþùèìñâîéñòâîì:äëÿ ëþáîé ÌÒ M è äëÿ ëþáîãî ñëîâà w ÓÌÒ U ,èìåÿ íà âõîäíîé ëåíòå íà÷àëüíóþ êîíôèãóðàöèþq1 code(M)#w , ïðîâîäèò âû÷èñëåíèå, êîòîðîåçàâåðøàåòñÿ â äîïóñêàþùåì ñîñòîÿíèè òîãäà èòîëüêî òîãäà, êîãäà ÌÒ M äîïóñêàåò ñëîâî w ;çàâåðøàåòñÿ â îòâåðãàþùåì ñîñòîÿíèè òîãäà èòîëüêî òîãäà, êîãäà ÌÒ M îòâåðãàåò ñëîâî w .IIÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÒåîðåìà 5.1.ñóùåñòâóþò.Óíèâåðñàëüíûå ìàøèíû ÒüþðèíãàÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÒåîðåìà 5.1.ñóùåñòâóþò.Óíèâåðñàëüíûå ìàøèíû ÒüþðèíãàÐàññìîòðèì 4-ëåíòî÷íóþ ÌÒU , êîòîðàÿ ðàáîòàåò ïî ñëåäóþùåìó ñöåíàðèþ.Äîêàçàòåëüñòâî.code(M)#w⇑q1Ïîëó÷èâ íà âõîäíîé ëåíòå íà÷àëüíóþ êîíôèãóðàöèþq1 code(M)#w ,code(M)#w#w⇑qb1code(q1 )code(M)Ïîëó÷èâ íà âõîäíîé ëåíòå íà÷àëüíóþ êîíôèãóðàöèþq1 code(M)#w ,ÌÒ U , ïåðåïèñûâåò äàííûå íà ðàáî÷èåëåíòû è äàëåå ïîâòîðÿåò îäíè è òå æå äåéñòâèÿ:code(M)#w# aw 0⇑qb1code(q1 )code(M)Èñïîëüçóÿ ðàçäåëèòåëü # êàê ìàðêåð îáîçðåâàåìîéÿ÷åéêè, çàïîìèíàåò áóêâó ñïðàâà îò ìàðêåðà,code(M)#w#aw 0code(q1 )· · · code(q1 )a b code(q2 )code(R) · · ·⇑qb2Èñïîëüçóÿ ýòó áóêâó è çàïèñü êîäà ñîñòîÿíèÿ code(q1) ,íàõîäèò êîä ñîîòâåòñòâóþùåé êîìàíäû,code(M)#wb#w 0⇑qb1code(q2 )code(M)è ìîäåëèðóåò ýôôåêò ïðèìåíåíèÿ ýòîé êîìàíäû.ÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÅñëè î÷åðåäíîå ñëîâî code(q) íà âòîðîé ðàáî÷åéëåíòå îêàçûâàåòñÿ êîäîìäîïóñêàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â äîïóñêþùåå ñîñòîÿíèå;îòâåðãàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â îòâåðãàþùåå ñîñòîÿíèå.QEDIIÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÅñëè î÷åðåäíîå ñëîâî code(q) íà âòîðîé ðàáî÷åéëåíòå îêàçûâàåòñÿ êîäîìäîïóñêàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â äîïóñêþùåå ñîñòîÿíèå;îòâåðãàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â îòâåðãàþùåå ñîñòîÿíèå.QEDÀ êàêîãî ðàçìåðà ìîãóò ÓÌÒ?IIÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÅñëè î÷åðåäíîå ñëîâî code(q) íà âòîðîé ðàáî÷åéëåíòå îêàçûâàåòñÿ êîäîìäîïóñêàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â äîïóñêþùåå ñîñòîÿíèå;îòâåðãàþùåãî ñîñòîÿíèÿ ÌÒ M , òî ÌÒ Uòàêæå ïåðåõîäèò â îòâåðãàþùåå ñîñòîÿíèå.QEDÀ êàêîãî ðàçìåðà ìîãóò ÓÌÒ?Þ.Â.
Ðîãîæèíó óäàëîñü ïîñòðîèòü ÓÌÒ ñ 22êîìàíäàìè [ðåêîðä!]IIÓÍÈÂÅÐÑÀËÜÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀÂíà÷àëå î ïðàêòè÷åñêîé ïîëüçå ÓÌÒ.ÓÌÒ ìàòåìàòè÷åñêàÿ ìîäåëü óíèâåðñàëüíîãîïðîãðàììèðóåìîãî âû÷èñëèòåëüíîãî óñòðîéñòâà.Ýòó ìîäåëü èñïîëüçîâàëè Òîì Ôëàóåðñ, ÌàêñÍüþìàí è èõ êîëëåãè ïðè ðàçðàáîòêå ïåðâîãîïðîãðàììèðóåìîãî êîìïüþòåðà Colossus , ÷òîáûïðîâåñòè óñïåøíûé êðèïòîàíàëèç ãåðìàíñêîéñèñòåìû øèôðîâàíèÿ Lorenz.Ýòó ìîäåëü èñïîëüçîâàë Äæîí ôîí Íåéìàí ïðèðàçðàáîòêå êîíöåïöèè óñòðîéñòâà óíèâåðñàëüíîãîêîìïüþòåðà.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÎáñóäèì òåîðåòè÷åñêîå çíà÷åíèå ÓÌÒ.Ïîêàæåì, êàê èäåè, ëåæàùèå â îñíîâå ÓÌÒìîæíî èñïîëüçîâàòü äëÿ ïîñòðîåíèÿ ïðèìåðàíåðåêóðñèâíîãî ÿçûêà.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÎáñóäèì òåîðåòè÷åñêîå çíà÷åíèå ÓÌÒ.Ïîêàæåì, êàê èäåè, ëåæàùèå â îñíîâå ÓÌÒìîæíî èñïîëüçîâàòü äëÿ ïîñòðîåíèÿ ïðèìåðàíåðåêóðñèâíîãî ÿçûêà.Íàçîâåì ÌÒ M ñàìîïðèìåíèìîé , åñëècode(M) ∈ L(M) .ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÎáñóäèì òåîðåòè÷åñêîå çíà÷åíèå ÓÌÒ.Ïîêàæåì, êàê èäåè, ëåæàùèå â îñíîâå ÓÌÒìîæíî èñïîëüçîâàòü äëÿ ïîñòðîåíèÿ ïðèìåðàíåðåêóðñèâíîãî ÿçûêà.Íàçîâåì ÌÒ M ñàìîïðèìåíèìîé , åñëècode(M) ∈ L(M) .Òåîðåìà 5.2.
ßçûêS = {code(M) : code(M) ∈ L(M)}ðåêóðñèâíî ïåðå÷èñëèì, íî íåðåêóðñèâåí.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.ÿçûêà S î÷åâèäíà.Ðåêóðñèâíàÿ ïåðå÷èñëèìîñòüÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàçàòåëüñòâî.Ðåêóðñèâíàÿ ïåðå÷èñëèìîñòüÿçûêà S î÷åâèäíà.Ïðåäïîëîæèì, ÷òî ÿçûê S ðåêóðñèâåí. Òîãäà åñòüòîòàëüíàÿ ÌÒ MS , ðàñïîçíàþùàÿ S .Ìîäèôèöèðóåì ÌÒ MS : ïîìåíÿåì ðîëÿìèäîïóñêþùåå ñîñòîÿíèå q0 (òåïåðü îíî áóäåòîòâåðãàþùèì) è îòâåðãàþùåå ñîñòîÿíèå q−1(òåïåðü îíî áóäåò äîïóñêàþùèì).Îáðàçîâàâøóþñÿ â ðåçóëüòàòå ýòîé çàìåíû ÌÒíàçîâåì MS ; îíà òàêæå ÿâëÿåòñÿ òîòàëüíîé.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ òåïåðü çàäàäèìñÿ âîïðîñîì: ïðèíàäëåæèò ëèñëîâî code(MS ) ÿçûêó S ?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ òåïåðü çàäàäèìñÿ âîïðîñîì: ïðèíàäëåæèò ëèñëîâî code(MS ) ÿçûêó S ?Åñëè code(MS ) ∈ S , òî ïî îïðåäåëåíèþ ÿçûêà Sâåðíî code(MS ) ∈ L(MS ).ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ òåïåðü çàäàäèìñÿ âîïðîñîì: ïðèíàäëåæèò ëèñëîâî code(MS ) ÿçûêó S ?Åñëè code(MS ) ∈ S , òî ïî îïðåäåëåíèþ ÿçûêà Sâåðíî code(MS ) ∈ L(MS ).Íî ÌÒ MS äîïóñêàåò òå ñëîâà, êîòîðûå îòâåðãàþòñÿ ÌÒ MS .
Çíà÷èò, code(MS ) ∈/ L(MS ) .ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ òåïåðü çàäàäèìñÿ âîïðîñîì: ïðèíàäëåæèò ëèñëîâî code(MS ) ÿçûêó S ?Åñëè code(MS ) ∈ S , òî ïî îïðåäåëåíèþ ÿçûêà Sâåðíî code(MS ) ∈ L(MS ).Íî ÌÒ MS äîïóñêàåò òå ñëîâà, êîòîðûå îòâåðãàþòñÿ ÌÒ MS . Çíà÷èò, code(MS ) ∈/ L(MS ) .Íî ïî îïðåäåëåíèþ ÌÒ MS âåðíî S = L(MS ) .Îòñþäà ñëåäóåò, ÷òî code(MS ) ∈/ S .Ïîëó÷èëè ïðîòèâîðå÷èå:code(MS ) ∈ S ⇒ code(MS ) ∈/S !ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ ÷òî áóäåò, åñëè ïðåäïîëîæèòü, ÷òîcode(MS ) ∈/ S?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ ÷òî áóäåò, åñëè ïðåäïîëîæèòü, ÷òîcode(MS ) ∈/ S?Òîãäà ïî îïðåäåëåíèþ ÿçûêà S âåðíîcode(MS ) ∈/ L(MS ).ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ ÷òî áóäåò, åñëè ïðåäïîëîæèòü, ÷òîcode(MS ) ∈/ S?Òîãäà ïî îïðåäåëåíèþ ÿçûêà S âåðíîcode(MS ) ∈/ L(MS ).Íî ÌÒ MS îòâåðãàåò òå ñëîâà, êîòîðûå äîïóñêàþòñÿ ÌÒ MS .
Çíà÷èò, code(MS ) ∈ L(MS ) .ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ ÷òî áóäåò, åñëè ïðåäïîëîæèòü, ÷òîcode(MS ) ∈/ S?Òîãäà ïî îïðåäåëåíèþ ÿçûêà S âåðíîcode(MS ) ∈/ L(MS ).Íî ÌÒ MS îòâåðãàåò òå ñëîâà, êîòîðûå äîïóñêàþòñÿ ÌÒ MS . Çíà÷èò, code(MS ) ∈ L(MS ) .Íî ïî îïðåäåëåíèþ ÌÒ MS âåðíî S = L(MS ) .Îòñþäà ñëåäóåò, ÷òî code(MS ) ∈ S .È ñíîâà ïðîòèâîðå÷èå:code(MS ) ∈/ S ⇒ code(MS ) ∈ S !ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÈòàê, îáå âîçìîæíîñòè code(MS ) ∈ S ècode(MS ) ∈/ S îêàçûâàþòñÿ íåñîñòîÿòåëüíûìè.×òî ýòî îçíà÷àåò?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÈòàê, îáå âîçìîæíîñòè code(MS ) ∈ S ècode(MS ) ∈/ S îêàçûâàþòñÿ íåñîñòîÿòåëüíûìè.×òî ýòî îçíà÷àåò?Ýòî îçíà÷àåò, ÷òî òàêîé ÌÒçíà÷èò, è ÌÒìîæåò!MS )MS(àñóùåñòâîâàòü íåÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÈòàê, îáå âîçìîæíîñòè code(MS ) ∈ S ècode(MS ) ∈/ S îêàçûâàþòñÿ íåñîñòîÿòåëüíûìè.×òî ýòî îçíà÷àåò?Ýòî îçíà÷àåò, ÷òî òàêîé ÌÒçíà÷èò, è ÌÒìîæåò!MS )MS(àñóùåñòâîâàòü íåÍî âîçìîæíîñòüþ ñâîåãî ñóùåñòâîâàíèÿ ÌÒ MSîáÿçàíà ïðåäïîëîæåíèþ î ðåêóðñèâíîñòè ÿçûêà S.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÈòàê, îáå âîçìîæíîñòè code(MS ) ∈ S ècode(MS ) ∈/ S îêàçûâàþòñÿ íåñîñòîÿòåëüíûìè.×òî ýòî îçíà÷àåò?Ýòî îçíà÷àåò, ÷òî òàêîé ÌÒçíà÷èò, è ÌÒMS )MS(àñóùåñòâîâàòü íåìîæåò!Íî âîçìîæíîñòüþ ñâîåãî ñóùåñòâîâàíèÿ ÌÒ MSîáÿçàíà ïðåäïîëîæåíèþ î ðåêóðñèâíîñòè ÿçûêà S.Çíà÷èò, ÿçûêSíåðåêóðñèâåí!QEDÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀßçûê S ñîîòâåòñòâóåò ìàññîâîé àëãîðèòìè÷åñêîéïðîáëåìå: ïî îïèñàíèþ ÌÒ âûÿñíèòü, ÿâëÿåòñÿëè ýòà ÌÒ ñàìîïðèìåíèìîé.Ðåêóðñèâíàÿ ïåðå÷èñëèìîñòü ÿçûêà S îçíà÷àåò,÷òî åñòü àëãîðèòì, ïðîâåðÿþùèé ïðàâèëüíîñòüðåøåíèÿ çàäà÷è î ñàìîïðèìåíèìîñòè ÌÒ.Íåðåêóðñèâíîñòü ÿçûêà S îçíà÷àåò, ÷òî ñàìîãîàëãîðèòìà ðåøåíèÿ ïðîáëåìû ñàìîïðèìåíèìîñòèÌÒ íå ñóùåñòâóåò.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀßçûê S ñîîòâåòñòâóåò ìàññîâîé àëãîðèòìè÷åñêîéïðîáëåìå: ïî îïèñàíèþ ÌÒ âûÿñíèòü, ÿâëÿåòñÿëè ýòà ÌÒ ñàìîïðèìåíèìîé.Ðåêóðñèâíàÿ ïåðå÷èñëèìîñòü ÿçûêà S îçíà÷àåò,÷òî åñòü àëãîðèòì, ïðîâåðÿþùèé ïðàâèëüíîñòüðåøåíèÿ çàäà÷è î ñàìîïðèìåíèìîñòè ÌÒ.Íåðåêóðñèâíîñòü ÿçûêà S îçíà÷àåò, ÷òî ñàìîãîàëãîðèòìà ðåøåíèÿ ïðîáëåìû ñàìîïðèìåíèìîñòèÌÒ íå ñóùåñòâóåò.Ïðîáëåìà ñàìîïðèìåíèìîñòè ÌÒ ýòî ïðèìåðçàäà÷è, ïîêàçûâàþùåé, ÷òî õîðîøèé ýêçàìåíàòîðìîæåò áûòü ïëîõèì ñòóäåíòîì!ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ êàêîé ìàòåìàòè÷åñêèé ïàðàäîêñ íàïîìèíàåòïðîáëåìà ñàìîïðèìåíèìîñòè ÌÒ?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ êàêîé ìàòåìàòè÷åñêèé ïàðàäîêñ íàïîìèíàåòïðîáëåìà ñàìîïðèìåíèìîñòè ÌÒ?Ïàðàäîêñ Ðàññåëà (çàäà÷ó î ïàðèêìàõåðå): åñòü ëèòàêîé ãîðîä, â êîòîðîì ïàðèêìàõåð áðååò âñåõ òåõæèòåëåé ãîðîäà, êîòîðûå íå áðåþòñÿ ñàìè?Ýòîò ïàðàäîêñ èìååò äåëî ñ òåì æå ñàìûìïðîòèâîðå÷èåì, êîòîðîå âîçíèêàåò ïðè ðåøåíèèïðîáëåìû ñàìîïðèìåíèìîñòè ÌÒ: à êòî áðååòñàìîãî ïàðèêìàõåðà?Ìû óâèäèì, ÷òî ïàðàäîêñ Ðàññåëà èìååò äàëåêîèäóùèå ïîñëåäñòâèÿ äëÿ ïðîãðàììèðîâàíèÿ.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ åñòü ëè òàêèå ïðîáëåìû, êîòîðûå íå òîëüêî íåèìåþò àëãîðèòìà ðåøåíèÿ, íî äàæå íå èìåþòàëãîðèòìà ïðîâåðêè ïðàâèëüíîñòè ðåøåíèé?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ åñòü ëè òàêèå ïðîáëåìû, êîòîðûå íå òîëüêî íåèìåþò àëãîðèòìà ðåøåíèÿ, íî äàæå íå èìåþòàëãîðèòìà ïðîâåðêè ïðàâèëüíîñòè ðåøåíèé?Ýòî ïðîáëåìà ÍÅñàìîïðèìåíèìîñòè ÌÒ :âûÿñíèòü, âåðíî ëè,÷òî çàäàííàÿ ÌÒ íå äîïóñêàåòñâîé ñîáñòâåííûé êîä.Ïî÷åìó îíà íå ÿâëÿåòñÿ ïîëóðàçðåøèìîé?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÀ åñòü ëè òàêèå ïðîáëåìû, êîòîðûå íå òîëüêî íåèìåþò àëãîðèòìà ðåøåíèÿ, íî äàæå íå èìåþòàëãîðèòìà ïðîâåðêè ïðàâèëüíîñòè ðåøåíèé?Ýòî ïðîáëåìà ÍÅñàìîïðèìåíèìîñòè ÌÒ :âûÿñíèòü, âåðíî ëè,÷òî çàäàííàÿ ÌÒ íå äîïóñêàåòñâîé ñîáñòâåííûé êîä.Ïî÷åìó îíà íå ÿâëÿåòñÿ ïîëóðàçðåøèìîé?Ïîòîìó ÷òî ïîëóðàçðåøèìîñòü îáåèõ ïðîáëåì ñàìîïðèìåíèìîñòè è íåñàìîïðèìåíèìîñòè îçíà÷àëà áû, ÷òî îáå îíè ÿâëÿþòñÿ ðàçðåøèìûìè(ñì.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
