4. Одноленточные машины Тьюринга. Вычисления машин Тьюринга. Рекурсивные и рекурсивно-перечислимые языки (1162495), страница 3
Текст из файла (страница 3)
Äîêàæèòå, ÷òî âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèíû Òüþðèíãà íå çàâèñÿò îò÷èñëà ñèìâîëîâ ðàáî÷åãî àëôàâèòà Γ .Çàäà÷à 4.1.ÂÀÐÈÀÖÈÈ ÌÀØÈÍ ÒÜÞÐÈÍÃÀÄîêàæèòå, ÷òî âû÷èñëèòåëüíûåâîçìîæíîñòè ìàøèíû Òüþðèíãà íå èçìåíÿþòñÿ,åñëè âìåñòî ôóíêöèè ïåðåõîäîâ îíà èñïîëüçóåòîòíîøåíèå ïåðåõîäîâ, ïîçâîëÿþùåå â íåêîòîðûõêîíôèãóðàöèÿõ íåäåòåðìèíèðîâàííî âûáèðàòüäëÿ âûïîëíåíèÿ îäíó èç íåñêîëüêèõ êîìàíä.Çàäà÷à 4.4. (Òðóäíàÿ) Äîêàæèòå, ÷òîâû÷èñëèòåëüíûå âîçìîæíîñòè ìàøèíû Òüþðèíãàíå èçìåíÿþòñÿ, åñëè âìåñòî áåñêîíå÷íîé ëåíòûîíà áóäåò ðàáîòàòü ñ î÷åðåäüþ, ñ÷èòûâàÿ áóêâûèç íà÷àëà î÷åðåäè è çàïèñûâàÿ áóêâû â êîíåöî÷åðåäè.Çàäà÷à 4.3.ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.6.
Êëàññ ðåêóðñèâíûõ ÿçûêîâ çàìêíóò îòíîñèòåëüíîîïåðàöèé îáúåäèíåíèÿ, ïåðåñå÷åíèÿ è äîïîëíåíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíûå ÿçûêè L1 è L2ðàñïîçíàþòñÿ òîòàëüíûìè 1-ëåòíî÷íûìè ÌÒ M1 è M2 .Ïîñòðîèì òîòàëüíóþ 2-ëåíòî÷íóþ ÌÒ M1∩2 , ðàñïîçíàþùóþÿçûê L1 ∩ L2 .ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.6. Êëàññ ðåêóðñèâíûõ ÿçûêîâ çàìêíóò îòíîñèòåëüíîîïåðàöèé îáúåäèíåíèÿ, ïåðåñå÷åíèÿ è äîïîëíåíèÿ.Äîêàçàòåëüñòâî.
Ïóñòü ðåêóðñèâíûå ÿçûêè L1 è L2ðàñïîçíàþòñÿ òîòàëüíûìè 1-ëåòíî÷íûìè ÌÒ M1 è M2 .Ïîñòðîèì òîòàëüíóþ 2-ëåíòî÷íóþ ÌÒ M1∩2 , ðàñïîçíàþùóþÿçûê L1 ∩ L2 .ÌÒ M1∩2 , ïîëó÷èâ âõîäíîå ñëîâî, êîïèðóåò åãî íà ðàáî÷óþëåíòó è çàïóñêàåò íà âõîäíîé ëåíòå ÌÒ M1 . Åñëè ýòà ÌÒäîñòèãàåò äîïóñêàþùåãî ñîñòîÿíèÿ, òî íà ðàáî÷åé ëåíòåçàïóñêàåòñÿ ÌÒ M2 . Åñëè è îíà äîñòèãàíò äîïóñêàþùåãîñîñòîÿíèÿ, òî ÌÒ M1∩2 äîïóñêàåò âõîäíîå ñëîâî.ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.6. Êëàññ ðåêóðñèâíûõ ÿçûêîâ çàìêíóò îòíîñèòåëüíîîïåðàöèé îáúåäèíåíèÿ, ïåðåñå÷åíèÿ è äîïîëíåíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíûå ÿçûêè L1 è L2ðàñïîçíàþòñÿ òîòàëüíûìè 1-ëåòíî÷íûìè ÌÒ M1 è M2 .Ïîñòðîèì òîòàëüíóþ 2-ëåíòî÷íóþ ÌÒ M1∩2 , ðàñïîçíàþùóþÿçûê L1 ∩ L2 .ÌÒ M1∩2 , ïîëó÷èâ âõîäíîå ñëîâî, êîïèðóåò åãî íà ðàáî÷óþëåíòó è çàïóñêàåò íà âõîäíîé ëåíòå ÌÒ M1 .
Åñëè ýòà ÌÒäîñòèãàåò äîïóñêàþùåãî ñîñòîÿíèÿ, òî íà ðàáî÷åé ëåíòåçàïóñêàåòñÿ ÌÒ M2 . Åñëè è îíà äîñòèãàíò äîïóñêàþùåãîñîñòîÿíèÿ, òî ÌÒ M1∩2 äîïóñêàåò âõîäíîå ñëîâî.Ïîêàæèòå ñàìîñòîÿòåëüíî, êàê ïîñòðîèòü ÌÒ, äîïóñêàþùèåÿçûêè L1 ∪ L2 è Σ∗ \ L1QEDÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.7. Êëàññ ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ çàìêíóòîòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè L1 èL2 ðàñïîçíàþòñÿ 1-ëåòíî÷íûìè ÌÒ M1 è M2 . Ïîñòðîèì2-ëåíòî÷íóþ ÌÒ M1∪2 , ðàñïîçíàþùóþ ÿçûê L1 ∪ L2 .ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.7.
Êëàññ ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ çàìêíóòîòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè L1 èL2 ðàñïîçíàþòñÿ 1-ëåòíî÷íûìè ÌÒ M1 è M2 . Ïîñòðîèì2-ëåíòî÷íóþ ÌÒ M1∪2 , ðàñïîçíàþùóþ ÿçûê L1 ∪ L2 .ÌÒ M1∪2 , ïîëó÷èâ âõîäíîå ñëîâî, êîïèðóåò åãî íà ðàáî÷óþëåíòó è çàïóñêàåò íà îáåèõ ëåíòàõ ÌÒ M1 è M2 , ÷åðåäóÿøàãè èõ âû÷èñëåíèé. Åñëè õîòÿ áû îäíà èç ýòèõ ÌÒ äîñòèãàåòäîïóñêàþùåãî ñîñòîÿíèÿ, òî ÌÒ M1∩2 äîïóñêàåò âõîäíîåñëîâî.ÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.7. Êëàññ ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ çàìêíóòîòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè L1 èL2 ðàñïîçíàþòñÿ 1-ëåòíî÷íûìè ÌÒ M1 è M2 . Ïîñòðîèì2-ëåíòî÷íóþ ÌÒ M1∪2 , ðàñïîçíàþùóþ ÿçûê L1 ∪ L2 .ÌÒ M1∪2 , ïîëó÷èâ âõîäíîå ñëîâî, êîïèðóåò åãî íà ðàáî÷óþëåíòó è çàïóñêàåò íà îáåèõ ëåíòàõ ÌÒ M1 è M2 , ÷åðåäóÿøàãè èõ âû÷èñëåíèé.
Åñëè õîòÿ áû îäíà èç ýòèõ ÌÒ äîñòèãàåòäîïóñêàþùåãî ñîñòîÿíèÿ, òî ÌÒ M1∩2 äîïóñêàåò âõîäíîåñëîâî.Ïîêàæèòå ñàìîñòîÿòåëüíî, êàê ïîñòðîèòü ÌÒ, äîïóñêàþùóþÿçûê L1 ∩ L2QEDÑÂÎÉÑÒÂÀ ÇÀÌÊÍÓÒÎÑÒÈÒåîðåìà 4.7. Êëàññ ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâ çàìêíóòîòíîñèòåëüíî îïåðàöèé îáúåäèíåíèÿ è ïåðåñå÷åíèÿ.Äîêàçàòåëüñòâî. Ïóñòü ðåêóðñèâíî ïåðå÷èñëèìûå ÿçûêè L1 èL2 ðàñïîçíàþòñÿ 1-ëåòíî÷íûìè ÌÒ M1 è M2 . Ïîñòðîèì2-ëåíòî÷íóþ ÌÒ M1∪2 , ðàñïîçíàþùóþ ÿçûê L1 ∪ L2 .ÌÒ M1∪2 , ïîëó÷èâ âõîäíîå ñëîâî, êîïèðóåò åãî íà ðàáî÷óþëåíòó è çàïóñêàåò íà îáåèõ ëåíòàõ ÌÒ M1 è M2 , ÷åðåäóÿøàãè èõ âû÷èñëåíèé.
Åñëè õîòÿ áû îäíà èç ýòèõ ÌÒ äîñòèãàåòäîïóñêàþùåãî ñîñòîÿíèÿ, òî ÌÒ M1∩2 äîïóñêàåò âõîäíîåñëîâî.Ïîêàæèòå ñàìîñòîÿòåëüíî, êàê ïîñòðîèòü ÌÒ, äîïóñêàþùóþÿçûê L1 ∩ L2QEDÂîïðîñ î çàìêíóòîñòè êëàññà ðåêóðñèâíî ïåðå÷èñëèìûõ ÿçûêîâîòíîñèòåëüíî äîïîëíåíèÿ ðàâíîñèëåí âîïðîñó î ñîâïàäåíèèýòîãî êëàññà ñ êëàññîì ðåêóðñèâíûõ ÿçûêîâ.ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÌíîãîëåíòî÷íûå ÌÒ ìîæíî èñïîëüçîâàòü íåòîëüêî äëÿ ðàñïîçíàâàíèÿ ñëîâ, íî è äëÿâû÷èñëåíèÿ îäíèõ ñëîâ èç äðóãèõ.Äëÿ ýòîé öåëè âûäåëÿåòñÿ îòäåëüíàÿ ëåíòà ëåíòà âûõîäà . Ïîëó÷èâ ñëîâî íà âõîäíîé ëåíòå,ÌÒ ïðîâîäèò âû÷èñëåíèå, èñïîëüçóÿ ðàáî÷èåëåíòû, çàïèñûâàåò ðåçóëüòàò (ñëîâî â âûõîäíîìàëôàâèòå ∆ ) íà ëåíòå âûõîäà è îñòàíàâëèâàåòñÿâ äîïóñêàþùåì ñîñòîÿíèè (èëè çàöèêëèâàåòñÿ).Ñëîâàðíûå ôóíêöèè F : Σ∗ → ∆∗ , âû÷èñëèìûåòàêèì îáðàçîì íà ÌÒ, íàçûâàþòñÿ âû÷èñëèìûìèïî Òüþðèíãó (êîðîòêî, Ò-ôóíêöèÿìè).ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÏîñêîëüêó êàæäîå ñëîâî w = aj aj .
. . aj âàëôàâèòå a1, . . . , ak ïðåäñòàâëÿåòçàïèñümPíàòóðàëüíîãî ÷èñëà nw = ji · k m−i, cëîâàðíûåi=1ôóíêöèè F : Σ∗ → ∆∗ ìîæíî èñòîëêîâûâàòü, êàêàðèôìåòè÷åñêèå ôóíêöèè.Èçâåñòíà ñëåäóþùàÿ12mÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÏîñêîëüêó êàæäîå ñëîâî w = aj aj . . . aj âàëôàâèòå a1, . . .
, ak ïðåäñòàâëÿåòçàïèñümPíàòóðàëüíîãî ÷èñëà nw = ji · k m−i, cëîâàðíûåi=1ôóíêöèè F : Σ∗ → ∆∗ ìîæíî èñòîëêîâûâàòü, êàêàðèôìåòè÷åñêèå ôóíêöèè.Èçâåñòíà ñëåäóþùàÿÒåîðåìà. [Ñ. Êëèíè] Êëàññ àðèôìåòè÷åñêèõÒ-ôóíêöèé ñîâïàäàåò ñ êëàññîì ÷àñòè÷íîðåêóðñèâíûõ ôóíêöèé.12mÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÊëàññ ðåêóðñèâíûõ è ðåêóðñèâíî ïåðå÷èñëèìûõÿçûêîâ ìîæíî îõàðàêòåðèçîâàòü â òåðìèíàõÒ-ôóíêöèé.Òåîðåìà 4.8. ßçûê L, L ⊆ Σ∗ , ÿâëÿåòñÿðåêóðñèâíûì òîãäà è òîëüêî òîãäà, êîãäàñóùåñòâóåò Ò-ôóíêöèÿ(1, åñëè w ∈ L,F (w ) =0, åñëè w ∈/ L,Äîêàçàòåëüñòâî. Î÷åâèäíî.ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓßçûê L, L ⊆ Σ∗, ÿâëÿåòñÿðåêóðñèâíî ïåðå÷èñëèìûì òîãäà è òîëüêî òîãäà,êîãäà ñóùåñòâóåò Ò-ôóíêöèÿ(1, åñëè w ∈ L,H(w ) =íåîïðåäåëåíî, åñëè w ∈/ L,Äîêàçàòåëüñòâî. Î÷åâèäíî.Òåîðåìà 4.9.ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓßçûê L, L ⊆ Σ∗, ÿâëÿåòñÿðåêóðñèâíî ïåðå÷èñëèìûì òîãäà è òîëüêî òîãäà,êîãäà ñóùåñòâóåò Ò-ôóíêöèÿ(1, åñëè w ∈ L,H(w ) =íåîïðåäåëåíî, åñëè w ∈/ L,Äîêàçàòåëüñòâî.
Î÷åâèäíî.Íî åñòü è áîëåå èíòåðåñíîå îïèñàíèå ðåêóðñèâíîïåðå÷èñëèìûõ ÿçûêîâ, îáúÿñíÿþùååïðîèñõîæäåíèå ýòîãî òåðìèíà.Òåîðåìà 4.9.ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓßçûê L, L ⊆ Σ∗, L 6= ∅, ÿâëÿåòñÿðåêóðñèâíî ïåðå÷èñëèìûì òîãäà è òîëüêî òîãäà,êîãäà ñóùåñòâóåò òàêàÿ âñþäó îïðåäåëåííàÿÒ-ôóíêöèÿ E : N → Σ∗ , îáëàñòüþ çíà÷åíèéêîòîðîé ÿâëÿåòñÿ ÿçûê L .Òåîðåìà óòâåðæäàåò, ÷òî ðåêóðñèâíàÿ ôóíêöèÿ Eñïîñîáíà ïåðå÷èñëèòü âñå ñëîâà ÿçûêà L .Òåîðåìà 4.10.ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ( ) Ïóñòü L = E (N) .Ñëåäóþùàÿ ÌÒ M ðàñïîçíàåò ÿçûê L .Äëÿ ïðîâåðêè âêëþ÷åíèÿ w ∈ L îíà çàïóñêàåòÌÒ, âû÷èñëÿþùóþ ôóíêöèþ E , ïîñëåäîâàòåëüíîíà âñåõ íàòóðàëüíûõ ÷èñëàõ, äî òåõ ïîð ïîêà íåáóäåò âû÷èñëåíî âûõîäíîå ñëîâî w .Åñëè ýòî ñëó÷èòñÿ, òî M ïåðåõîäèò âäîïóñêàþùåå ñîñòîÿíèå.Äîêàçàòåëüñòâî.
⇐ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ( )Ïðåäïîëîæèì, ÷òî ÌÒ M ðàñïîçíàåò ÿçûê L .Ïîñêîëüêó ÿçûê L íåïóñò, ñóùåñòâóåò âõîäíîåñëîâî w0, w0 ∈ L .Ðàñïîëîæèì âñå âõîäíûå ñëîâà èç ìíîæåñòâà Σ∗â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: u1, u2, u3, . . . .Äîêàçàòåëüñòâî. ⇒ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ( )Ïðåäïîëîæèì, ÷òî ÌÒ M ðàñïîçíàåò ÿçûê L .Ïîñêîëüêó ÿçûê L íåïóñò, ñóùåñòâóåò âõîäíîåñëîâî w0, w0 ∈ L .Ðàñïîëîæèì âñå âõîäíûå ñëîâà èç ìíîæåñòâà Σ∗â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: u1, u2, u3, . . . .À òåïåðü ïðèâåäåì ðåêóðñèâíîå îïèñàíèåôóíêöèè E , ïåðå÷èñëÿþùåé âñå ñëîâà ÿçûêà L .Äîêàçàòåëüñòâî. ⇒ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0).
Ïîëîæèì E (0) = w0 .ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0). Ïîëîæèì E (0) = w0 .n → n+1). ×òîáû âû÷èñëèòü E (n + 1) íóæíî1. Âû÷èñëèòü ñïèñîê âõîäíûõ ñëîâWn = {E (0), E (1), . . . , E (n)} ;ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0). Ïîëîæèì E (0) = w0 .n → n+1). ×òîáû âû÷èñëèòü E (n + 1) íóæíî1. Âû÷èñëèòü ñïèñîê âõîäíûõ ñëîâWn = {E (0), E (1), . . . , E (n)} ;2.
Ñôîðìèðîâàòü ñïèñîê ñëîâ Un = {u0, u1, . . . , un , un+1} \Wn ;ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0). Ïîëîæèì E (0) = w0 .n → n+1). ×òîáû âû÷èñëèòü E (n + 1) íóæíî1. Âû÷èñëèòü ñïèñîê âõîäíûõ ñëîâWn = {E (0), E (1), . . . , E (n)} ;2. Ñôîðìèðîâàòü ñïèñîê ñëîâ Un = {u0, u1, . . . , un , un+1} \Wn ;3. Ïðèìåíèòü ÌÒ M ê êàæäîìó ñëîâó èç ñïèñêà Un ,îãðàíè÷èâ âðåìÿ åå ðàáîòû n + 1 òàêòàìè;ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0).
Ïîëîæèì E (0) = w0 .n → n+1). ×òîáû âû÷èñëèòü E (n + 1) íóæíî1. Âû÷èñëèòü ñïèñîê âõîäíûõ ñëîâWn = {E (0), E (1), . . . , E (n)} ;2. Ñôîðìèðîâàòü ñïèñîê ñëîâ Un = {u0, u1, . . . , un , un+1} \Wn ;3. Ïðèìåíèòü ÌÒ M ê êàæäîìó ñëîâó èç ñïèñêà Un ,îãðàíè÷èâ âðåìÿ åå ðàáîòû n + 1 òàêòàìè;4. Åñëè ÌÒ M ïðè ðàáîòå ñ êàæäûì èç ñëîâ ñïèñêà Un íåäîñòèãàåò äîïóñêàþùåãî ñîñòîÿíèÿ çà n + 1 èëè ìåíååòàêòîâ ðàáîòû, òî ïîëîæèòü E (n + 1) = w0 ;ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓ0). Ïîëîæèì E (0) = w0 .n → n+1). ×òîáû âû÷èñëèòü E (n + 1) íóæíî1. Âû÷èñëèòü ñïèñîê âõîäíûõ ñëîâWn = {E (0), E (1), .
. . , E (n)} ;2. Ñôîðìèðîâàòü ñïèñîê ñëîâ Un = {u0, u1, . . . , un , un+1} \Wn ;3. Ïðèìåíèòü ÌÒ M ê êàæäîìó ñëîâó èç ñïèñêà Un ,îãðàíè÷èâ âðåìÿ åå ðàáîòû n + 1 òàêòàìè;4. Åñëè ÌÒ M ïðè ðàáîòå ñ êàæäûì èç ñëîâ ñïèñêà Un íåäîñòèãàåò äîïóñêàþùåãî ñîñòîÿíèÿ çà n + 1 èëè ìåíååòàêòîâ ðàáîòû, òî ïîëîæèòü E (n + 1) = w0 ;5.  ïðîòèâíîì ñëó÷àå âûáðàòü ñëîâî u ñíàèìåíüøèì ïîðÿäêîâûì íîìåðîì ñðåäè òåõ ñëîâ ñïèñêàUn , ïðè ðàáîòå ñ êîòîðûìè ÌÒ M äîñòèãëàäîïóñêàþùåãî ñîñòîÿíèÿ íå áîëåå ÷åì çà n + 1 òàêòîâðàáîòû, è ïîëîæèòü E (n + 1) = u .ÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÈç ïðèâåäåííîãî îïèñàíèÿ âèäíî, ÷òîE (x) âñþäó îïðåäåëåííàÿ Ò-âû÷èñëèìàÿôóíêöèÿ;IÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÈç ïðèâåäåííîãî îïèñàíèÿ âèäíî, ÷òîE (x) âñþäó îïðåäåëåííàÿ Ò-âû÷èñëèìàÿôóíêöèÿ;çíà÷åíèÿìè ôóíêöèè E (x) ÿâëÿþòñÿ òîëüêîñëîâà ÿçûêà L = L(M) ;IIÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÈç ïðèâåäåííîãî îïèñàíèÿ âèäíî, ÷òîE (x) âñþäó îïðåäåëåííàÿ Ò-âû÷èñëèìàÿôóíêöèÿ;çíà÷åíèÿìè ôóíêöèè E (x) ÿâëÿþòñÿ òîëüêîñëîâà ÿçûêà L = L(M) ;åñëè âõîäíîå ñëîâî u èìååò ïîðÿäêîâûé íîìåðk è äîïóñêàåòñÿ ÌÒ M çà m òàêòîâ ðàáîòû,òî E (n) = u äëÿ íåêîòîðîãî n, 0 ≤ n ≤ m + k .Òàêèì îáðàçîì, âñÿêèé ðåêóðñèâíî ïåðå÷èñëèìûéÿçûê ãåíåðèðóåòñÿ íåêîòîðîé âñþäó îïðåäåëåííîéÒ-âû÷èñëèìîé (ò.å.
ðåêóðñèâíîé) ôóíêöèåé. QEDIIIÔÓÍÊÖÈÈ, ÂÛ×ÈÑËÈÌÛÅ ÏÎ ÒÜÞÐÈÍÃÓÄîêàæèòå, ÷òî áåñêîíå÷íûé ÿçûêL, L ⊆ Σ , L 6= ∅, ÿâëÿåòñÿ ðåêóðñèâíûì òîãäà èòîëüêî òîãäà, êîãäà ñóùåñòâóåò âñþäó îïðåäåëåííàÿÒ-ôóíêöèÿ E : N → Σ∗ , ïåðå÷èñëÿþùàÿ ñëîâàýòîãî ÿçûêà â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå.Çàäà÷à 4.6. Äîêàæèòå, ÷òî ÿçûê L, L ⊆ Σ∗ ,ÿâëÿåòñÿ ðåêóðñèâíî ïåðå÷èñëèìûì, åñëèñóùåñòâóåò íåäåòåðìèíèðîâàííàÿ ÌÒ,êîòîðàÿ, êîòîðàÿ ïîëó÷èâ íà âõîäå ïóñòóþ ëåíòó,ìîæåò íàïå÷àòàòü íà âûõîäíîé ëåíòå âñå ñëîâàÿçûêà L, L ⊆ Σ∗, è òîëüêî ýòè ñëîâà.Çàäà÷à 4.5.∗ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÌàòåìàòè÷åñêèå çàäà÷è ìîæíî ðàçäåëèòü íà äâàêëàññà:èíäèâèäóàëüíûå çàäà÷è : íàïðèìåð, ðåøèòüóðàâíåíèå x 4 + 2x 2 + 1 = 0 ;ìàññîâûå ïðîáëåìû : íàïðèìåð, ðåøèòü ëþáîåóðàâíåíèå âèäà ax 4 + bx 3 + cx 2 + dx + e = 0.IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÌàòåìàòè÷åñêèå çàäà÷è ìîæíî ðàçäåëèòü íà äâàêëàññà:èíäèâèäóàëüíûå çàäà÷è : íàïðèìåð, ðåøèòüóðàâíåíèå x 4 + 2x 2 + 1 = 0 ;ìàññîâûå ïðîáëåìû : íàïðèìåð, ðåøèòü ëþáîåóðàâíåíèå âèäà ax 4 + bx 3 + cx 2 + dx + e = 0.×òîáû ïðîäåìîíñòðèðîâàòü ñïîñîáíîñòü ðåøàòüèíäèâèäóàëüíóþ çàäà÷ó, Âàì äîñòàòî÷íî ïðèâåñòèåå ïðàâèëüíîå ðåøåíèå, è îáúÿñíèòü, êàêïðîâåðèòü åãî ïðàâèëüíîñòü.IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÌàòåìàòè÷åñêèå çàäà÷è ìîæíî ðàçäåëèòü íà äâàêëàññà:èíäèâèäóàëüíûå çàäà÷è : íàïðèìåð, ðåøèòüóðàâíåíèå x 4 + 2x 2 + 1 = 0 ;ìàññîâûå ïðîáëåìû : íàïðèìåð, ðåøèòü ëþáîåóðàâíåíèå âèäà ax 4 + bx 3 + cx 2 + dx + e = 0.×òîáû ïðîäåìîíñòðèðîâàòü ñïîñîáíîñòü ðåøàòüèíäèâèäóàëüíóþ çàäà÷ó, Âàì äîñòàòî÷íî ïðèâåñòèåå ïðàâèëüíîå ðåøåíèå, è îáúÿñíèòü, êàêïðîâåðèòü åãî ïðàâèëüíîñòü.À êàê ïîäòâåðäèòü óìåíèå ðåøàòü ìàññîâóþïðîáëåìó?IIÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÄî ñåðåäèíû XX âåêà ìàòåìàòèêè íå çíàëèñðåäñòâ äëÿ ôîðìàëüíîãî îïðåäåëåíèÿ ïîíÿòèÿ¾ñïîñîá ðåøåíèÿ çàäà÷è¿.È ïîýòîìó îíè íå ìîãëè äîêàçûâàòü óòâåðæäåíèÿî òîì, ÷òî íåêîòîðûå ìàññîâûå ïðîáëåìû íåèìåþò ñïîñîáà èõ ðåøåíèÿ.ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÄî ñåðåäèíû XX âåêà ìàòåìàòèêè íå çíàëèñðåäñòâ äëÿ ôîðìàëüíîãî îïðåäåëåíèÿ ïîíÿòèÿ¾ñïîñîá ðåøåíèÿ çàäà÷è¿.È ïîýòîìó îíè íå ìîãëè äîêàçûâàòü óòâåðæäåíèÿî òîì, ÷òî íåêîòîðûå ìàññîâûå ïðîáëåìû íåèìåþò ñïîñîáà èõ ðåøåíèÿ.Ñ ïîÿâëåíèåì ôîðìàëüíûõ îïðåäåëåíèé ïîíÿòèÿ¾àëãîðèòìà¿ ìàòåìàòèêè ïðèøëè ê ñîãëàøåíèþ îòîì, ÷òî ñïîñîáîì ðåøåíèÿ çàäà÷è ñëåäóåòñ÷èòàòü ôîðìàëüíûé àëãîðèòì åå ðåøåíèÿ.È òîãäà ïîÿâèëàñü âîçìîæíîñòü ôîðìàëèçîâàòüïîíÿòèå ¾ìàññîâîé àëãîðèòìè÷åñêîé ïðîáëåìû¿.ÌÀÑÑÎÂÛÅ ÀËÃÎÐÈÒÌÈ×ÅÑÊÈÅÏÐÎÁËÅÌÛÌû áóäåì ðàññìàòðèâàòü èíäèâèäóàëüíûå çàäà÷èðàñïîçíàâàíèÿ, ðåøåíèÿìè êîòîðûõ ñëóæàòîòâåòû ¾äà¿ èëè ¾íåò¿.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
