С.С. Марченков - Избранные главы дискретной математики (1124120), страница 14
Текст из файла (страница 14)
. . , fm } ñóùåñòâóåò, è r1 , . . . , rm âåñà ôóíêöèé f1 , . . . , fm . Ïóñòüp ïðîñòîå ÷èñëî è p > max(r1 , . . . , rm ). Îïðåäåëèì êîíå÷íî-àâòîìàòíóþôóíêöèþ f (x), êîòîðàÿ ïåðåðàáàòûâàåò ëþáóþ âõîäíóþ ïîñëåäîâàòåëüíîñòü â ïåðèîäè÷åñêóþ ïîñëåäîâàòåëüíîñòü ñ ïåðèîäîì 0p−1 1. Èñïîëüçóÿòåîðåìó 3.9, ïîëó÷àåì, ÷òî ôóíêöèþ f íåâîçìîæíî ðåàëèçîâàòü ñóïåðïîçèöèÿìè ôóíêöèé f1 , . .
. , fm . Òåîðåìà äîêàçàíà.Äîêàçàòåëüñòâî.ÓÏÐÀÆÍÅÍÈßêàÈñïîëüçóÿ ïîëíóþ â êëàññå P ,2 ñèñòåìó êîíå÷íî-àâòîìàòíûõ ôóíêöèé {f∨ , f& , f− , ç}, îïðåäåëèòü ñ ïîìîùüþ îïåðàöèé ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè ñëåäóþùèå êîíå÷íî-àâòîìàòíûå ôóíêöèè:8. y(t) = x(t) ⊕ q(t − 1),1)q(t) = x̄(t) · q̄(t − 1),q(0) = 0,y1 (t) = x̄1 (t) ∨ x2 (t) ∨ q1 (t − 1), y2 (t) = q̄1 (t − 1) ∨ x̄2 (t) · q2 (t − 1),q1 (t) = x2 (t) → q1 (t − 1),2)q (t) = q̄2 (t − 1) ∨ x1 (t), 2q1 (0) = q2 (0) = 0.Äîêàçàòü ïîëíîòó ñèñòåìû ôóíêöèé {f1 , f2 } â êëàññå Pòåëüíî îïåðàöèé ñóïåðïîçèöèè è ââåäåíèÿ îáðàòíîé ñâÿçè:1) f1 : y(t) = x̄1 (t) · x̄2 (t) (t > 1),9. y(t) = x1 (t) · x̄2 (t) ∨ q(t − 1),q(t) = x1 (t) ∨ x2 (t),f2 :q(0) = 0;2) f1 : y(t) = x1 (t) → x̄2 (t) (t > 1), y(t) = (x1 (t) → x2 (t)) · q(t − 1),f2 :q(t) = x1 (t) · x2 (t),q(0) = 0.64êà,2 îòíîñè-Ãëàâà 4ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ È ÂÛ×ÈÑËÈÌÛÅ ÔÓÍÊÖÈÈ 1.
Ìàøèíà Òüþðèíãà ñåðåäèíå 1930-õ ãîäîâ íåñêîëüêèì ìàòåìàòèêàì (À. ×¼ð÷, Ê. üäåëü,À. Òüþðèíã, Ý. Ïîñò, Ñ. Êëèíè) è ñ èñïîëüçîâàíèåì ðàçëè÷íûõ ïîäõîäîâóäàëîñü ïîëó÷èòü òî÷íûå ìàòåìàòè÷åñêèå ôîðìóëèðîâêè äëÿ ïîíÿòèéàëãîðèòìà è àëãîðèòìè÷åñêè âû÷èñëèìîé ôóíêöèè. Îäèí èç ýòèõ ïîäõîäîâ áûë ïðåäëîæåí àíãëèéñêèì ìàòåìàòèêîì À.Òüþðèíãîì (A.Turing,19121954) è áàçèðîâàëñÿ íà íåêîòîðîì àáñòðàêòíîì âû÷èñëèòåëüíîìóñòðîéñòâå, êîòîðîå âïîñëåäñòâèè áûëî íàçâàíî. ×óòüïîçæå ïî÷òè òàêîå æå ïîíÿòèå àáñòðàêòíîé âû÷èñëèòåëüíîé ìàøèíûáûëî ïðåäëîæåíî àìåðèêàíñêèì ìàòåìàòèêîì Ý.
Ïîñòîì (E. Post, 18971954). Ïîýòîìó èíîãäà ìàøèíû Òüþðèíãà íàçûâàþò ìàøèíàìè ÒüþðèíãàÏîñòà. Ìû áóäåì èñïîëüçîâàòü áîëåå ðàñïðîñòðàíåííîå íàçâàíèå.ñîñòîèò èç,è(ñì. ðèñ. ??).ìàøèíîé Òüþðèíãàìàøè-íà ÒüþðèíãàÌàøèíà Òüþðèíãàëåíòû ñ÷èòûâàþùå-çàïèñûâàþùåé ãîëîâêè óïðàâëÿþùåãî óñòðîéñòâàÐèñ. 1: Ìàøèíà ÒüþðèíãàËåíòà áåñêîíå÷íà âëåâî è âïðàâî è ðàçáèòà íà êëåòêè.
 êàæäîéêëåòêå ëåíòû ìîæåò áûòü çàïèñàí îäèí èç ñèìâîëîâ (áóêâ) êîíå÷íîãîëåíòî÷íîãî àëôàâèòà A = {a0 , a1 , . . . , ak }. Îáû÷íî â àëôàâèòå A âûäåëÿåòñÿ òàê íàçûâàåìûé ¾ïóñòîé¿ ñèìâîë a0 .ìàøèíû ìîæåò:äâèãàòüñÿ ïî ëåíòå âëåâî è âïðàâî, ïåðåìåùàÿñü èç îäíîé êëåòêè âñîñåäíþþ ñ íåé êëåòêó;÷èòàòü ñèìâîë, çàïèñàííûé â êëåòêå, è çàïèñûâàòü â îáîçðåâàåìóþêëåòêó ëþáîé ñèìâîë àëôàâèòà A.Ãîëîâêà65Óïðàâëÿþùåå óñòðîéñòâî îðãàíèçóåò ïåðåìåùåíèå ãîëîâêè íà ëåíòåè çàïèñü ñèìâîëîâ â êëåòêè ëåíòû. Îíî ìîæåò íàõîäèòüñÿ â îäíîì èçêîíå÷íîãî ÷èñëàq0 , q1 , .
. . , qr .  ìíîæåñòâå ñîñòîÿíèé âûäåëÿþòñÿq1 èq0 .Èçìåíåíèå ïîëîæåíèÿ ãîëîâêè íà ëåíòå, çàïèñü íîâûõ ñèìâîëîâ âêëåòêè ëåíòû è ïåðåõîä â äðóãèå ñîñòîÿíèÿ ïðîèñõîäèò ñîãëàñíîìàøèíû, êîòîðàÿ ñîñòîèò èçâèäàñîñòîÿíèéíà÷àëüíîå ñîñòîÿíèåçàêëþ÷èòåëüíîå ñîñòîÿíèåãðàììåêîìàíäai qj → al Dqs ,ïðî-(4.1)ãäå j 6= 0 è D åñòü îäèí èç ñèìâîëîâ äâèæåíèÿ: L, R, S . Äëÿ ëþáûõâîçìîæíûõ çíà÷åíèé i, j (0 6 i 6 k, 1 6 j 6 r) ïðîãðàììà ìàøèíûñîäåðæèò ðîâíî îäíó êîìàíäó (4.1) ñ ëåâîé ÷àñòüþ ai qj . Îáû÷íî ïðîãðàììó ìàøèíû Òüþðèíãà çàïèñûâàþò â âèäå òàáëèöû, ñòðîêè êîòîðîéïîìå÷åíû ñèìâîëàìè a0 , a1 , .
. . , ak , à ñòîëáöû ñèìâîëàìè q1 , . . . , qr . Âêëåòêå òàáëèöû, îòâå÷àþùåé ñòðîêå ai è ñòîëáöó qj , çàïèñàíà ïðàâàÿ÷àñòü al Dqs êîìàíäû (4.1).Ðàáîòà ìàøèíû Òüþðèíãà ïðîòåêàåò â äèñêðåòíîì âðåìåíè t = 1, 2, . . ..Ïåðåä íà÷àëîì ðàáîòû ìàøèíû Òüþðèíãà (t = 0) íà ëåíòå çàïèñûâàåòñÿíåêîòîðîå ñëîâî ā â àëôàâèòå {a1 , . . . , ak }, âñÿ îñòàëüíàÿ ÷àñòü ëåíòû(ñëåâà è ñïðàâà îò ñëîâà ā) çàïîëíÿåòñÿ ¾ïóñòûì¿ ñèìâîëîì a0 . Ãîëîâêàìàøèíû Òüþðèíãà óñòàíàâëèâàåòñÿ â êëåòêó, ñîäåðæàùóþ ïåðâóþ áóêâóñëîâà ā, à óïðàâëÿþùåå óñòðîéñòâî ïðèâîäèòñÿ â ñîñòîÿíèå q1 .Êàæäûé èç ïîñëåäóþùèõ íåçàêëþ÷èòåëüíûõ øàãîâ (òàêòîâ) ðàáîòûìàøèíû Òüþðèíãà âûïîëíÿåòñÿ ñîãëàñíî îäíîìó è òîìó æå ïðàâèëó:åñëè â ìîìåíò âðåìåíè t ãîëîâêà ìàøèíû Òüþðèíãà ñ÷èòûâàåò ñèìâîë ai ,óïðàâëÿþùåå óñòðîéñòâî íàõîäèòñÿ â ñîñòîÿíèè qj (j 6= 0) è â ïðîãðàììåìàøèíû èìååòñÿ êîìàíäà (4.1), òî â ìîìåíò âðåìåíè t + 1:â îáîçðåâàåìóþ â ìîìåíò t êëåòêó ëåíòû áóäåò çàïèñàí ñèìâîë al(âîçìîæíî, ÷òî l = i);ãîëîâêà ñäâèíåòñÿ íà îäíó êëåòêó âëåâî (åñëè D = L), âïðàâî (åñëèD = R) èëè îñòàíåòñÿ â ïðåæíåé êëåòêå (åñëè D = S);óïðàâëÿþùåå óñòðîéñòâî ïåðåéäåò â ñîñòîÿíèå qs (è çäåñü âîçìîæíîðàâåíñòâî s = j ).Ìàøèíà Òüþðèíãà çàêàí÷èâàåò ðàáîòó, åñëè óïðàâëÿþùåå óñòðîéñòâîïîïàäàåò â çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 .Ñðàçó îòìåòèì, ÷òî, âîîáùå ãîâîðÿ, íå äëÿ âñåõ ñëîâ ā ìàøèíà Òüþðèíãà çàâåðøàåò ñâîþ ðàáîòó.
Äëÿ íåêîòîðûõ ñëîâ ā îíà ìîæåò ðàáîòàòüíåîãðàíè÷åííî äîëãî, íå ïîïàäàÿ â çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 .  ñëó66÷àå îêîí÷àíèÿ ðàáîòû ìàøèíû Òüþðèíãà ðåçóëüòàòîì ïðèìåíåíèÿ ìàøèíû ê ñëîâó ā îáû÷íî ñ÷èòàþò ñëîâî â àëôàâèòå {a1 , . . . , ak }, êîòîðîåîêàçûâàåòñÿ çàïèñàííûì íà ëåíòå â çàêëþ÷èòåëüíûé ìîìåíò âðåìåíè.Åñëè æå ìàøèíà Òüþðèíãà íå çàêàí÷èâàåò ðàáîòó, òî ðåçóëüòàò ïðèìåíåíèÿ ìàøèíû ê ñëîâó ā íå îïðåäåëåí.Ðàññìîòðèì ïðèìåðû ìàøèí Òüþðèíãà. Ìàøèíà Òüþðèíãà M1 , íà÷èíàÿ ðàáîòó íà ïåðâîì ñèìâîëå a1 ñëîâà ā = a1 . . .
a1 , îñòàâëÿåò åãî áåçèçìåíåíèÿ, ñäâèãàåò ãîëîâêó íà îäíó êëåòêó âïðàâî è îñòàíàâëèâàåòñÿ.Ìàøèíà Òüþðèíãà M2 òàêæå îñòàâëÿåò ïåðâûé ñèìâîë a1 ñëîâà ā =a1 . . . a1 áåç èçìåíåíèÿ, îäíàêî ñäâèãàåò ãîëîâêó íà îäíó êëåòêó âëåâî,çàïèñûâàåò â íåå åùå îäèí ñèìâîë a1 è îñòàíàâëèâàåòñÿ. Ìàøèíà Òüþðèíãà M3 íà ëþáîì ñëîâå ðàáîòàåò íåîãðàíè÷åííî äîëãî.a0a1q1a0 Rq1a1 Rq0M1a0a1q1a1 Sq0a1 Lq1M2a0a1q1a0 Sq1a1 Sq1M3 äàëüíåéøåì íàñ â ïåðâóþ î÷åðåäü áóäóò èíòåðåñîâàòü ôóíêöèè,âû÷èñëèìûå íà ìàøèíàõ Òüþðèíãà. ×òîáû îïðåäåëèòü ýòè ôóíêöèè,íåîáõîäèìî ïðåæäå âñåãî óñëîâèòüñÿ î ñïîñîáå ïðåäñòàâëåíèÿ ÷èñåë èçìíîæåñòâà N = {0, 1, 2, .
. .} (âñå âû÷èñëèìûå ôóíêöèè ðàñìàòðèâàþòñÿ,êàê ïðàâèëî, íà ìíîæåñòâå N ) íà ëåíòå ìàøèíû Òüþðèíãà. Ìû âûáåðåìñïîñîá, êîòîðûé íà ïðàêòèêå âñòðå÷àåòñÿ ðåäêî, îäíàêî óäîáåí â òåîðåòè÷åñêèõ ïîñòðîåíèÿõ. Èìåííî, ÷èñëî m èç N áóäåì ïðåäñòàâëÿòü ñëîâîì,ñîñòîÿùåì èç m + 1 ñèìâîëîâ 1 (¾ëèøíþþ¿ åäèíèöó äîáàâëÿåì, ÷òîáûèìåòü âîçìîæíîñòü ïðåäñòàâëÿòü ÷èñëî 0).
 ñâÿçè ñ ýòèì ëåíòî÷íûéàëôàâèò A ìàøèíû Òüþðèíãà, ïðåäíàçíà÷åííîé äëÿ âû÷èñëåíèÿ íåêîòîðîé ôóíêöèè, âñåãäà áóäåò ñîäåðæàòü ñèìâîë 1 (íàïðèìåð, a1 = 1),ïóñòîé ñèìâîë 0 (a0 = 0) è, âîçìîæíî, äðóãèå ñèìâîëû.Èòàê, ÷èñëî m èç N çàïèñûâàåì íà ëåíòå ìàøèíû Òüþðèíãà â âèäåìàññèâà èç m + 1 åäèíèö, à â îñòàëüíûõ êëåòêàõ ëåíòû ïîìåùàåì ïóñòîéñèìâîë 0. Åñëè n > 1 è òðåáóåòñÿ ïðåäñòàâèòü íà ëåíòå ìàøèíû Òüþðèíãà íàáîð ÷èñåë (m1 , .
. . , mn ), òî îáðàçóåì n ìàññèâîâ èç m1 +1, . . . , mn +1åäèíèö ñîîòâåòñòâåííî è ïîìåùàåì ìåæäó ñîñåäíèìè ìàññèâàìè ðàçäåëèòåëüíûé ñèìâîë 0. Òàêîå ïðåäñòàâëåíèå íàáîðà ÷èñåë (m1 , . . . , mn ) íàëåíòå ìàøèíû Òüþðèíãà (âêëþ÷àÿ ñëó÷àé n = 1) áóäåì íàçûâàòü(m1 , . . . , mn ).îñíîâ-íûì êîäîì íàáîðà67Ïåðåéäåì ñîáñòâåííî ê îïðåäåëåíèþ ôóíêöèè, âû÷èñëèìîé íà ìàøèíå Òüþðèíãà.
Ïóñòü f (x1 , . . . , xn ) ôóíêöèÿ (âîîáùå ãîâîðÿ, ÷àñòè÷íàÿ, ò.å. îïðåäåëåííàÿ íå äëÿ âñåõ çíà÷åíèé àðãóìåíòîâ) ñ àðãóìåíòàìè,ïðèíèìàþùèìè çíà÷åíèÿ èç N , è çíà÷åíèÿìè òàêæå â ìíîæåñòâå N , M ìàøèíà Òüþðèíãà ñ ëåíòî÷íûì àëôàâèòîì A, ñîäåðæàùèì ñèìâîëû0 è 1. Áóäåì ãîâîðèòü, ÷òîM, åñëè äëÿëþáîãî íàáîðà (m1 , . .
. , mn ) âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ.1. Åñëè çíà÷åíèå f (m1 , . . . , mn ) îïðåäåëåíî, òî ìàøèíà M, íà÷èíàÿðàáîòó â ñîñòîÿíèè q1 íà ïåðâîé åäèíèöå îñíîâíîãî êîäà íàáîðà (m1 , . . . ,mn ), ÷åðåç êîíå÷íîå ÷èñëî òàêòîâ îñòàíàâëèâàåòñÿ è â çàêëþ÷èòåëüíûéìîìåíò âðåìåíè íà ëåíòå ìàøèíû â îñíîâíîì êîäå ïðåäñòàâëåíî ÷èñëîf (m1 , . . . , mn ).2. Åñëè çíà÷åíèå f (m1 , . .
. , mn ) íå îïðåäåëåíî, òî, íà÷èíàÿ ðàáîòó èçòîé æå ïîçèöèè, ÷òî è â ï. 1, ìàøèíà M ëèáî íèêîãäà íå îñòàíàâëèâàåòñÿ, ëèáî îñòàíàâëèâàåòñÿ, íî ïðè ýòîì íà ëåíòå ìàøèíû íå ïðåäñòàâëåíîâ îñíîâîì êîäå íèêàêîå ÷èñëî èç N . äàëüíåéøåì ïî ÷èñòî òåõíè÷åñêèì ïðè÷èíàì íàì áóäåò óäîáíî èìåòüîïðåäåëåíèå âû÷èñëèìîé ôóíêöèè â áîëåå ñòàíäàðòèçîâàííîì âèäå. Èìåííî, ìû õîòèì, ÷òîáû â ï. 1 îïðåäåëåíèÿ ìàøèíà M â çàêëþ÷èòåëüíûéìîìåíò âðåìåíè îñòàíàâëèâàëàñü íà ïåðâîé åäèíèöå îñíîâíîãî êîäà ÷èñëà f (m1 , .
. . , mn ). À â ï. 2 îïðåäåëåíèÿ ìû õîòèì îòêàçàòüñÿ îò âòîðîéâîçìîæíîñòè, êîãäà íà ëåíòå ìàøèíû M îòñóòñòâóåò îñíîâíîé êîä ÷èñëà èç N . Òàêîå ìîäèôèöèðîâàííîå ïîíÿòèå âû÷èñëåíèÿ ôóíêöèè f íàìàøèíå M áóäåì íàçûâàòüM. Ñðàâíèòåëüíî íåñëîæíî ïîêàçàòü, ÷òî âòîðîå îïðåäåëåíèå âû÷èñëèìîñòè íå ñóæàåò êëàññà ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà.Îáðàòèìñÿ ê ïðèìåðàì âû÷èñëåíèÿ ôóíêöèé íà ìàøèíàõ Òüþðèíãà.ìàøèíàâû÷èñëÿåò ôóíêöèþ fïðàâèëüíûì âû÷èñëåíèåì ôóíêöèè f íà ìà-øèíåq10 1Sq01 1Lq1M4q10 1Sq01 0Rq1M5q1q201Sq01 0Rq2 1Sq0M6Íåòðóäíî ïîíÿòü, ÷òî ìàøèíà M4 ïðàâèëüíî âû÷èñëÿåò ôóíêöèþx + 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
