В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 8
Текст из файла (страница 8)
. . , an ), ìàøèíà M â òîì ñëó÷àå, êîãäà f (a1 , a2 , . . . , an ) íå îïðåäåëåíî, îáÿçàòåëüíî ðàáîòàåò áåñêîíå÷íî äîëãî, à â òîì ñëó÷àå, êîãäàf (a1 , a2 , . . . , an ) = b, ìàøèíà îñòàíàâëèâàåòñÿ, íà ëåíòå îñòàåòñÿ êîä b èãîëîâêà ìàøèíû îáîçðåâàåò ñàìûé ëåâûé ñèìâîë |.34Óòâåðæäåíèå.
Åñëèf (x1 , x2 , . . . , xn ) âû÷èñëèìà, òî ñóùåñòâóåòM , êîòîðàÿ åå âû÷èñëÿåò ïðàâèëüíî.Äîêàçàòåëüñòâî ñì., íàïðèìåð, â [18].Îïðåäåëåíèå. Âñþäó îïðåäåëåííûå âû÷èñëèìûå ôóíêöèè ìû áóäåì íàçûâàòü îáùåðåêóðñèâíûìè ôóíêöèÿìè. (Îáû÷íî îáùåðåêóðñèâíûå ôóíêöèè îïðåäåëÿþò èíà÷å, íî äàííîå îïðåäåëåíèå ýêâèâàëåíòíîîáû÷íîìó; ñì., íàïðèìåð, [18]).Ôóíêöèÿ, âû÷èñëÿåìàÿ ìàøèíîé M , íå èçìåíèòñÿ, åñëè ïðîèçâîëüíî ïåðåèìåíîâàòü âñå ñèìâîëû ëåíòî÷íîãî àëôàâèòà, êðîìå | è Λ, èâñå ñîñòîÿíèÿ, îñòàâëÿÿ íà÷àëüíîå ñîñòîÿíèå íà÷àëüíûì (êîíå÷íî, ðàçíûå ñèìâîëû äîëæíû ïåðåèìåíîâûâàòüñÿ â ðàçíûå).
Ïîýòîìó ìû áóäåìñ÷èòàòü, ÷òî åñòü áåñêîíå÷íûé ôèêñèðîâàííûé àëôàâèò {c0 = Λ, c1 =|, c2 , c3 , . . .}, èç êîòîðîãî áåðåòñÿ ëåíòî÷íûé àëôàâèò ìàøèíû M , è áåñêîíå÷íûé ôèêñèðîâàííûé àëôàâèò {q0 , q1 , q2 , . . .}, èç êîòîðîãî áåðóòñÿñîñòîÿíèÿ ìàøèíû M . Áóäåì çàïèñûâàòü èíäåêñû â ñòðîêó ïîñëå c èëèq , ïðåäñòàâëÿÿ èõ â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ (íàïðèìåð, c6 = c110).Ïðîãðàììó ìàøèíû M áóäåì çàïèñûâàòü â âèäå ïîñëåäîâàòåëüíîñòèâñåõ åå êîìàíä ci qj −→ ck qr T , ðàçäåëåííûõ òî÷êîé ñ çàïÿòîé.
Òîãäàïðîãðàììà ëþáîé ìàøèíû áóäåò ïðåäñòàâëÿòü ñîáîé ñëîâî â àëôàâèòåD = {Λ, |, c, q, 0, 1, −→, R, L, S, ; }.ìàøèíà ÒüþðèíãàÒåîðåìà 4.1. Ñóùåñòâóåò àëãîðèòì íóìåðàöèè âñåõ ìàøèíÒüþðèíãà èç óêàçàííîãî âûøå ñåìåéñòâà òàêîé, ÷òî äëÿ âîññòàíîâëåíèÿ ïðîãðàììû ïî åå íîìåðó òàêæå ñóùåñòâóåò àëãîðèòì.Áóäåì ñ÷èòàòü, ÷òî ñèìâîëû àëôàâèòà D óïîðÿäî÷åíû (íàïðèìåð, òàê, êàê ýòî ñäåëàíî âûøå).
Òîãäà âñå ñëîâà îäíîéäëèíû k ìîæíî óïîðÿäî÷èòü ëåêñèãðàôè÷åñêè (êàê â ñëîâàðå). Áóäåìòåïåðü ïðîñìàòðèâàòü âñå ñëîâà â àëôàâèòå D â ñîîòâåòñòâèè ñ èõäëèíîé: ñíà÷àëà äëèíû 1, çàòåì äëèíû 2 è ò.ä. Ñëîâà îäíîé äëèíûk ïðîñìàòðèâàåì â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå. Äëÿ êàæäîãî ñëîâàïðèìåíÿåì àëãîðèòì, êîòîðûé ïðîâåðÿåò, ÿâëÿåòñÿ ëè ýòî ñëîâî ïðàâèëüíî ïîñòðîåííîé ïðîãðàììîé íåêîòîðîé äåòåðìèíèðîâàííîé ìàøèíûÒüþðèíãà. Åñëè äà, òî ïðèïèñûâàåì ýòîé ïðîãðàììå î÷åðåäíîé íîìåð(íà÷èíàÿ ñ 0). Ïðè ýòîì ëþáîé ìàøèíå Òüþðèíãà (èç ðàññìàòðèâàåìîãî ñåìåéñòâà) ïî åå ïðîãðàììå áóäåò (àëãîðèòìè÷íî) ñîïîñòàâëÿòüñÿíåêîòîðûé íîìåð. Òîò æå ïåðåáîð îñóùåñòâëÿåì, åñëè çàäàí íîìåð èòðåáóåòñÿ íàéòè ñîîòâåòñòâóþùóþ ýòîìó íîìåðó ïðîãðàììó.Äîêàçàòåëüñòâî.Çàôèêñèðóåì äàëåå íåêîòîðóþ íóìåðàöèþ ìàøèí Òüþðèíãà i ←→Mi , óäîâëåòâîðÿþùóþ òåîðåìå.
Òàê êàê ìàøèíà Mi âû÷èñëÿåò íåêîòîðóþ ôóíêöèþ f (x), òî ìû ïîëó÷àåì òàêæå íåêîòîðóþ íóìåðàöèþ âñåõ35âû÷èñëèìûõ ôóíêöèé îäíîé ïåðåìåííîé i −→ ϕi (x). Çàìåòèì, ÷òî ïðèýòîì ìîæåò áûòü ϕi (x) ≡ ϕj (x) ïðè i 6= j , ïîñêîëüêó ðàçíûå ìàøèíûÒüþðèíãà ìîãóò âû÷èñëÿòü îäíó è òó æå ôóíêöèþ f (x).Äîêàæåì òåïåðü òåîðåìû î òîì, ÷òî ñóùåñòâóþò ñêîëü óãîäíîñëîæíî âû÷èñëèìûå ôóíêöèè.Òåîðåìà 4.2. Äëÿ ëþáîé îáùåðåêóðñèâíîé ôóíêöèèñòâóåò îáùåðåêóðñèâíàÿ ôóíêöèÿf (x),T (x)ñóùå-ïðèíèìàþùàÿ òîëüêî 2 çíà÷å-Mi , âû÷èñëÿþùåéf (x), õîòÿ áû ïðè îäíîì x âûïîëíÿåòñÿ íåðàâåíñòâî ti (x) > T (x), ãäåti (x) âðåìÿ ðàáîòû ìàøèíû Mi íà âõîäå x (òî÷íåå, íà êîäå ÷èñëà x).Çàìå÷àíèå. Îòìåòèì, ÷òî ôóíêöèÿ T (x) ìîæåò ðàñòè î÷åíü áûñòðî.
Íàïðèìåð, ôóíêöèè g1 (n) = n, g2 (n) = nn , g3 (n) = ng2 (n) , . . .,gm+1 (n) = ngm (n) , . . . îáùåðåêóðñèâíû. Òàêæå îáùåðåêóðñèâíà è ôóíêöèÿ h(n) = gn (n), êîòîðàÿ ðàñòåò ñ àñòðîíîìè÷åñêîé ñêîðîñòüþ.++Äîêàçàòåëüñòâî. Äëÿ âñåõ i ∈ Z è x ∈ Z ïóñòü ti (x) îáîçíà÷àåòâðåìÿ ðàáîòû ìàøèíû ñ íîìåðîì i, åñëè âõîäîì ÿâëÿåòñÿ êîä ÷èñëà x(ti (x) ìîæåò áûòü è áåñêîíå÷íûì), è ïóñòü ϕi (x) îáîçíà÷àåò ôóíêöèþ,âû÷èñëÿåìóþ ìàøèíîé Mi . Îïðåäåëèì ôóíêöèþ f (x) ñëåäóþùèì îáðàçîì:(1, åñëè tx (x) 6 T (x) è ϕx (x) = 0,f (x) =0, èíà÷å.íèÿ 0 è 1 è òàêàÿ, ÷òî äëÿ ëþáîé ìàøèíû ÒüþðèíãàÓòâåðæäåíèå. Ôóíêöèÿf (x) âû÷èñëèìàÿ, à ñëåäîâàòåëüíî, îáùå-ðåêóðñèâíàÿ.Îïèøåì àëãîðèòì âû÷èñëåíèÿ f (x). Ïî çàäàííîìó x ∈ Z íàõîäèì ïðîãðàììó ìàøèíû Mx (ñì.
òåîðåìó 4.1). Âû÷èñëÿåìT (x) (òàê êàê T (x) îáùåðåêóðñèâíà, òî äëÿ ýòîãî ñóùåñòâóåò àëãîðèòì). Èìåÿ ïðîãðàììó ìàøèíû Mx , ìîäåëèðóåì åå ðàáîòó â òå÷åíèåT (x) òàêòîâ, âçÿâ â êà÷åñòâå âõîäíîãî ñëîâà êîä ÷èñëà x. Åñëè çà T (x)òàêòîâ ìàøèíà îñòàíîâèòñÿ è ðåçóëüòàòîì áóäåò êîä ÷èñëà 0, òî âûäàåìîòâåò 1, èíà÷å âûäàåì îòâåò 0. Ìîäåëèðóÿ ðàáîòó ìàøèíû, ìû ìîæåìðàáîòàòü òîëüêî ñ òîé ÷àñòüþ ëåíòû, íà êîòîðîé çàïèñûâàåòñÿ âõîäíîåñëîâî, à òàêæå êîòîðàÿ ïîñåùàåòñÿ ãîëîâêîé âî âðåìÿ ðàáîòû.
Òîãäà íàêàæäîì øàãå íàì äîñòàòî÷íî õðàíèòü ëèøü êîíå÷íûé êóñîê ëåíòû, ÷òîïîçâîëÿåò îïðåäåëèòü ñîäåðæèìîå ëåíòû è ïîñëå îñòàíîâà ìàøèíû. Ñëåäîâàòåëüíî, âåñü ïðîöåññ âû÷èñëåíèÿ f (x) àëãîðèòìè÷åí.  ñîîòâåòñòâèèñ òåçèñîì Òüþðèíãà ñóùåñòâóåò ìàøèíà Òüþðèíãà, êîòîðàÿ âû÷èñëÿåòf (x). Ìû ïðèìåì çäåñü ýòî óòâåðæäåíèå, õîòÿ äëÿ îïèñàííîé ôóíêöèèf (x) ìîæíî è ÿâíî ïîñòðîèòü âû÷èñëÿþùóþ åå ìàøèíó Òüþðèíãà (ïðàâäà, äîëãî è ãðîìîçäêî).Äîêàçàòåëüñòâî.+36Ïóñòü ìàøèíà Mi âû÷èñëÿåò f (x), òî åñòü f (x) = ϕi (x).  ÷àñòíîñòè ϕi (i) = f (i) è çíà÷èò îïðåäåëåíî.
Äîïóñòèì, ÷òî ti (i) 6 T (i). Òîãäà ïîîïðåäåëåíèþ f (x) ïîëó÷àåì: åñëè ϕi (i) = 0, òî f (i) = 1, à åñëè ϕi (i) 6= 0,òî f (i) = 0.  ëþáîì ñëó÷àå f (i) 6= ϕi (i) ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî(îò ïðîòèâíîãî) ti (i) > T (i). Òåîðåìà äîêàçàíà.Òåîðåìà 4.3. Äëÿ ëþáîé îáùåðåêóðñèâíîé ôóíêöèèñòâóåò îáùåðåêóðñèâíàÿ ôóíêöèÿf (x),ñóùå-ïðèíèìàþùàÿ òîëüêî 2 çíà÷å-íèÿ 0 è 1 è òàêàÿ, ÷òî äëÿ ëþáîé ìàøèíû Òüþðèíãàf (x),T (x)ñóùåñòâóåò áåñêîíå÷íîå ÷èñëî çíà÷åíèéx,Mi ,âû÷èñëÿþùåéäëÿ êîòîðûõ âûïîë-ti (x) > T (x).√ 2Äîêàçàòåëüñòâî.
Ïóñòü g(x)= x − (b xc) . Òîãäà ôóíêöèÿ g(x) âû÷èñëèìà è âñþäó îïðåäåëåíà (òî åñòü îáùåðåêóðñèâíà). Ïðè x = 0, 1, 2, 3, . . . ôóíêöèÿ g(x) ïðèíèìàåò çíà÷åíèÿ0, 0, 1, 2, 0, 1, 2, 3, 4, 0, 1, . . .. Ëåãêî äîêàçàòü, ÷òî ôóíêöèÿ g(x) ïðèíèìàåòêàæäîå çíà÷åíèå èç Z + áåñêîíå÷íîå ÷èñëî ðàç. Îïðåäåëèì ôóíêöèþ f (x)ñëåäóþùèì îáðàçîì:(1, åñëè tg(x) (x) 6 T (x) è ϕg(x) (x) = 0,f (x) =0, èíà÷å.íÿåòñÿ íåðàâåíñòâîÒîãäà ôóíêöèÿ f (x) îáùåðåêóðñèâíà (äîêàçûâàåòñÿ òàê æå, êàêâ ïðåäûäóùåé òåîðåìå). Ïóñòü ìàøèíà Mi âû÷èñëÿåò f (x), òî åñòüf (x) = ϕi (x). Ïóñòü j - ëþáîå ÷èñëî, òàêîå, ÷òî g(j) = i (òàêèõ jáåñêîíå÷íî ìíîãî). Äîïóñòèì, ÷òî ti (j) 6 T (j). Òîãäà ïî îïðåäåëåíèþf (x) ïîëó÷àåì: åñëè ϕi (j) = 0, òî f (j) = 1, à åñëè ϕi (j) 6= 0 , òîf (j) = 0.
 ëþáîì ñëó÷àå f (j) 6= ϕi (j) - ïðîòèâîðå÷èå. Ñëåäîâàòåëüíî,ti (j) > T (j). Òåîðåìà äîêàçàíà.Ñïðàâåäëèâî åùå áîëåå ñèëüíîå óòâåðæäåíèå, êîòîðîå ìû ïðèâåäåìáåç äîêàçàòåëüñòâà.Òåîðåìà 4.4. Äëÿ ëþáîé îáùåðåêóðñèâíîé ôóíêöèèñòâóåò îáùåðåêóðñèâíàÿ ôóíêöèÿf (x),ñóùå-ïðèíèìàþùàÿ òîëüêî 2 çíà÷å-íèÿ 0 è 1 è òàêàÿ, ÷òî äëÿ ëþáîé ìàøèíû Òüþðèíãàf (x),T (x)Mi ,âû÷èñëÿþùåéx, äëÿ êîòîðûõ ti (x) 6 T (x), êîíå÷íî.Òåîðåìû 4.2-4.4 ïîêàçûâàþò, ÷òî ñóùåñòâóþò ñêîëü óãîäíî ñëîæíîâû÷èñëèìûå îáùåðåêóðñèâíûå ôóíêöèè ñ äâóìÿ çíà÷åíèÿìè (èëè, ÷òîýêâèâàëåíòíî, ñêîëü óãîäíî ñëîæíî ðàñïîçíàâàåìûå ÿçûêè).
Âîçíèêàåòâîïðîñ: à êàêîé âîîáùå ìîæåò áûòü ñëîæíîñòü çàäà÷ (ÿçûêîâ)? Ñóùåñòâåííûé îòâåò íà ýòîò âîïðîñ äàåò ñëåäóþùàÿ òåîðåìà, êîòîðóþ ìûïðèâîäèì áåç äîêàçàòåëüñòâà.Òåîðåìà 4.5. Ïóñòü îáùåðåêóðñèâíûå ôóíêöèè t(n) è T (n) òàìíîæåñòâî òåõ37T (n)t(n) log2 t(n) → ∞ ïðè n → ∞. Òîãäà ñóùåñòâóåò ÿçûê L,êîòîðûé ðàñïîçíàåòñÿ íåêîòîðîé ìàøèíîé Òüþðèíãà ñ ÷èñëîì øàãîâêîâû, ÷òîT (n) (äëÿ âñåõ âõîäíûõ ñëîâ ëþáîé äëèíû n) è íå ðàñïîçíàåòñÿíèêàêîé ìàøèíîé Òüþðèíãà ñ ÷èñëîì øàãîâ t(n).Ýòà òåîðåìà ïîêàçûâàåò, ÷òî âîçìîæíûå ôóíêöèè ñëîæíîñòè ÿçûêîâ îáðàçóþò äîâîëüíî ïëîòíîå ìíîæåñòâî.
Ìîæíî ëè ïîëó÷èòü ðåçóëüòàò î áîëüøåé ïëîòíîñòè, â îáùåì ñëó÷àå íåèçâåñòíî. Îäíàêî äëÿ îäíîãîâàæíîãî èíòåðâàëà ìû ïîëó÷èì îòðèöàòåëüíûé îòâåò â ï. 4.4. À èìåííî,ìû ïîêàæåì, ÷òî íå ñóùåñòâóåò ÿçûêîâ ñî ñëîæíîñòüþ ðàñïîçíàâàíèÿ(íà ìàøèíå Òüþðèíãà) ïî ïîðÿäêó ìåæäó n è n log n.íå áîëåå4.3. Ìåòîä ñëåäîâ. Ðàñïîçíàâàíèå ñèììåòðèèÕîòÿ â ïðåäûäóùåì ïàðàãðàôå ïîêàçàíî, ÷òî ñóùåñòâóþò ñêîëüóãîäíî ñëîæíûå çàäà÷è, ïîëó÷èòü âûñîêóþ íèæíþþ îöåíêó ñëîæíîñòèäëÿ êîíêðåòíîé çàäà÷è î÷åíü òÿæåëî. Îäèí èç ìåòîäîâ äëÿ ïîëó÷åíèÿíèæíèõ îöåíîê ñëîæíîñòè ðåøåíèÿ çàäà÷ íà ìàøèíàõ Òüþðèíãà, íàçûâàåìûé ìåòîäîì ñëåäîâ, ïðåäëîæèë ß. Ì.
Áàðçäèíü, êîòîðûé âïåðâûåïðèìåíèë ýòîò ìåòîä äëÿ îöåíêè ñëîæíîñòè ðàñïîçíàâàíèÿ ñèììåòðèèíà ìàøèíå Òüþðèíãà [5].Îïðåäåëåíèå. Ðàññìîòðèì òî÷êó íà ëåíòå ìàøèíû Òüþðèíãàìåæäó ÿ÷åéêàìè ñ íîìåðàìè i è i+1. Ñëåäîì â ýòîé òî÷êå ïðè ðàáîòå ìàøèíû íà íåêîòîðîì âõîäíîì ñëîâå áóäåì íàçûâàòü ïîñëåäîâàòåëüíîñòüâñåõ ñîñòîÿíèé, â êîòîðûå ïåðåõîäèò ìàøèíà, êîãäà åå ãîëîâêà ñìåùàåòñÿèç ÿ÷åéêè i â ÿ÷åéêó i + 1 èëè íàîáîðîò (òî åñòü ïðîõîäèò íàä ýòîéòî÷êîé). Ïóñòü ā = ā1 ā2 âõîäíîå ñëîâî. Òîãäà ÷åðåç ξM (ā1 |ā2 ) áóäåìîáîçíà÷àòü ñëåä ìàøèíû M ïðè ðàáîòå íà ñëîâå ā1 ā2 â òî÷êå, ðàçäåëÿþùåé ā1 è ā2 (ñ÷èòàåì, ÷òî íà÷àëüíàÿ êîíôèãóðàöèÿ ñòàíäàðòíàÿ).Îñíîâíàÿ èäåÿ Áàðçäèíÿ ñîñòîèò â èñïîëüçîâàíèè ñëåäóþùåãîóòâåðæäåíèÿ.ξM (ā1 |ā2 ) = ξM (b̄1 |b̄2 ).ā1 b̄2 ìàøèíà M ñëåâà îò òî÷êè,Ëåììà 4.1. Ïóñòüâõîäíîì ñëîâåÒîãäà ïðè ðàáîòå íàðàçäåëÿþùåéā1èb̄2ðàáîòàåò òàê æå, êàê íà ñîîòâåòñòâóþùåé ÷àñòè ïðè âõîäíîì ñëîâåā1 ā2 ,à ñïðàâà òàê æå, êàê íà ñîîòâåòñòâóþùåé ÷àñòè ïðè âõîäíîìξM (ā1 |b̄2 ) = ξM (ā1 |ā2 ) = ξM (b̄1 |b̄2 ).Äîêàçàòåëüñòâî.
Ïóñòü ξM (ā1 |ā2 ) = ξM (b̄1 |b̄2 ) = qi1 qi2 . . . qin , àξM (ā1 |b̄2 ) = qj1 qj2 . . . qjm . Çàìåòèì, ÷òî ðàáîòà ìàøèíû M íà ñëîâå ā1 b̄2ñëåâà îò ðàçäåëÿþùåé òî÷êè îäíîçíà÷íî îïðåäåëÿåòñÿ ñëîâîì ā1 è ñîñòîÿíèÿìè qj2 qj4 qj6 . . ., â êîòîðûõ ãîëîâêà ïåðåõîäèò ÷åðåç ðàçäåëÿþùèåñëîâåb̄1 b̄2 ,ïðè÷åì38òî÷êè âëåâî, à ðàáîòà ñïðàâà îò ðàçäåëÿþùåé òî÷êè îäíîçíà÷íî îïðåäåëÿåòñÿ ñëîâîì b̄2 è ñîñòîÿíèÿìè qj1 qj3 qj5 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
