1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 12

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 12)

. . ,xk , 0, . . .Åãî ìîæíî çàïèñàòü â ýêâèâàëåíòíîì âèäå, êàêÏðîãð (e) & seq (y) & stop (e, hx1 , . . . ,xk i , lh (y)−̇1)& ∀i < lh (y) ((y)i = rg (e, hx1 , . . . ,xk i , i)).Îòñþäà ÿñíî, ÷òî îòíîøåíèå Tk ðåêóðñèâíî.Âñïîìíèâ îïðåäåëåíèå ôóíêöèè APk , ìû âèäèì, ÷òî åñëè e êîäïðîãðàììû P , òî âûïîëíåíî ðàâåíñòâîAPk (x1 , . . . ,xk ) ' U (µy Tk (e, x1 , . . . ,xk , y)).Èç íåãî ñëåäóåò âàæíûé âûâîä: ëþáàÿ âû÷èñëèìàÿ íà ìàøèíå ؼíôèëäà ôóíêöèÿ ÷àñòè÷íî ðåêóðñèâíà, òî åñòü ìû äîêàçàëè òåîðåìó 3.2.5.Ñëåäñòâèå 3.4.3 (Òåîðåìà Êëèíè î íîðìàëüíîé ôîðìå) Äëÿ âñÿ-êîé ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè ψ(x1 , .

. . ,xk ) ñóùåñòâóåò íàòóðàëüíîå ÷èñëî e òàêîå, ÷òîψ(x1 , . . . ,xk ) ' U (µy Tk (e, x1 , . . . ,xk , y)).68Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÇäåñü ïîèñê y ïðè ïîìîùè µîïåðàòîðà ìîæíî óïîäîáèòü øàãàì âû÷èñëåíèÿ, à ÷èñëî e èãðàåò ðîëü ïðîãðàììû (äà ýòî è åñòü êîä ïðîãðàììû). Ñàìà ôóíêöèÿ U (µy Tk (e, x1 , . . .

,xk , y)) ìîæåò ìûñëèòüñÿ, êàêóíèâåðñàëüíîå âû÷èñëèòåëüíîå óñòðîéñòâî, íåêèé êîìïüþòåð, â êîòîðûéïåðåä íà÷àëîì ðàáîòû ââîäèòñÿ ïðîãðàììà â âèäå íàòóðàëüíîãî ÷èñëàe.Ñëåäñòâèå 3.4.4 (Òåîðåìà îá óíèâåðñàëüíîé ôóíêöèè) Äëÿ âñÿêîãî ÷èñëà àðãóìåíòîâ k = 1, 2, . . . ñóùåñòâóåò ÷àñòè÷íî ðåêóðñèâíàÿôóíêöèÿ ϕ(e, x1 , . . . ,xk ) òàêàÿ, ÷òî äëÿ âñÿêîé ÷àñòè÷íî ðåêóðñèâíîéôóíêöèè ψ(x1 , . . .

,xk ) ñóùåñòâóåò íàòóðàëüíîå ÷èñëî e òàêîå, ÷òîψ(x1 , . . . ,xk ) ' ϕ(e, x1 , . . . ,xk ).Äîêàçàòåëüñòâî. Ìîæíî âçÿòü ϕ(e, x1 , . . . ,xk ) ' U (µy Tk (e, x1 , . . . ,xk , y)).¤Ââåäåì îáîçíà÷åíèå:{e}(x1 , . . . ,xk ) ' U (µy Tk (e, x1 , . . . ,xk , y)).Íà ñàìîì äåëå {e}(x1 , . . . ,xk ) ýòî ïðîñòî ðåçóëüòàò ïðèìåíåíèÿ ìàøèíû ؼíôèëäà ñ íîìåðîì e ê àðãóìåíòàì x1 , . . . ,xk , â ñëó÷àå, êîãäà e íîìåð íåêîòîðîé ìàøèíû ؼíôèëäà, â ïðîòèâíîì ñëó÷àå ýòî çíà÷åíèåíå îïðåäåëåíî.Ïóñòü òàêæå æe îáîçíà÷àåò óíàðíóþ ôóíêöèþ, âû÷èñëÿåìîé ìàøèíîé ؼíôèëäà ñ íîìåðîì e â ñëó÷àå, êîãäà e ýòî íîìåð íåêîòîðîéìàøèíû, è íèãäå íå îïðåäåëåííóþ ôóíêöèè â ïðîòèâíîì ñëó÷àå.

Èìååì: æe (x) ' {e}(x), äëÿ âñåõ e ∈ N.Òåîðåìà 3.4.5 (Òåîðåìà î ïàðàìåòðèçàöèè) Äëÿ ëþáîé ÷àñòè÷íî ðåêóðñèâíîé ôóíêöèè F (y1 , . . . ,ym , x1 . . . xn ) ñóùåñòâóåò ðàçíîçíà÷íàÿ ðåêóðñèâíàÿ ôóíêöèÿ s(y1 , . . . ,ym ) òàêàÿ, ÷òîF (y1 , . . . ,ym , x1 . . . xn ) ' {s(y1 , . . . ,ym )}(x1 . . . xn ).Ýòó òåîðåìó òàêæå íàçûâàþò smnòåîðåìîé, âèäèìî ïî îáîçíà÷åíèþôóíêöèè s, èñïîëüçîâàííîìó â ïåðâûõ ðàáîòàõ.Ïðåæäå ÷åì äîêàçûâàòü ýòó òåîðåìó, ïîïûòàåìñÿ ïîíÿòü åå ñ íåôîðìàëüíîé òî÷êè çðåíèÿ. Îíà óòâåðæäàåò, ÷òî, ðàñïîëàãàÿ ïðîãðàììîé (ââèäå íîìåðà) äëÿ âû÷èñëåíèÿ íåêîòîðîé ôóíêöèè îò âõîäíûõ ïåðåìåííûõ y1 , .

. . ,ym , x1 . . . xn , ìû ìîæåì äëÿ ôèêñèðîâàííûõ y1 , . . . ,ym , (÷òîáû3.4. Êîäèðîâàíèå ìàøèí ؼíôèëäà69íå ââîäèòü èõ êàæäûé ðàç çàíîâî) ïðåîáðàçîâàòü åå â ïðîãðàììó (òî÷íåå,â åå íîìåð) äëÿ âû÷èñëåíèÿ ôóíêöèè H(x1 . . . xn ) ' F (y1 , .

. . ,ym , x1 . . . xn )îò çíà÷åíèé îñòàâøèõñÿ ïåðåìåííûõ x1 . . . xn , ïðè÷åì ýòî ïðåîáðàçîâàíèå ìîæíî îñóùåñòâëÿòü åäèíîé äëÿ âñåõ y1 , . . . ,ym àëãîðèòìè÷åñêîéïðîöåäóðîé. Èìåííî ýòó àëãîðèòìè÷åñêóþ ïðîöåäóðó ìû áóäåì ñòðîèòüâ äîêàçàòåëüñòâå ýòîé òåîðåìû. Ïðè ýòîì îêàæåòñÿ, ÷òî ïî çíà÷åíèþêîäà íîâîé ïðîãðàììû âñåãäà ìîæíî áóäåò âîññòàíîâèòü çíà÷åíèÿ ïåðåìåííûõ y1 , . .

. ,ym (ðàçíîçíà÷íîñòü ôóíêöèè s).Äîêàçàòåëüñòâî. Ðàññìîòðèì ôóíêöèþF 0 (x1 . . . xn , y1 , . . . ,ym ) ' F (y1 , . . . ,ym , x1 . . . xn ).Îíà òîæå ÷àñòè÷íî ðåêóðñèâíà, òàê êàêF 0 (x1 . . . xn , y1 , . . . ,ym ) 'm+nm+nF (In+1(x̄, ȳ), . . . ,In+m(x̄, ȳ), I1m+n (x̄, ȳ), . . . ,Inm+n (x̄, ȳ)).Ïóñòü ïðîãðàììà P ñ íîìåðîì e âû÷èñëÿåò F 0 (x1 . . . xn , y1 , . . . ,ym ). Åñëèìû çàôèêñèðóåì y1 , .

. . ,ym , òî çíà÷åíèå ôóíêöèè îò îñòàâøèõñÿ àðãóìåíòîâ x1 . . . xn áóäåò âû÷èñëÿòüñÿ ñëåäóþùåé ìàêðîïðîãðàììîé (íîìåðà êîìàíä îïóùåíû):INC n + 1 ...y ðàç 1INC n + 1...INC n + m ...y ðàç mINC n + mP∗Íàì îñòàëàñü ðóòèííàÿ ðàáîòà ïî ïðåîáðàçîâàíèþ äàííîé ïðîãðàììû âýêâèâàëåíòíóþ åé ïðîãðàììó Py1 ,...,yk áåç ìàêðîñîâ è àêêóðàòíîìó âû÷èñëåíèþ åå íîìåðà ïî y1 , . . .

,ym . Ïðåäïîëîæèì, ÷òî ìû óæå äîêàçàëè,÷òî êîä k é êîìàíäû âû÷èñëÿåòñÿ ñ ïîìîùüþ íåêîòîðîé ðåêóðñèâíîéôóíêöèè ïî k è ȳ = y1 , . . . ,yk , òî åñòü äîêàçàëè, íàïðèìåð, ðåêóðñèâíîñòü ôóíêöèè êîä k é êîìàíäû Pȳ , åñëè â Pȳ åñòüêîìàíäà íîìåðîì kG(k, ȳ) =0â îñòàëüíûõ ñëó÷àÿõ.70Ãëàâà 3.

Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàÒîãäà åñëè ` ÷èñëî êîìàíä ïðîãðàììû P , òî ìîæíî îïðåäåëèòüs(ȳ) = µz (seq (z) & lh (z) = ` + y1 + · · · + ym & ∀i < lh (z)((z)i = G(i, ȳ)).Íåôîðìàëüíî ìîæíî çàïèñàòü:êîä (INC n + 1), åñëè 0 6 k < y1êîä (INC n + 2), åñëè y1 6 k < y1 + y2...êîä (INC n + m), åñëè y1 + · · · + ym−1 6 k < y1 + · · · + ym êîä (DEC I,j + y1 + · · · + ym ), åñëèG(k, ȳ) =y1 + · · · + ym 6 k < y1 + · · · ym + ` èk −̇(y1 + · · · + ym )ÿ êîìàíäà P åñòü DEC I,jêîä(INC J), åñëèy1 + · · · + ym 6 k < y1 + · · · ym + ` èk −̇(y1 + · · · + ym )ÿ êîìàíäà P åñòü INC J0, â îñòàëüíûõ ñëó÷àÿõ.Ââåäåì îáîçíà÷åíèÿ: Y (ȳ) = y1 + · · · + ym , A(k, ȳ) = k −̇Y (ȳ),R(k, ȳ) ⇔ Y (ȳ) 6 k < Y (ȳ) + `.Òåïåðü îïðåäåëåíèå äëÿ G(k, ȳ) çàïèøåòñÿ òàê:h0, n + 1i , åñëè 0 6 k < y1h0, n + 2i , åñëè y1 6 y1 + y2 ... h0, n + mi , åñëè y1 + · · · + ym−1 6 k < y1 + · · · + ym­®G(k, ȳ) =1, ((e)A(k,ȳ) )1 , ((e)A(k,ȳ) )2 + Y (ȳ) , åñëè ­ R(k, ȳ) è ((e)® A(k,ȳ) )0 = 10,((e))A(k,ȳ) 1 , åñëèR(k, ȳ) è ((e)A(k,ȳ) )0 = 00, â îñòàëüíûõ ñëó÷àÿõ,îòêóäà è ñëåäóåò ðåêóðñèâíîñòü ôóíêöèè G.

Òåîðåìà äîêàçàíà.3.5 Ìàøèíû ÒüþðèíãàÌàøèíû Òüþðèíãà ÿâëÿåòñÿ èñòîðè÷åñêè îäíîé èç ñàìûõ ïåðâûõ è, íàðÿäó ñ ÷àñòè÷íî ðåêóðñèâíûìè ôóíêöèÿìè, îäíîé èç ñàìûõ ïîïóëÿðíûõôîðìàëèçàöèé äëÿ ïîíÿòèÿ âû÷èñëèìîé ôóíêöèè.Ìàøèíà Òüþðèíãà ñîñòîèò èç3.5. Ìàøèíû Òüþðèíãà71êîíå÷íîé ëåíòû, ñîñòîÿùåé èç ïîñëåäîâàòåëüíî ðàñïîëîæåííûõ îäè-íàêîâûõ ÿ÷ååê, â êàæäîé èç êîòîðûõ çàïèñàí íåêîòîðûé ñèìâîë èçíåïóñòîãî êîíå÷íîãî âíåøíåãî àëôàâèòà A = {a0 , . .

. , am } (îáû÷íî ñ÷èòàåòñÿ, ÷òî a0 = 0). Ýòà ëåíòà êîíå÷íà â êàæäûé ìîìåíòâðåìåíè, íî îíà ìîæåò ðàñøèðÿòñÿ ïóòåì äîáàâëåíèÿ íîâûõ ÿ÷ååêñïðàâà è ñëåâà.ïîäâèæíîãî ñ÷èòûâàþùåçàïèñûâàþùåãî óñòðîéñòâà, äëÿ êðàòêîñòè íàçûâàåàìîãî óêàçàòåëåì, êîòîðûé â êàæäûé ìîìåíò âðåìåíè íàõîäèòñÿ íàä êàêîéëèáî ÿ÷åéêîé ëåíòû, ìîæåò ñäâèãàòüñÿâïðàâî è âëåâî, ìîæåò ñ÷èòûâàòü çàïèñàííûå íà ëåíòå ñèìâîëûâíåøíåãî àëôàâèòà è çàìåíÿòü èõ íà íîâûå ñèìâîëû.Ìàøèíà Òüþðèíãà â êàæäûé ìîìåíò âðåìåíè íàõîäèòñÿ â îäíîì èçâíóòðåííèõ ñîñòîÿíèé, îáîçíà÷àåìûõ ñèìâîëàìè êîíå÷íîãî âíóòðåííåãî àëôàâèòà Q = {q0 , q1 , . .

. , qn }. Ìû ïðåäïîëàãàåì, ÷òî Q ∩A = ∅ è n > 0.ïðîãðàììû, êîòîðàÿ ñîñòîèò èç êîíå÷íîãî íàáîðà êîìàíä âèäàqi aj → qk al S, qi , qk ∈ Q, aj , al ∈ A, S ∈ {Λ, R, L},ïðè÷åì äëÿ êàæäîé ïàðû qi aj â ïðîãðàììå ñóùåñòâóåò íå áîëååîäíîé êîìàíäû âèäà qi aj → qk al S .Íà ðèñóíêå íèæå ïîêàçàíî ñõåìàòè÷åñêîå èçîáðàæåíèå ìàøèíû Òüþðèíãà.q ¡@@ j¡...aialak...Ðèñ.

3.1: Ìàøèíà ÒüþðèíãàÌàøèíà Òüþðèíãà ðàáîòàåò ïî øàãàì. Îïèøåì øàã ìàøèíû. Åñëèìàøèíà íàõîäèòñÿ âî âíóòðåííåì ñîñòîÿíèè qi , è åå óêàçàòåëü îáîçðåâàåòÿ÷åéêó, â êîòîðîé çàïèñàí ñèìâîë aj , òî â ïðîãðàììå èùåòñÿ êîìàíäàâèäà qi aj → qk al S , è åñëè îíà åñòü â ïðîãðàììå, òî îíà èñïîëíÿåòñÿ.Èñïîëíåíèå êîìàíäû ñîñòîèò â ñëåäóþùåì72Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìà1. Ìàøèíà ïåðåõîäèò â ñîñòîÿíèå qk .2. Ñèìâîë aj â îáîçðåâàåìîé ÿ÷åéêå ëåíòû çàìåíÿåòñÿ íà ñèìâîë al .3. åñëè S = R, òî óêàçàòåëü ñäâèãàåòñÿ íà îäíó ïîçèöèþ âïðàâî. Åñëèâ ðåçóëüòàòå ýòîãî óêàçàòåëü âûõîäèò çà ïðåäåëû ëåíòû, òî ìàøèíàäîñòðàèâàåò íîâóþ ÿ÷åéêó òàê, ÷òîáû óêàçàòåëü íàõîäèëñÿ íàä íåéè çàïèñûâàåò â íåå ñèìâîë a0 .4. åñëè S = L, òî óêàçàòåëü ñäâèãàåòñÿ íà îäíó ïîçèöèþ âëåâî.

Åñëè âðåçóëüòàòå ýòîãî óêàçàòåëü âûõîäèò çà ïðåäåëû ëåíòû, òî ìàøèíàäîñòðàèâàåò íîâóþ ÿ÷åéêó òàê, ÷òîáû óêàçàòåëü íàõîäèëñÿ íàä íåéè çàïèñûâàåò â íåå ñèìâîë a0 .Åñëè êîìàíäà âèäà qi aj → qk al S â ïðîãðàììå îòñóòñòâóåò, òî ìàøèíàîñòàíàâëèâàåòñÿ.

Ïðè ýòîì ãîâîðÿò, ÷òî ïðîèçîøëà íåïðàâèëüíàÿ îñòàíîâêà ìàøèíû.Åñëè ïîñëå èñïîëíåíèÿ øàãà ìàøèíà îêàçàëàñü âî âíóòðåííåì ñîñòîÿíèè q0 , òî ìàøèíà îñòàíàâëèâàåòñÿ, è äàëüíåéøåå èñïîëíåíèå êîìàíäïðåêðàùàåòñÿ. Ïðè ýòîì ãîâîðÿò, ÷òî ïðîèçîøëà ïðàâèëüíàÿ îñòàíîâêàìàøèíû.Âî âñåõ îñòàëüíûõ ñëó÷àÿõ ìàøèíà ïîñëå ýòîãî èñïîëíÿåò ñëåäóþùèé øàã.Ââèäó îñîáîé ðîëè, êîòîðóþ èãðàþò ñîñòîÿíèÿ q1 è q0 , ýòè ñîñòîÿíèÿíàçûâàþòñÿ ñîîòâåòñòâåííî íà÷àëüíûì ñîñòîÿíèåì è çàêëþ÷èòåëüíûìñîñòîÿíèåì.Ïðåäñòàâëåíèå ñëîâàìè êîíôèãóðàöèé Ìàøèíû Òüþðèíãà.  êàæäûéìîìåíò âðåìåíè ìàøèíà Òüþðèíãà íàõîäèòñÿ â íåêîòîðîì ñîñòîÿíèè qè åå ãîëîâêà îáîçðåâàåò íåêîòîðóþ j þ ÿ÷åéêó ëåíòû, íà êîòîðîé çàïèñàíû ïî ïîðÿäêó ñèìâîëû c1 , .

. . , cj , . . . , cp . Ýòó êàðòèíó ìû áóäåì íàçûâàòü êîíôèãóðàöèåé ìàøèíû Òüþðèíãà. Òàêóþ êîíôèãóðàöèþ ìîæíîçàïèñàòü ñëîâîì c1 . . . qcj . . . cp . Ââèäó òîãî, ÷òî Q ∩ A = ∅, ýòî ñëîâîîäíîçíà÷íî îïðåäåëÿåòñÿ ïî êîíôèãóðàöèè, è ñàìà êîíôèãóðàöèÿ îäíîçíà÷íî âîññòàíàâëèâàåòñÿ ïî äàííîìó ñëîâó. Ïîýòîìó ìû áóäåì îòîæäåñòâëÿòü êîíôèãóðàöèè è ñëîâà, èõ ïðåäñòàâëÿþùèå.Åñëè ìàøèíà Òüþðèíãà M ïåðåõîäèò çà îäèí øàã èç êîíôèãóðàöèè,çàïèñûâàåìîé ñëîâîì v â êîíôèãóðàöèþ, çàïèñûâàåìóþ ñëîâîì w, ìûáóäåì çàïèñûâàòü ýòî êàê v ⇒M w.

Åñëè æå îíà ïåðåõîäèò çà êîíå÷íîå÷èñëî øàãîâ èç êîíôèãóðàöèè, çàïèñûâàåìîé ñëîâîì v â êîíôèãóðàöèþ,çàïèñûâàåìóþ ñëîâîì w, è ïðè ýòîì íå ïðîèñõîäèò äîñòðàèâàíèÿ ÿ÷ååê3.5. Ìàøèíû Òüþðèíãà73ñëåâà, ìû áóäåì çàïèñûâàòü ýòî êàê v VM w. Åñëè ÿñíî, î êàêîé ìàøèíåèäåò ðå÷ü, òî èíäåêñ M ìîæåò îïóñêàòüñÿ.Ïðèìåð. Ðàññìîòðèì ìàøèíó Òüþðèíãà M ñ âíåøíèì àëôàâèòîì{0, 1} (ïðåäïîëàãàåòñÿ a0 = 0), âíóòðåííèì àëôàâèòîì {q0 , q1 , q2 , q3 } èïðîãðàììîéq1 0 → q2 0R q3 1 → q3 0Lq2 1 → q2 1R q3 0 → q0 0Λq2 0 → q3 0LÍåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òîq1 011 ⇒M 0q2 11 ⇒M 01q2 1 ⇒M 011q2 0 (âîçíèêëà íîâàÿ ÿ÷åéêà) ⇒M⇒M 01q3 10 ⇒M 0q3 100 ⇒M q3 0000 ⇒M q0 0000.Ìîæíî òàêæå çàïèñàòü q1 011 VM q0 0000. Ìîæíî ïîêàçàòü, ÷òî äëÿ âñåõíàòóðàëüíûõ n âûïîëíåíî q1 01n VM q0 0n+2 .Îïðåäåëåíèå 3.5.1 Ïóñòü f ÷àñòè÷íàÿ ôóíêöèÿ èç Nk â N. Ìûáóäåì ãîâîðèòü, ÷òî ìàøèíà Òüþðèíãà M ïðàâèëüíî âû÷èñëÿåò ýòóôóíêöèþ, åñëè1.

Характеристики

Список файлов лекций