В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 8

Òîãäà âñå ñëîâà îäíîéäëèíû 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 . . ., â êîòîðûõ ãîëîâêà ïåðåõîäèò÷åðåç ðàçäåëÿþùèå òî÷êè âïðàâî. Ïåðåõîä ãîëîâêè ìàøèíû M ÷åðåçñîîòâåòñòâóþùèå ðàçäåëÿþùèå òî÷êè äåëèò ðàáîòó M íà êàæäîì èç ñëîâā1 |b̄2 , ā1 |ā2 è b̄1 |b̄2 íà ýòàïû. Ìàøèíà M íà ïåðâîì ýòàïå íà ñëîâå ā1 b̄2ðàáîòàåò òàê æå, êàê íà ïåðâîì ýòàïå íà ñëîâå ā1 ā2 .

Ïîýòîìó qj1 = qi1è ìàøèíà M íà âòîðîì ýòàïå íà ñëîâå ā1 b̄2 ðàáîòàåò òàê æå, êàê íàâòîðîì ýòàïå íà ñëîâå b̄1 b̄2 . Îòñþäà qj2 = qi2 è ìàøèíà M íà òðåòüåìýòàïå íà ñëîâå ā1 b̄2 ðàáîòàåò òàê æå, êàê íà òðåòüåì ýòàïå íà ñëîâå ā1 ā2 .Ïðîäîëæàÿ ýòî ðàññóæäåíèå, ìû ïîëó÷àåì óòâåðæäåíèå ëåììû.Îïðåäåëåíèå. Ïóñòü A = {0, 1} è ñëîâî ā = a1 a2 . . . an ∈ A∗ .Áóäåì ãîâîðèòü, ÷òî ñëîâî ā ñèììåòðè÷íî, åñëè a1 = an , a2 = an−1 è ò.ä.Ïóñòü ìàøèíà Òüþðèíãà M èìååò ëåíòî÷íûé àëôàâèò C è ìíîæåñòâîñîñòîÿíèé Q, ïðè÷åì A ⊆ C è q 0 ∈ Q, q 00 ∈ Q.

Áóäåì ãîâîðèòü, ÷òî Mðàñïîçíàåò ñèììåòðèþ, åñëè äëÿ ëþáîãî âõîäíîãî ñëîâà ā ∈ A∗ ìàøèíàM âñåãäà îñòàíàâëèâàåòñÿ è ïðè ýòîì íàõîäèòñÿ â ñîñòîÿíèè q 0 , åñëè āñèììåòðè÷íî, èëè q 00 , åñëè ā íå ñèììåòðè÷íî.Óòâåðæäåíèå. Ñóùåñòâóåò ìàøèíà ÒüþðèíãàM,êîòîðàÿ ðàñ-ïîçíàåò ñèììåòðèþ è äåëàåò ïðè ëþáîì âõîäíîì ñëîâå äëèíû2áîëåå cn øàãîâ, ãäå c íåêîòîðàÿ êîíñòàíòà.níåÄîñòàòî÷íî ïîñòðîèòü ìàøèíó M , êîòîðàÿ çàïîìèíàåò è ñòèðàåò ïåðâûé ñèìâîë, ïåðåãîíÿåò ãîëîâêó â êîíåö ñëîâàè ñðàâíèâàåò ñèìâîë â ïàìÿòè ñ ïîñëåäíèì ñèìâîëîì ñëîâà. Åñëè îíèíå ñîâïàäàþò, òî M ïåðåõîäèò â ñîñòîÿíèå q 00 è îñòàíàâëèâàåòñÿ. Åñëèñîâïàäàþò, òî îíà ñòèðàåò ïîñëåäíèé ñèìâîë, âîçâðàùàåòñÿ â íà÷àëîñëîâà è ïîâòîðÿåò ïðîöåññ.