1610906280-58a805c0f28e2c985192966a2f3bd6d2 (824374), страница 14
Текст из файла (страница 14)
Òîãäà Λ →A 1Λ →A 11Λ →A 111Λ →A . . ., è A(Λ)íå îïðåäåëåíî.3. Ïóñòü A = 0 → 1. Òîãäà A(22) = 22.Îïðåäåëåíèå 3.6.1 Áóäåì ãîâîðèòü, ÷òî ÷àñòè÷íàÿ ôóíêöèÿ f : Nk →N âû÷èñëèìà ñ ïîìîùüþ íîðìàëüíîãî àëãîðèôìà Ìàðêîâà A, åñëè äëÿëþáûõ x1 , . . . , xk ∈ N â ñëó÷àå, êîãäà çíà÷åíèå f (x1 , . . . , xk ) îïðåäåëåíî,âûïîëíåíî A(1x1 01x2 0 .
. . 01xk ) = 1f (x1 ,...,xk ) , à â ñëó÷àå, êîãäà çíà÷åíèåf (x1 , . . . , xk ) íå îïðåäåëåíî, A(1x1 01x2 0 . . . 01xk ) òîæå íå îïðåäåëåíî.Áóäåì ãîâîðèòü, ÷òî ÷àñòè÷íàÿ ôóíêöèÿ f : Nk → N âû÷èñëèìà ñïîìîùüþ íîðìàëüíûõ àëãîðèôìîâ Ìàðêîâà, åñëè îíà âû÷èñëèìà ñ ïîìîùüþ íåêîòîðîãî íîðìàëüíîãî àëãîðèôìà Ìàðêîâà.Ïðèìåð.
Ôóíêöèÿ s(x) = x + 1 âû÷èñëÿåòñÿ íîðìàëüíûì àëãîðèôìîì,ñîñòîÿùèì èç îäíîé ðåäóêöèè Λ →• 1.Ñïðàâåäëèâà ñëåäóþùàÿ òåîðåìà:3.7. Òåçèñ ×¼ð÷à79Òåîðåìà 3.6.2 Êëàññ ôóíêöèé, âû÷èñëèìûõ ñ ïîìîùüþ íîðìàëüíûõàëãîðèôìîâ Ìàðêîâà ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõôóíêöèé.Îáùàÿ ñõåìà äîêàçàòåëüñòâà ýòîé òåîðåìû òàêàÿ æå, êàê è äëÿ ìàøèí ؼíôèëäà, è ìû åãî îïóñêàåì.Óïðàæíåíèÿ.1. Äîêàçàòü âû÷èñëèìîñòü ñ ïîìîùüþ íîðìàëüíûõ àëãîðèôìîâ Ìàðêîâà ñëåäóþùèõ ôóíêöèé:à) f (x) = 0;á) x−̇1;â) x − 1;ã) x−̇y ;ä) x − y ;å) f (x) = îñòàòîê îò äåëåíèÿ x íà 2;¼) Inm (x1 , .
. . , xm ) = xn .2. Ïóñòü A íåêîòîðûé êîíå÷íûé àëôàâèò. Ïîñòðîèòü íîðìàëüíûåàëãîðèôìû A (âîçìîæíî â ðàñøèðåííîì àëôàâèòå), óäîâëåòâîðÿþùèå ñëåäóþùèì óñëîâèÿì:à) A(w) = Λ, äëÿ âñåõ w ∈ A∗ ;á) A(w) = 1|w| , äëÿ âñåõ w ∈ A∗ ;â) A(w) = w½0 (ôèêñèðîâàííîå ñëîâî), äëÿ âñåõ w ∈ A∗ ;w0 åñëè w = w0ã)∗ A(w) =Λ â ïðîòèâíîì ñëó÷àå,äëÿ âñåõ w ∈ A∗ (w0 ôèêñèðîâàííîå ñëîâî);ä) f (w) = aw (a ôèêñèðîâàííûé ñèìâîë);å)∗ f (w) = wa½ (a ôèêñèðîâàííûé ñèìâîë);1 åñëè w ðåãóëÿðíîå âûðàæåíèå¼)∗ A(w) =.0 â ïðîòèâíîì ñëó÷àå.3.7 Òåçèñ ×¼ð÷àÌû óæå ðàññìîòðåëè òàêèå âåñüìà íåïîõîæèå, èäóùèå îò ðàçíûõ îáùèõ èäåé è ïðåäñòàâëåíèé, ìàòåìàòè÷åñêèå ôîðìàëèçàöèè âû÷èñëèìîñòè, êàê ìàøèíû ؼíôèëäà, ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè, ìàøèíû Òüþðèíãà, íîðìàëüíûå àëãîðèôìû Ìàðêîâà.
Íåòðèâèàëüíûå äîêàçàòåëüñòâà ñâèäåòåëüñòâóþò, ÷òî êëàññû ôóíêöèé, âû÷èñëèìûå â ýòèõ80Ãëàâà 3. Ôîðìàëèçàöèè ïîíÿòèÿ àëãîðèòìàôîðìàëèçàöèÿõ, ñîâïàäàþò. Ñóùåñòâóþò è äðóãèå ìàòåìàòè÷åñêèå ôîðìàëèçàöèè ïîíÿòèÿ âû÷èñëèìîñòè, àíàëèç êîòîðûõ òàêæå ïîêàçûâàåò,÷òî ïîëó÷àþùèéñÿ ïðè ýòîì êëàññ ôóíêöèé ñîâïàäàåò ñ êëàññîì ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé. Ýòî ïîçâîëÿåò óòâåðæäàòü, ÷òî ïîëó÷èâøèéñÿòî÷íî ìàòåìàòè÷åñêè îïðåäåëåííûé êëàññ âû÷èñëèìûõ ôóíêöèé ñîâïàäàåò ñ êëàññîì èíòóèòèâíî âû÷èñëèìûõ ôóíêöèé, òî åñòü, ÷òî ïðåäëîæåííîå â ðåçóëüòàòå ìàòåìàòè÷åñêîå ïîíÿòèå âû÷èñëèìîñòè àäåêâàòíîîòðàæàåò íàøè èíòóèòèâíûå ïðåäñòàâëåíèÿ î âû÷èñëèìîñòè. Ýòî óòâåðæäåíèå èçâåñòíî ïîä íàçâàíèåì òåçèñà ×¼ð÷à, êîòîðûé îáû÷íî ôîðìóëèðóåòñÿ â ñëåäóþùåì âèäå:Òåçèñ ×¼ð÷à.
Êëàññ èíòóèòèâíî âû÷èñëèìûõ ôóíêöèé ñîâïàäàåò ñ êëàññîì âñåõ ÷àñòè÷íî ðåêóðñèâíûõ ôóíêöèé.Òåçèñ ×¼ð÷à íå ÿâëÿåòñÿ ìàòåìàòè÷åñêèì óòâåðæäåíèåì, è åãî íåëüçÿ íè äîêàçàòü íè îïðîâåðãíóòü ìàòåìàòè÷åñêèìè ðàññóæäåíèÿìè.Òåì íå ìåíåå, òåçèñ ×¼ð÷à èñïîëüçóåòñÿ â ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâàõ. Òàê, íàïðèìåð, ÷òîáû äîêàçàòü ñóùåñòâîâàíèå ðåêóðñèâíîéôóíêöèè ñ çàäàííûìè ñâîéñòâàìè, â ìàòåìàòè÷åñêîì äîêàçàòåëüñòâå ìîæåò áûòü ïîêàçàíà åå èíòóèòèâíàÿ âû÷èñëèìîñòü è îïóùåíî ôîðìàëüíîå äîêàçàòåëüñòâî åå ðåêóðñèâíîñòè.  òàêèõ ñëó÷àÿõ ãîâîðÿò, ÷òî äîêàçàòåëüñòâî ïðîâîäèòñÿ ïî òåçèñó ×¼ð÷à.
Âî âñåõ òàêèõ ñëó÷àÿõ, îäíàêî,äîêàçûâàþùèé äîëæåí áûòü ãîòîâ ïðåäñòàâèòü õîòÿ áû è íåâåðîÿòíî ãðîìîçäêîå íî ôîðìàëüíîå äîêàçàòåëüñòâî âû÷èñëèìîñòè òàêîéôóíêöèè.Ââèäó ýêâèâàëåíòíîñòè ðàçëè÷íûõ îïðåäåëåíèé âû÷èñëèìîñòè, íà÷èíàÿ ñ ýòîãî ìîìåíòà ìû áóäåì íàçûâàòü ÷àñòè÷íî ðåêóðñèâíûå ôóíêöèè òàêæå ÷àñòè÷íûìè âû÷èñëèìûìè ôóíêöèÿìè, ðåêóðñèâíûå ôóíêöèè òàêæå âû÷èñëèìûìè ôóíêöèÿìè, à ðåêóðñèâíûå îòíîøåíèÿ òàêæå âû÷èñëèìûìè îòíîøåíèÿìè.Ãëàâà 4Äàëüíåéøèå ðåçóëüòàòû îâû÷èñëèìîñòè4.1 Íóìåðàöèè è àëãîðèòìè÷åñêèå ïðîáëåìûÌû óæå âèäåëè, ÷òî ìíîãèå îáúåêòû, âíåøíå íå ïîõîæèå íà íàòóðàëüíûå÷èñëà, òàêèå, êàê ñëîâà, êîìàíäû, ïðîãðàììû, âû÷èñëåíèÿ, ìîãóò áûòüçàêîäèðîâàíû ñ ïîìîùüþ íàòóðàëüíûõ ÷èñåë.
Ìîæíî òàêæå ïðèäóìàòüìåòîäû êîäèðîâàíèÿ è äëÿ ìíîãèõ äðóãèõ êëàññîâ îáúåêòîâ, òàêèõ êàê,íàïðèìåð, òåêñòîâ, ìàòðèö, ðàöèîíàëüíûõ ÷èñåë è ïðî÷èõ.Áëàãîäàðÿ òàêîé âîçìîæíîñòè îòîæäåñòâëåíèÿ íàøèõ îáúåêòîâ ñ íàòóðàëüíûìè ÷èñëàìè, ìû ìîæåì ãîâîðèòü òàêæå è îá àëãîðèòìàõ, ðàáîòàþùèõ íàä ýòèìè îáúåêòàìè.Ýòè ðàññìîòðåíèÿ ïðèâîäÿò ê ïîíÿòèþ íóìåðàöèè.Îïðåäåëåíèå 4.1.1 Ïóñòü S íåêîòîðîå ìíîæåñòâî. Ëþáîå îòîáðàæåíèå ν èç N íà ýòî ìíîæåñòâî íàçûâàåòñÿ íóìåðàöèåé ýòîãî ìíîæåñòâà. Ïðè ýòîì óïîðÿäî÷åííàÿ ïàðà (S, ν) íàçûâàåòñÿ íóìåðîâàííûì ìíîæåñòâîì.Ïóñòü ν íóìåðàöèÿ. Îòíîøåíèå ην = {(x, y) | νx = νy} íàçûâàåòñÿíóìåðàöèîííîé ýêâèâàëåíòíîñòüþ.Íóìåðàöèÿ ν íàçûâàåòñÿ• ðàçðåøèìîé, åñëè îòíîøåíèå ην ðåêóðñèâíî;• ïîçèòèâíîé, åñëè ñóùåñòâóåò ðåêóðñèâíàÿ ôóíêöèÿ, îáëàñòü çíà÷åíèé êîòîðîé åñòü ìíîæåñòâî êîäîâ ïàð èç ην , òî åñòü, âñå ïàðû8182Ãëàâà 4.
Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòè÷èñåë x, y ñî ñâîéñòâîì νx = νy ìîãóò áûòü ïåðå÷èñëåíû1 ñ ïîìîùüþ íåêîòîðîãî àëãîðèòìà;• íåãàòèâíîé, åñëè ñóùåñòâóåò ðåêóðñèâíàÿ ôóíêöèÿ, îáëàñòü çíà÷åíèé êîòîðîé åñòü ìíîæåñòâî êîäîâ ïàð èç N2 \ ην , òî åñòü, âñåïàðû ÷èñåë x, y ñî ñâîéñòâîì νx 6= νy ìîãóò áûòü ïåðå÷èñëåíû ñïîìîùüþ íåêîòîðîãî àëãîðèòìà;• îäíîçíà÷íîé, åñëè ν âçàèìíîîäíîçíà÷íà.Óìåÿ êîäèðîâàòü îáúåêòû ìíîæåñòâà S íàòóðàëüíûìè ÷èñëàìè, ìûìîæåì ãîâîðèòü îá àëãîðèòìè÷åñêèõ ïðîáëåìàõ íàä ýòèì ìíîæåñòâîì.Êàê ïðàâèëî, àëãîðèòìè÷åñêàÿ ïðîáëåìà ñîñòîèò â ðàñïîçíàâàíèè îáúåêòîâ ìíîæåñòâà S , îáëàäàþùèõ îïðåäåëåííûìè ñâîéñòâàìè.
ÐàññìîòðèìÏðèìåð. Îïðåäåëèì êîä öåëîãî ÷èñëà z ∈ Z, êàê ÷èñëî½êîä (z) =h0, |z|i , åñëè z > 0h1, |z|i , åñëè z < 0Äàëåå ìîæíî îïðåäåëèòü êîäèðîâàíèå ìàòðèö 2 × 2 íàä Z ñëåäóþùèìîáðàçîì:µ·¸¶a bêîä= hêîä (a), êîä (b), êîä (c), êîä (d)i .c dÒåïåðü íà îñíîâàíèè ýòîãî êîäèðîâàíèÿ ìîæíî îïðåäåëèòü íóìåðàöèþ ν ìàòðèö, êàê ìàòðèöå ñ êîäîì x, åñëè x êîä ìàòðèöû·¸ν(x) =10,â îñòàëüíûõ ñëó÷àÿõ0 1Òåïåðü ìîæíî ñôîðìóëèðîâàòü ïðîáëåìó ðàñïîçíàâàíèÿ íîìåðîâ ìàòðèö äëÿ êîòîðûõ ñóùåñòâóåò îáðàòíàÿ öåëî÷èñëåííàÿ ìàòðèöà. Íå ñîñòàâëÿåò áîëüøîãî òðóäà ïîêàçàòü, ÷òî ìíîæåñòâî íîìåðîâ òàêèõ ìàòðèöâû÷èñëèìî.
×èòàòåëü, ïðî÷èòàâøèé ýòó êíèãó ñ íà÷àëà äî ýòîãî ìåñòà,âïîëíå ñïîñîáåí ñàìîñòîÿòåëüíî ïðîâåñòè ýòî äîêàçàòåëüñòâî.Îáùåå îïðåäåëåíèå àëãîðèòìè÷åñêîé ïðîáëåìû íàä íóìåðîâàííûììíîæåñòâîì âûãëÿäèò òàê:1Èíà÷å ãîâîðÿ, ýòà ýêâèâàëåíòíîñòü ÿâëÿåòñÿ âû÷èñëèìî ïåðå÷èñëèìîé. Î âû÷èñëèìî ïåðå÷èñëèìûõ ìíîæåñòâàõ ðå÷ü ïîéäåò äàëåå â ïàðàãðàôå 4.4.4.1.
Íóìåðàöèè è àëãîðèòìè÷åñêèå ïðîáëåìû83Îïðåäåëåíèå 4.1.2 Ïóñòü (S, ν) íóìåðîâàííîå ìíîæåñòâî. Ëþáîåïîäìíîæåñòâî S0 ⊆ S íàçûâàåòñÿ àëãîðèòìè÷åñêîé ïðîáëåìîé íàä(S, ν). Ýòà àëãîðèòìè÷åñêàÿ ïðîáëåìà íàçûâàåòñÿ ðàçðåøèìîé, åñëèìíîæåñòâî {x | ν(x) ∈ S0 } âû÷èñëèìî è íåðàçðåøèìîé â ïðîòèâíîìñëó÷àå.Òàêèì îáðàçîì, ïðîáëåìà ðàñïîçíàâàíèÿ îáðàòèìûõ öåëî÷èñëåííûõìàòðèö ðàçìåðíîñòè 2×2 íàä óêàçàííîé âûøå íóìåðàöèåé ν ðàçðåøèìà.Ìîæíî áûëî áû òàêæå îïðåäåëèòü àëãîðèòìè÷åñêóþïðîáëåìó êàêSìíîæåñòâî S0 ⊆ S n èëè äàæå êàê S0 ⊆ i∈N S i .
Ââèäó èìåþùåéñÿ âîçìîæíîñòè êîäèðîâàíèÿ íàòóðàëüíûìè ÷èñëàìè nîê íàòóðàëüíûõ ÷èñåë, îáà ýòè âàðèàíòà ìîæíî ïðèâåñòè ê äàííîìó íàìè îïðåäåëåíèþàëãîðèòìè÷åñêîé ïðîáëåìû, êàê ïîäìíîæåñòâà íåêîòîðîãî íóìåðîâàííîãî ìíîæåñòâà, âîçìîæíî, çàìåíèâ èñõîäíîå íóìåðîâàííîå ìíîæåñòâîíà êàêîåíèáóäü äðóãîå.Ëþáîå ïîäìíîæåñòâî S0 ⊆ N ìîæíî ðàññìàòðèâàòü, êàê àëãîðèòìè÷åñêóþ ïðîáëåìó íàä òîæäåñòâåííîé íóìåðàöèåé ν(x) = x.Ïðèâåäåì åùå îäèí âàæíûé ïðèìåð àëãîðèòìè÷åñêîé ïðîáëåìû. Íàïîìíèì, ÷òî çàïèñü f (x̄) ↓ îçíà÷àåò, ÷òî çíà÷åíèå f (x̄) îïðåäåëåíî, àçàïèñü f (x̄) ↑ îçíà÷àåò, ÷òî çíà÷åíèå f (x̄) íåîïðåäåëåíî.Òåîðåìà 4.1.3 (Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâêè) ÏðîáëåìàK = {x ∈ N | {x}(x) ↓}íåðàçðåøèìà.Äîêàçàòåëüñòâî.
Ïðåäïîëîæèì, ÷òî ýòà ïðîáëåìà ðàçðåøèìà. Òîãäàôóíêöèÿ½f (x) =0,åñëè {x}(x) ↑íåîïðåäåëåíà, â ïðîòèâíîì ñëó÷àåÿâëÿåòñÿ ÷àñòè÷íîé âû÷èñëèìîé ôóíêöèåé, òàê êàê f (x) ' µy({x}(x) ↑& y = 0). Ðàññìîòðèì a ∈ N òàêîå, ÷òî f (x) ' {a}(x). Èìååì{a}(x) ↓⇔ f (x) ↓⇔ {x}(x) ↑ .Ïîäñòàâèâ x = a, ïîëó÷èì ïðîòèâîðå÷èå {a}(a) ↓⇔ {a}(a) ↑ . ¤Ñëåäñòâèå 4.1.4 Ïðîáëåìà{hx, yi ∈ N | {x}(y) ↓}íåðàçðåøèìà.84Ãëàâà 4. Äàëüíåéøèå ðåçóëüòàòû î âû÷èñëèìîñòèÄîêàçàòåëüñòâî. Ìû äàäèì ëèøü èäåþ äîêàçàòåëüñòâà, îñòàâëÿÿ äå-òàëè â êà÷åñòâå óïðàæíåíèÿ. Åñëè áû ýòà ïðîáëåìà áûëà ðàçðåøèìà, òîáûëà áû ðàçðåøèìà è ïðîáëåìà {x ∈ N | {x}(x) ↓}. ¤Ýòîò ðåçóëüòàò ìîæåò áûòü ìåíåå ôîðìàëüíî ïåðåôîðìóëèðîâàí ñëåäóþùèì îáðàçîì: Íå ñóùåñòâóåò àëãîðèòìà, êîòîðûé ïî çàäàííûìïðîãðàììå è äàííûì îïðåäåëÿåò, çàâåðøèòñÿ ëè âû÷èñëåíèå ïî äàííîéïðîãðàììå íà ýòèõ âõîäíûõ äàííûõ.Äëÿ ìíîãèõ êëàññîâ îáúåêòîâ ìîæíî óêàçàòü òàêóþ åñòåñòâåííóþ êîäèðîâêó íàòóðàëüíûìè ÷èñëàìè, ÷òî ïî ëþáîìó îáúåêòó ìîæíî ýôôåêòèâíî îïðåäåëèòü íåêîòîðîå íàòóðàëüíîå ÷èñëî åãî íîìåð, è ïî ëþáîìó íàòóðàëüíîìó ÷èñëó ìîæíî ýôôåêòèâíî âîññòàíîâèòü ñàì îáúåêò.Ïîýòîìó ìû ìîæåì ãîâîðèòü ïðîñòî î ïðîáëåìå ðàñïîçíàâàíèÿ îáðàòèìûõ öåëî÷èñëåííûõ ìàòðèö, íå óïîìèíàÿ ñàìó íóìåðàöèþ, à ëèøü ïîäðàçóìåâàÿ å¼.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
