5. Универсальные машины Тьюринга. Неразрешимость проблемы останова для машин Тьюринга. Сводимость алгоритмических проблем (1162496), страница 2
Текст из файла (страница 2)
Òåîðåìó 4.4).ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÏðîáëåìà ñàìîïðèìåíèìîñòè êàæåòñÿ âåñüìàèñêóñòâåííîé: íó êîìó ïðèäåò â ãîëîâó ïîäàâàòüíà âõîä ïðîãðàììû åå æå ñîáñòâåííûé êîä?ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÏðîáëåìà ñàìîïðèìåíèìîñòè êàæåòñÿ âåñüìàèñêóñòâåííîé: íó êîìó ïðèäåò â ãîëîâó ïîäàâàòüíà âõîä ïðîãðàììû åå æå ñîáñòâåííûé êîä?1) Ýòî íå ñîâñåì òàê: íàïðèìåð, íà âõîäêîìïèëÿòîðà ìîæíî (è âïîëíå ðàçóìíî) ïîäàâàòüñàìó æå ïðîãðàììó êîìïèëÿöèè.ÏÐÎÁËÅÌÀ ÑÀÌÎÏÐÈÌÅÍÈÌÎÑÒÈÌÀØÈÍ ÒÜÞÐÈÍÃÀÏðîáëåìà ñàìîïðèìåíèìîñòè êàæåòñÿ âåñüìàèñêóñòâåííîé: íó êîìó ïðèäåò â ãîëîâó ïîäàâàòüíà âõîä ïðîãðàììû åå æå ñîáñòâåííûé êîä?1) Ýòî íå ñîâñåì òàê: íàïðèìåð, íà âõîäêîìïèëÿòîðà ìîæíî (è âïîëíå ðàçóìíî) ïîäàâàòüñàìó æå ïðîãðàììó êîìïèëÿöèè.2) Åñòü î÷åíü ìíîãî ¾åñòåñòâåííûõ¿ çàäà÷ïðîãðàììèðîâàíèÿ, äëÿ êîòîðûõ íåâîçìîæíîïîñòðîèòü àëãîðèòìîâ èõ ðåøåíèÿ. Ýòî ìîæíîäîêàçàòü îïèðàÿñü íà òîò ôàêò, ÷òî ïðîáëåìàñàìîïðèìåíèìîñòè ÌÒ íåðàçðåøèìà.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÁóäåì ãîâîðèòü, ÷òî ÌÒ M îñòàíàâëèâàåòñÿ íàïóñòîé ëåíòå , åñëè ε ∈ L(M) , ò.å.
âû÷èñëåíèåÌÒ M , íà÷èíàþùååñÿ êîíôèãóðàöèåé, â êîòîðîéíà ëåíòå çàïèñàíî ïóñòîå âõîäíîå ñëîâî,çàâåðøàåòñÿ ñïóñòÿ êîíå÷íî ÷èñëî òàêòîâ ðàáîòûâ äîïóñêàþùåì ñîñòîÿíèè.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÁóäåì ãîâîðèòü, ÷òî ÌÒ M îñòàíàâëèâàåòñÿ íàïóñòîé ëåíòå , åñëè ε ∈ L(M) , ò.å. âû÷èñëåíèåÌÒ M , íà÷èíàþùååñÿ êîíôèãóðàöèåé, â êîòîðîéíà ëåíòå çàïèñàíî ïóñòîå âõîäíîå ñëîâî,çàâåðøàåòñÿ ñïóñòÿ êîíå÷íî ÷èñëî òàêòîâ ðàáîòûâ äîïóñêàþùåì ñîñòîÿíèè.Ìîæíî ëè ïîñòðîèòü àëãîðèòì ïðîâåðêè ñâîéñòâàîñòàíîâà ÌÒ íà ïóñòîé ëåíòå?ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÁóäåì ãîâîðèòü, ÷òî ÌÒ M îñòàíàâëèâàåòñÿ íàïóñòîé ëåíòå , åñëè ε ∈ L(M) , ò.å.
âû÷èñëåíèåÌÒ M , íà÷èíàþùååñÿ êîíôèãóðàöèåé, â êîòîðîéíà ëåíòå çàïèñàíî ïóñòîå âõîäíîå ñëîâî,çàâåðøàåòñÿ ñïóñòÿ êîíå÷íî ÷èñëî òàêòîâ ðàáîòûâ äîïóñêàþùåì ñîñòîÿíèè.Ìîæíî ëè ïîñòðîèòü àëãîðèòì ïðîâåðêè ñâîéñòâàîñòàíîâà ÌÒ íà ïóñòîé ëåíòå?Òåîðåìà 5.3. ßçûê K = {code(M) : ε ∈ L(M)}íåðåêóðñèâåí.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀÏîêàæåì, ÷òî èçíåðàçðåøèìîñòè ïðîáëåìû ñàìîïðèìåíèìîñòèÌÒ ñëåäóåò íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâà.Äîêàçàòåëüñòâî ïðîâîäèòñÿ ¾îò ïðîòèâíîãî¿.Äîêàçàòåëüñòâî.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀÏîêàæåì, ÷òî èçíåðàçðåøèìîñòè ïðîáëåìû ñàìîïðèìåíèìîñòèÌÒ ñëåäóåò íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâà.Äîêàçàòåëüñòâî ïðîâîäèòñÿ ¾îò ïðîòèâíîãî¿.Äîïóñòèì, ÷òî ñóùåñòâóåò òàêàÿ òîòàëüíàÿ ÌÒMK , ÷òî K = L(MK ) .Ïîêàæåì, êàê èñïîëüçóÿ ÌÒ MK , ïîñòðîèòüòîòàëüíóþ ÌÒ MS , ðàñïîçíàþùóþ ÿçûê S , ò.å.ðåøàþùóþ ïðîáëåìó ñàìîïðèìåíèìîñòè ÌÒ.
Ò.ê.ýòà ïðîáëåìà íåðàçðåøèìà, òàêîå ïîñòðîåíèåîçíà÷àåò, ÷òî ÌÒ MK , ðåøàþùóþ ïðîáëåìóîñòàíîâà ïîñòðîèòü íåâîçìîæíî.Äîêàçàòåëüñòâî.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀ0000⇑000000000MÓñëîâèå îñòàíîâà ÌÒ: âû÷èñëåíèå M íà ïóñòîé ëåíòåçàâåðøàåòñÿ.0ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀ0000⇑0000000000MÓñëîâèå îñòàíîâà ÌÒ: âû÷èñëåíèå M íà ïóñòîé ëåíòåçàâåðøàåòñÿ.00code(M)⇑00MÓñëîâèå ñàìîïðèìåíèìîñòè ÌÒ: âû÷èñëåíèå M íà âõîäíîìñëîâå code(M) çàâåðøàåòñÿ.ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÏðåäïîëîæèì ó íàñ åñòü ÌÒ MK , ðåøàþùàÿ ïðîáëåìóîñòàíîâà íà ïóñòîé ëåíòå.00code(M)⇑MK00ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÏðåäïîëîæèì ó íàñ åñòü ÌÒ MK , ðåøàþùàÿ ïðîáëåìóîñòàíîâà íà ïóñòîé ëåíòå.00code(M)⇑: q0XXXMKXz q−100ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÏðåäïîëîæèì ó íàñ åñòü ÌÒ MK , ðåøàþùàÿ ïðîáëåìóîñòàíîâà íà ïóñòîé ëåíòå.00code(M)⇑: q000XXXMKXz q−1È êàê íàì ïîñòðîèòü ÌÒ MS , ðåøàþùóþ ïðîáëåìóñàìîïðèìåíèìîñòè?00code(M)⇑: q0XMSXXXz q−100ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀ00code(M)⇑00MKÇàìåòèì, ÷òî ìû íè÷åãî íå çíàåì îá óñòðîéñòâå ïðåäïîëàãàåìîé ÌÒ MK .
Ìû çíàåì òîëüêî åå ôóíêöèîíàëüíîñòü: îíàðåøàåò ïðîáëåìó îñòàíîâà íà ïóñòîé ëåíòå.Îíà ÿâëÿåòñÿ äëÿ íàñ ¾÷åðíûì ÿùèêîì¿: ìû ìîæåìèñïîëüçîâàòü åå ôóíêöèîíàëüíîñòü, íî íå ìîæåì âíîñèòüèçìåíåíèé â åå óñòðîéñòâî.Êàê æå íàì ïðàâèëüíî èñïîëüçîâàòü ÌÒ MK äëÿ ïðîâåðêèñàìîïðèìåíèìîñòè ÌÒ?ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÍàì íàäî ïåðåôîðìóëèðîâàòü âîïðîñ îñàìîïðèìåíèìîñòè çàäàííîé ÌÒ òàê, ÷òîáû íàíåãî ìîã îòâå÷àòü ¾÷åðíûé ÿùèê¿ MK ,óìåþùèé ðåøàòü ïðîáëåìó ïóñòîòû.Áîëåå êîíêðåòíî: íóæíî íàó÷èòüñÿ òðàíñëèðîâàòüïðîãðàììó çàäàííîé ÌÒ M â ïðîãðàììó äðóãîéc òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèåÌÒ Mc ∈ K.code(M) ∈ S ⇔ code(M)ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÍàì íàäî ïåðåôîðìóëèðîâàòü âîïðîñ îñàìîïðèìåíèìîñòè çàäàííîé ÌÒ òàê, ÷òîáû íàíåãî ìîã îòâå÷àòü ¾÷åðíûé ÿùèê¿ MK ,óìåþùèé ðåøàòü ïðîáëåìó ïóñòîòû.Áîëåå êîíêðåòíî: íóæíî íàó÷èòüñÿ òðàíñëèðîâàòüïðîãðàììó çàäàííîé ÌÒ M â ïðîãðàììó äðóãîéc òàê, ÷òîáû âûïîëíÿëîñü ñîîòíîøåíèåÌÒ Mc ∈ K.code(M) ∈ S ⇔ code(M)Åñëè òàêîé òðàíñëÿòîð T óäàñòñÿ ïîñòðîèòü, òîïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ T ; MK áóäåòðåøàòü ïðîáëåìó ñàìîïðèìåíèìîñòè ÌÒ!ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÄëÿ êàæäîé ÌÒ M îáîçíà÷èì çàïèñüþ WriteMÌÒ, êîòîðàÿ çàïèñûâàåò íà ïóñòîé ëåíòå êîäcode(M) ÌÒ M .Ïîêàæåì, ÷òî ïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ ÌÒWriteM ; M êàê ðàç è ÿâëÿåòñÿ æåëàåìûìc.ðåçóëüòàòîì òðàíñëÿöèè MÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÄëÿ êàæäîé ÌÒ M îáîçíà÷èì çàïèñüþ WriteMÌÒ, êîòîðàÿ çàïèñûâàåò íà ïóñòîé ëåíòå êîäcode(M) ÌÒ M .Ïîêàæåì, ÷òî ïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ ÌÒWriteM ; M êàê ðàç è ÿâëÿåòñÿ æåëàåìûìc.ðåçóëüòàòîì òðàíñëÿöèè MÄåéñòâèòåëüíî, ÌÒ WriteM; M âíà÷àëå çàïèøåòíà ïóñòîé âõîäíîé ëåíòå êîä code(M) , à ïîòîìïðèìåíèò ÌÒ M ê ýòîìó êîäó.Çíà÷èò, WriteM; M îñòàíîâèòñÿ íà ïóñòîéâõîäíîé ëåíòå òîãäà è òîëüêî òîãäà, êîãäà ÌÒ Mñàìîïðèìåíèìà!ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) .
Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) . Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) . Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abcÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) .
Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abccode(q1 0 : cq2 L)ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) . Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abccode(q1 0 : cq2 L)code(q2 0 : bq3 L)ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) .
Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abccode(q1 0 : cq2 L)code(q2 0 : bq3 L)code(q3 0 : bq4 L)ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) . Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abccode(q1 0:cq2 L)code(q2 0:bq3 L)code(q3 0:bq4 L)code(q4 0:bq5 R)ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÎñòàëîñü ïîñòðîèòü òðàíñëÿòîðT : code(M) → code(WriteM ) . Íî ýòî ñäåëàòüî÷åíü ïðîñòî!ÌÒ T ïðî÷èòûâàåò íà âõîäíîé ëåíòå ñëîâîcode(M) áóêâó çà áóêâîé è äëÿ êàæäîé ïðî÷èòàííîé áóêâû çàïèñûâàåò íà âûõîäíîé ëåíòå êîäòîé êîìàíäû, êîòîðàÿ ìîæåò çàïèñàòü ýòó áóêâó:T:abccode(q1 0:cq2 L)code(q2 0:bq3 L)code(q3 0:bq4 L)code(q4 0:bq5 R)à ïîòîì ê ýòîé ïîñëåäîâàòåëüíîñòè êîäîâ êîìàíääîáàâëÿåò êîä code(M) ÌÒ M .ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÂîò è âñå.
Åñëè ÌÒ T ; MK ïðèìåíèòü êâõîäíîìó ñëîâó code(M) , òî òðàíñëÿòîð Tçàïèøåò íà ðàáî÷åé ëåíòå êîä ÌÒ WriteM; M , èïîñëå ýòîãî ¾÷åðíûé ÿùèê¿ MK ïðîâåðèòñâîéñòâî îñòàíîâà äëÿ ÌÒ WriteM; M .ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀÂîò è âñå. Åñëè ÌÒ T ; MK ïðèìåíèòü êâõîäíîìó ñëîâó code(M) , òî òðàíñëÿòîð Tçàïèøåò íà ðàáî÷åé ëåíòå êîä ÌÒ WriteM; M , èïîñëå ýòîãî ¾÷åðíûé ÿùèê¿ MK ïðîâåðèòñâîéñòâî îñòàíîâà äëÿ ÌÒ WriteM; M .Ïîñêîëüêó ýòî ñâîéñòâî ðàâíîñèëüíî ñâîéñòâóñàìîïðèìåíèìîñòè ÌÒ M , â ðåçóëüòàòå ìûïîñòðîèëè òîòàëüíóþ ÌÒ, êîòîðàÿ ðåøàåòïðîáëåìó ñàìîïðèìåíèìîñòè, ÷òî ïðîòèâîðå÷èòÒåîðåìå 5.2.Çíà÷èò, òîòàëüíîé ÌÒ, ðàñïîçíàþùåé ÿçûê MKíå ñóùåñòâóåò.QEDÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀcode(M)⇑q1kT ; MKÂíà÷àëå ðàáîòàåò ÌÒ T , êîòîðàÿ ñîãëàñíîîïðåäåëåíèþ çàïèñûâàåò íà âõîäíîé ëåíòå ñëîâîcode(WriteM ; M) .ÏÐÎÁËÅÌÀ ÎÑÒÀÍÎÂÀ ÌÀØÈÍÒÜÞÐÈÍÃÀcode(WriteM ; M)⇑q 0k 1T ; MKÏîñëå ýòîãî ÌÒ MK ïðèìåíÿåòñÿ ê âõîäíîìóñëîâó code(WriteM; M) , ò.å.
ïðîâåðÿåò,îñòàíàâëèâàåòñÿ ëè íà ïóñòîé ëåíòå ÌÒWriteM ; M .À ýòî ðàâíîñèëüíî ïðîâåðêå ñàìîïðèìåíèìîñòèÌÒ M .ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌ äîêàçàòåëüñòâå Òåîðåìû 5.3 ìû ïîñòðîèëèòðàíñëÿòîð, êîòîðûé ïîçâîëèë èñïîëüçîâàòü¾÷åðíûé ÿùèê¿, ðåøàþùèé îäíó àëãîðèòìè÷åñêóþ ïðîáëåìó, äëÿ ðåøåíèÿ äðóãîé ïðîáëåìû.Ýòîò ïðèåì èìååò øèðîêîå ïðèìåíåíèå.ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌ äîêàçàòåëüñòâå Òåîðåìû 5.3 ìû ïîñòðîèëèòðàíñëÿòîð, êîòîðûé ïîçâîëèë èñïîëüçîâàòü¾÷åðíûé ÿùèê¿, ðåøàþùèé îäíó àëãîðèòìè÷åñêóþ ïðîáëåìó, äëÿ ðåøåíèÿ äðóãîé ïðîáëåìû.Ýòîò ïðèåì èìååò øèðîêîå ïðèìåíåíèå.Áóäåì ãîâîðèòü, ÷òî ÿçûê L1 m-ñâîäèòñÿ(ìíîãî-îäíî ñâîäèòñÿ) ê ÿçûêó L2 , åñëèñóùåñòâóåò òîòàëüíàÿ Ò-âû÷èñëèìàÿ ôóíêöèÿϕ : Σ∗ → Σ∗ , óäîâëåòâîðÿþùàÿ óñëîâèþ:äëÿ ëþáîãî ñëîâà ww ∈ L1 ⇐⇒ ϕ(w ) ∈ L2 .ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÌÒ, âû÷èñëÿþùàÿ ôóíêöèþ ϕ , è ÿâëÿåòñÿ òåìñàìûì òðàíñëÿòîðîì, êîòîðûé ïîçâîëÿåò ðåøàòüðåøàòü îäíè àëãîðèòìè÷åñêèå ïðîáëåìû ïðèïîìîùè ¾ðåøàòåëåé¿ äðóãèõ ïðîáëåì.Òåîðåìà 5.4.
Åñëè ÿçûê L2 ÿâëÿåòñÿ ðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì), à ÿçûê L1m-ñâîäèòñÿ ê ÿçûêó L2 , òî ÿçûê L1 òàêæå ÿâëÿåòñÿðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì).ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÌÒ, âû÷èñëÿþùàÿ ôóíêöèþ ϕ , è ÿâëÿåòñÿ òåìñàìûì òðàíñëÿòîðîì, êîòîðûé ïîçâîëÿåò ðåøàòüðåøàòü îäíè àëãîðèòìè÷åñêèå ïðîáëåìû ïðèïîìîùè ¾ðåøàòåëåé¿ äðóãèõ ïðîáëåì.Òåîðåìà 5.4. Åñëè ÿçûê L2 ÿâëÿåòñÿ ðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì), à ÿçûê L1m-ñâîäèòñÿ ê ÿçûêó L2 , òî ÿçûê L1 òàêæå ÿâëÿåòñÿðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì).Äîêàçàòåëüñòâî. Ïóñòü (òîòàëüíàÿ) ÌÒ M2ðàñïîçíàåò ÿçûê L2 , à ÌÒ T âû÷èñëÿåò ôóíêöèþϕ , êîòîðàÿ ñâîäèò ÿçûê L1 ê ÿçûêó L2 . Òîãäà(òîòàëüíàÿ) ÌÒ T ; M2 ðàñïîçíàåò ÿçûê L1 .
QEDÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÅñëè ÿçûê L1 ÍÅ ÿâëÿåòñÿ ðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì) è m-ñâîäèòñÿê ÿçûêó L2 , òî ÿçûê L2 òàêæå ÍÅ ÿâëÿåòñÿðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì).Ñëåäñòâèå.ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÅñëè ÿçûê L1 ÍÅ ÿâëÿåòñÿ ðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì) è m-ñâîäèòñÿê ÿçûêó L2 , òî ÿçûê L2 òàêæå ÍÅ ÿâëÿåòñÿðåêóðñèâíûì (ðåêóðñèâíî ïåðå÷èñëèìûì).Òàê, íàïðèìåð, ìû âîñïîëüçîâàëèñü ýòèìñëåäñòâèåì ïðè äîêàçàòåëüñòâå Òåîðåìû 5.3,ïîñòðîèâ m-ñâåäåíèå ÿçûêàS = {code(M) : code(M) ∈ L(M)} ê ÿçûêóK = {code(M) : ε ∈ L(M)} .È òî÷íî òàê æå ìîæíî ïîêàçàòü àëãîðèòìè÷åñêóþíåðàçðåøèìîñòü ìíîãèõ äðóãèõ êëþ÷åâûõ çàäà÷ïðîãðàììèðîâàíèÿ.Ñëåäñòâèå.ÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÓòâåðæäåíèå 5.5.ßçûêTot = {code(M) : L(M) = Σ∗ }òîòàëüíîñòè ÌÒ) íåðåêóðñèâåí.(ïðîáëåìàÑÂÎÄÈÌÎÑÒÜ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÕÏÐÎÁËÅÌÓòâåðæäåíèå 5.5.ßçûêTot = {code(M) : L(M) = Σ∗ }(ïðîáëåìàòîòàëüíîñòè ÌÒ) íåðåêóðñèâåí.Äîêàçàòåëüñòâî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
