1610906281-2dcf0fef1ce626ab2dbf8dbda8c94e1a (Машины Тьюринга и др)

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

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

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

Åñëèìàøèíà íàõîäèòñÿ âî âíóòðåííåì ñîñòîÿíèèÿ÷åéêó, â êîòîðîé çàïèñàí ñèìâîëâèäàqi aj → qk al S ,aj ,qi , è å¼ óêàçàòåëü îáîçðåâàåòòî â ïðîãðàììå èùåòñÿ êîìàíäàè åñëè îíà åñòü â ïðîãðàììå, òî îíà èñïîëíÿåòñÿ.Èñïîëíåíèå êîìàíäû ñîñòîèò â ñëåäóþùåì1. Ìàøèíà ïåðåõîäèò â ñîñòîÿíèå2. Ñèìâîëajqk .â îáîçðåâàåìîé ÿ÷åéêå ëåíòû çàìåíÿåòñÿ íà ñèìâîë1al .q@@ j...aialak...Ðèñ. 1: Ìàøèíà Òüþðèíãà3.

åñëèS = R, òî óêàçàòåëü ñäâèãàåòñÿ íà îäíó ïîçèöèþ âïðàâî. Åñëèâ ðåçóëüòàòå ýòîãî óêàçàòåëü âûõîäèò çà ïðåäåëû ëåíòû, òî ìàøèíàäîñòðàèâàåò íîâóþ ÿ÷åéêó òàê, ÷òîáû óêàçàòåëü íàõîäèëñÿ íàä íåéè çàïèñûâàåò â íå¼ ñèìâîë4. åñëèa0 .S = L, òî óêàçàòåëü ñäâèãàåòñÿ íà îäíó ïîçèöèþ âëåâî. Åñëè âðåçóëüòàòå ýòîãî óêàçàòåëü âûõîäèò çà ïðåäåëû ëåíòû, òî ìàøèíàäîñòðàèâàåò íîâóþ ÿ÷åéêó òàê, ÷òîáû óêàçàòåëü íàõîäèëñÿ íàä íåéè çàïèñûâàåò â íå¼ ñèìâîëÅñëè êîìàíäà âèäàa0 .qi aj → qk al Sâ ïðîãðàììå îòñóòñòâóåò, òî ìàøèíàîñòàíàâëèâàåòñÿ. Ïðè ýòîì ãîâîðÿò, ÷òî ïðîèçîøëàíîâêà ìàøèíû.íåïðàâèëüíàÿ îñòà-Åñëè ïîñëå èñïîëíåíèÿ øàãà ìàøèíà îêàçàëàñü âî âíóòðåííåì ñîñòîÿíèèq0 ,òî ìàøèíà îñòàíàâëèâàåòñÿ, è äàëüíåéøåå èñïîëíåíèå êîìàíäïðåêðàùàåòñÿ.

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

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

Åñëè ÿñíî, î êàêîé ìàøèíåèäåò ðå÷ü, òî èíäåêñ M ìîæåò îïóñêàòüñÿ.Ïðèìåð.{0, 1}Ðàññìîòðèì ìàøèíó Òüþðèíãà(ïðåäïîëàãàåòñÿa0 = 0),Mñ âíåøíèì àëôàâèòîìâíóòðåííèì àëôàâèòîì{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.Ìîæíî òàêæå çàïèñàòüíàòóðàëüíûõnq1 011 VM q0 0000. Ìîæíî ïîêàçàòü, ÷òî äëÿ âñåõq1 01n VM q0 0n+2 .âûïîëíåíîÏóñòü f ÷àñòè÷íàÿ ôóíêöèÿ èç Nk â N.

Ìû áóäåìãîâîðèòü, ÷òî ìàøèíà Òüþðèíãà Mâû÷èñëÿåò ýòó ôóíêöèþ, åñëè1. äëÿ ëþáîãî íàáîðà x1, . . . , xk ∈ N òàêîãî, ÷òî çíà÷åíèå f (x1, . . . , xk )îïðåäåëåíî, âûïîëíÿåòñÿÎïðåäåëåíèå 1.1ïðàâèëüíî0q1 1x1 +1 0 . . . 01xk +1 0 VM 0q0 1f (x1 ,...,xk )+1 0 . . . 0.2. äëÿ ëþáîãî íàáîðà x1, . . . , xk ∈ N òàêîãî, ÷òî çíà÷åíèå f (x1, . . .

, xk )íå îïðåäåëåíî, ìàøèíà Òüþðèíãà M , íà÷àâ ñâîþ ðàáîòó ñ êîíôèãóðàöèè 0q11x +10 . . . 01x +10, íèêîãäà íå îñòàíîâèòñÿ ïðàâèëüíî(òî åñòü, ëèáî ïðîèçîéäåò íåïðàâèëüíàÿ îñòàíîâêà M ëèáî Mâîîáùå íèêîãäà íå îñòàíîâèòñÿ) è ïðè ýòîì íå äîñòðàèâàåò ÿ÷ååê ñëåâà.Ìû ãîâîðèì, ÷òî ÷àñòè÷íàÿ ôóíêöèÿíà ìàøèíåÒüþðèíãà, åñëè íåêîòîðàÿ ìàøèíà Òüþðèíãà å¼ ïðàâèëüíî âû÷èñëÿåò.1kïðàâèëüíî âû÷èñëèìà3Íàïðèìåð, ôóíêöèÿf (x) = x + 1ïðàâèëüíî âû÷èñëèìà íà ìàøèíåÒüþðèíãà ñî ñëåäóþùåé ïðîãðàììîé:q1 1 → q1 1R, q1 0 → q2 1L, q2 1 → q2 1L, q2 0 → q0 0R.Óïðàæíåíèå.Óáåäèòüñÿ, ÷òî ýòî èìåííî òàê.Åñëè â ýòîì îïðåäåëåíèè îïóñòèòü òðåáîâàíèå íå äîñòðàèâàòü ÿ÷åéêè ñëåâà, òî ïîëó÷èòñÿ ïðîñòî îïðåäåëåíèå ôóíêöèé, âû÷èñëèìûõ íàìàøèíàõ Òüþðèíãà.Êëàññ ôóíêöèé, âû÷èñëèìûõ íà ìàøèíàõ Òüþðèíãà, ñîâïàäàåò ñ êëàññîì âñåõ ôóíêöèé, ïðàâèëüíî âû÷èñëèìûõ íà ìàøèíàõÒüþðèíãà è ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.Òåîðåìà 1.2Ìû íå áóäåì ïðèâîäèòü äîêàçàòåëüñòâî ýòîé òåîðåìû. Áóäó÷è âåñüìà ãðîìîçäêî òåõíè÷åñêè, îíî âåñüìà ïðîñòî ïî ñâîåé èäåå è ñëåäóåòòîé æå ñàìîé ñõåìå, ÷òî è äîêàçàòåëüñòâî ñîâïàäåíèÿ êëàññîâ ÷àñòè÷íîðåêóðñèâíûõ ôóíêöèé è ôóíêöèé, âû÷èñëèìûõ íà ìèíèìàøèíàõ.2Íóìåðàöèè è àëãîðèòìè÷åñêèå ïðîáëåìûÌû óæå âèäåëè, ÷òî ìíîãèå îáúåêòû, âíåøíå íå ïîõîæèå íà íàòóðàëüíûå÷èñëà, òàêèå, êàê ñëîâà, êîìàíäû, ïðîãðàììû, âû÷èñëåíèÿ, ìîãóò áûòüçàêîäèðîâàíû ñ ïîìîùüþ íàòóðàëüíûõ ÷èñåë.

Ìîæíî òàêæå ïðèäóìàòüìåòîäû êîäèðîâàíèÿ è äëÿ ìíîãèõ äðóãèõ êëàññîâ îáúåêòîâ, òàêèõ êàê,íàïðèìåð, òåêñòîâ, ìàòðèö, ðàöèîíàëüíûõ ÷èñåë è ïðî÷èõ.Áëàãîäàðÿ òàêîé âîçìîæíîñòè îòîæäåñòâëåíèÿ íàøèõ îáúåêòîâ ñ íàòóðàëüíûìè ÷èñëàìè, ìû ìîæåì ãîâîðèòü òàêæå è îá àëãîðèòìàõ, ðàáîòàþùèõ íàä ýòèìè îáúåêòàìè.íóìåðàöèèÎïðåäåëåíèå 2.1 Ïóñòü S íåêîòîðîå ìíîæåñòâî.

Ëþáîå îòîáðàæåíèå ν èç N íà ýòî ìíîæåñòâî íàçûâàåòñÿ íóìåðàöèåé ýòîãî ìíîæåñòâà. Ïðè ýòîì óïîðÿäî÷åííàÿ ïàðà (S, ν) íàçûâàåòñÿ íóìåðîâàííûì ìíîæåñòâîì.Ýòè ðàññìîòðåíèÿ ïðèâîäÿò ê ïîíÿòèþÏóñòüν íóìåðàöèÿ. Îòíîøåíèåíóìåðàöèîííîé ýêâèâàëåíòíîñòüþ.Íóìåðàöèÿνíàçûâàåòñÿ4.ην = {(x, y) | νx = νy}íàçûâàåòñÿðàçðåøèìîé• îäíîçíà÷íîé•, åñëè îòíîøåíèå, åñëèÏðèìåð.νηνðåêóðñèâíî;âçàèìíîîäíîçíà÷íà.Îïðåäåëèì êîä öåëîãî ÷èñëàêîä (z) =h0, |z|i ,h1, |z|i ,z ∈ Z,åñëèåñëèêàê ÷èñëîz>0z<0Äàëåå ìîæíî îïðåäåëèòü êîäèðîâàíèå ìàòðèö2×2íàäZñëåäóþùèìîáðàçîì:êîäa bc d= hêîä (a), êîä (b), êîä (c), êîä (d)i .Òåïåðü íà îñíîâàíèè ýòîãî êîäèðîâàíèÿ ìîæíî îïðåäåëèòü íóìåðàöèþνìàòðèö, êàêν(x) =ìàòðèöå ñ êîäîì1 00 1x,åñëèx êîä ìàòðèöû,â îñòàëüíûõ ñëó÷àÿõÒåïåðü ìîæíî ñòàâèòü, íàïðèìåð, çàäà÷ó ðàñïîçíàâàíèÿ íîìåðîâ ìàòðèöäëÿ êîòîðûõ ñóùåñòâóåò îáðàòíàÿ öåëî÷èñëåííàÿ ìàòðèöà.

Íå ñîñòàâëÿåò áîëüøîãî òðóäà ïîêàçàòü, ÷òî ìíîæåñòâî íîìåðîâ òàêèõ ìàòðèöâû÷èñëèìî. ×èòàòåëü, ïðî÷èòàâøèé ýòó êíèãó ñ íà÷àëà äî ýòîãî ìåñòà,âïîëíå ñïîñîáåí ñàìîñòîÿòåëüíî ïðîâåñòè ýòî äîêàçàòåëüñòâî.Óìåÿ êîäèðîâàòü îáúåêòû ìíîæåñòâàSíàòóðàëüíûìè ÷èñëàìè, ìûìîæåì ãîâîðèòü îá àëãîðèòìè÷åñêèõ ïðîáëåìàõ íàä ýòèì ìíîæåñòâîì.Êàê ïðàâèëî, àëãîðèòìè÷åñêàÿ ïðîáëåìà ñîñòîèò â ðàñïîçíàâàíèè îáúåêòîâ ìíîæåñòâàS , îáëàäàþùèõ îïðåäåë¼ííûìè ñâîéñòâàìè. Îáùåå îïðå-äåëåíèå àëãîðèòìè÷åñêîé ïðîáëåìû íàä íóìåðîâàííûì ìíîæåñòâîì âûãëÿäèò òàê:Ïóñòü (S, ν) íóìåðîâàííîå ìíîæåñòâî.

Ëþáîåïîäìíîæåñòâî S0 ⊆ S íàçûâàåòñÿ àëãîðèòìè÷åñêîé ïðîáëåìîé íàä(S, ν). Ýòà àëãîðèòìè÷åñêàÿ ïðîáëåìà íàçûâàåòñÿ ðàçðåøèìîé, åñëèìíîæåñòâî {x | ν(x) ∈ S0} âû÷èñëèìî è íåðàçðåøèìîé â ïðîòèâíîìñëó÷àå.Îïðåäåëåíèå 2.2Òàêèì îáðàçîì, ïðîáëåìà ðàñïîçíàâàíèÿ îáðàòèìûõ öåëî÷èñëåííûõìàòðèö ðàçìåðíîñòè2×2 íàä óêàçàííîé âûøå íóìåðàöèåé ν5ðàçðåøèìà.Ëþáîå ïîäìíîæåñòâîS0 ⊆ Nìîæíî ðàññìàòðèâàòü, êàê àëãîðèòìè-÷åñêóþ ïðîáëåìó íàä òîæäåñòâåííîé íóìåðàöèåéν(x) = x.***Ïðèâåäåì åù¼ îäèí âàæíûé ïðèìåð àëãîðèòìè÷åñêîé ïðîáëåìû. Íàïîìíèì, ÷òî çàïèñüçàïèñüf (x̄) ↑f (x̄) ↓îçíà÷àåò, ÷òî çíà÷åíèåîçíà÷àåò, ÷òî çíà÷åíèåf (x̄)f (x̄)îïðåäåëåíî, àíåîïðåäåë¼ííî.Òåîðåìà 2.3 (Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâêè)ÏðîáëåìàK = {x ∈ N | {x}(x) ↓}íåðàçðåøèìà.Äîêàçàòåëüñòâî.Ïðåäïîëîæèì, ÷òî ýòà ïðîáëåìà ðàçðåøèìà.

Òîãäàôóíêöèÿf (x) ={x}(x) ↑0,åñëèíåîïðåäåëåíà,â ïðîòèâíîì ñëó÷àåÿâëÿåòñÿ ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèåé, òàê êàê& y = 0).Ðàññìîòðèìa∈Nòàêîå, ÷òîf (x) ' µy({x}(x) ↑f (x) ' {a}(x).Èìååì{a}(x) ↓⇔ f (x) ↓⇔ {x}(x) ↑ .Ïîäñòàâèâx = a,Ñëåäñòâèå 2.4ïîëó÷èì ïðîòèâîðå÷èå{a}(a) ↓⇔ {a}(a) ↑ . Ïðîáëåìà{hx, yi ∈ N | {x}(y) ↓}íåðàçðåøèìà.Äîêàçàòåëüñòâî.Ìû äàäèì ëèøü èäåþ äîêàçàòåëüñòâà, îñòàâëÿÿ äå-òàëè â êà÷åñòâå óïðàæíåíèÿ. Åñëè áû ýòà ïðîáëåìà áûëà ðàçðåøèìà, òîáûëà áû ðàçðåøèìà è ïðîáëåìà{x ∈ N | {x}(x) ↓}. Ýòîò ðåçóëüòàò ìîæåò áûòü ìåíåå ôîðìàëüíî ïåðåôîðìóëèðîâàí ñëå-Íå ñóùåñòâóåò àëãîðèòìà, êîòîðûé ïî çàäàííûìïðîãðàììå è äàííûì îïðåäåëÿåò, çàâåðøèòñÿ ëè âû÷èñëåíèå ïî äàííîéïðîãðàììå íà ýòèõ âõîäíûõ äàííûõ.äóþùèì îáðàçîì:Äëÿ ìíîãèõ êëàññîâ îáúåêòîâ ìîæíî óêàçàòü òàêóþ åñòåñòâåííóþ êîäèðîâêó íàòóðàëüíûìè ÷èñëàìè, ÷òî ïî ëþáîìó îáúåêòó ìîæíî ýôôåêòèâíî îïðåäåëèòü íåêîòîðîå íàòóðàëüíîå ÷èñëî åãî íîìåð, è ïî ëþáîìó íàòóðàëüíîìó ÷èñëó ìîæíî ýôôåêòèâíî âîññòàíîâèòü ñàì îáúåêò.6Ïîýòîìó ìû ìîæåì ãîâîðèòü ïðîñòî î ïðîáëåìå ðàñïîçíàâàíèÿ îáðàòèìûõ öåëî÷èñëåííûõ ìàòðèö, íå óïîìèíàÿ ñàìó íóìåðàöèþ, à ëèøü ïîäðàçóìåâàÿ å¼.