1610906281-2dcf0fef1ce626ab2dbf8dbda8c94e1a (824378)
Текст из файла
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Ïîýòîìó ìû ìîæåì ãîâîðèòü ïðîñòî î ïðîáëåìå ðàñïîçíàâàíèÿ îáðàòèìûõ öåëî÷èñëåííûõ ìàòðèö, íå óïîìèíàÿ ñàìó íóìåðàöèþ, à ëèøü ïîäðàçóìåâàÿ å¼.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
