Таран Т.А. Основы дискретной математики

Подождите немного. Документ загружается.

260

íåïðîòèâîðå÷èâîñòè òåîðèè S. Âñïîìíèì òåïåðü, ÷òî, â ñîîòâåòñòâèè

ñî ñòàíäàðòíîé èíòåðïðåòàöèåé, ã¸äåëåâà íåðàçðåøèìàÿ ôîðìóëà

G ñîäåðæàòåëüíî âûðàæàåò ñâîþ ñîáñòâåííóþ íåâûâîäèìîñòü. Òîãäà

ôîðìóëà Con

→G ñîäåðæàòåëüíî óòâåðæäàåò, ÷òî åñëè òåîðèÿ S

íåïðîòèâîðå÷èâà, òî ôîðìóëà G â íåé íåâûâîäèìà. Íî â ýòîì è

ñîñòîèò ïåðâàÿ ÷àñòü òåîðåìû Ã¸äåëÿ.

Ìàòåìàòè÷åñêèå ðàññóæäåíèÿ, äîêàçûâàþùèå òåîðåìó Ã¸äåëÿ,

ìîãóò áûòü âûðàæåíû è ïðîâåäåíû ñðåäñòâàìè òåîðèè S, òàê ÷òî â

ðåçóëüòàòå îêàçûâàåòñÿ âîçìîæíûì ïîëó÷èòü âûâîä ôîðìóëû

Con

→G â òåîðèè S. (Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ ñì. â

[Ãèëüáåðò, Áåðíàéñ, 1979]). Èòàê, |

S

Con

→G. Ïðåäïîëîæèì, ÷òî

|

S

Con

, ò.å.ñðåäñòâàìè òåîðèè S ìîæíî äîêàçàòü íåïðîòè-

âîðå÷èâîñòü S. Òîãäà ïî ïðàâèëó ÌÐ ïîëó÷èì |

G. Ñîãëàñíî

òåîðåìå Ã¸äåëÿ, îäíàêî, åñëè òåîðèÿ S íåïðîòèâîðå÷èâà, òî ôîðìóëà

G â íåé íåâûâîäèìà. Îòñþäà ñëåäóåò, ÷òî åñëè òåîðèÿ S

íåïðîòèâîðå÷èâà, òî â íåé íåâûâîäèìà è ôîðìóëà Con

. Èíûìè

ñëîâàìè, åñëè òåîðèÿ íåïðîòèâîðå÷èâà, òî â íåé íåâûâîäèìà íåêîòî-

ðàÿ ôîðìóëà, ñîäåðæàòåëüíî óòâåðæäàþùàÿ íåïðîòèâîðå÷èâîñòü

òåîðèè S.

Ýòîò ðåçóëüòàò íîñèò íàçâàíèå âòîðîé òåîðåìû Ã¸äåëÿ. Ãðóáî

ãîâîðÿ, ýòà òåîðåìà óòâåðæäàåò, ÷òî åñëè òåîðèÿ S íåïðîòèâîðå÷èâà,

òî äîêàçàòåëüñòâî íåïðîòèâîðå÷èâîñòè òåîðèè íå ìîæåò áûòü ïðîâå-

äåíî ñðåäñòâàìè ñàìîé òåîðèè S, ò. å. âñÿêîå òàêîå äîêàçàòåëüñòâî

îáÿçàòåëüíî äîëæíî èñïîëüçîâàòü íåâûðàçèìûå â S èäåè èëè

ìåòîäû. Ïðèìåðàìè ìîãóò ñëóæèòü äîêàçàòåëüñòâà íåïðîòèâîðå-

÷èâîñòè òåîðèè S, ïðåäëîæåííûå Ãåíöåíîì â 1936, 1938 ã.ã. è Øþòòå

â 1951 ã., â êîòîðûõ ïðèìåíÿþòñÿ ïîíÿòèÿ è ìåòîäû (íàïðèìåð,

îäèí ôðàãìåíò òåîðèè ñ÷åòíûõ ïîðÿäêîâûõ ÷èñåë), î÷åâèäíî, íå

ôîðìàëèçóåìûå ñðåäñòâàìè òåîðèè S.

Ãëàâà 14

Ãëàâà 15. ÒÅÎÐÈß ÀËÃÎÐÈÒÌÎÂ

15.1. Èíòóèòèâíîå ïîíÿòèå àëãîðèòìà

Ôóíêöèÿ f(x

,, x

) íàçûâàåòñÿ ýôôåêòèâíî âû÷èñëèìîé, åñëè

äëÿ êàæäîãî íàáîðà àðãóìåíòîâ à

,, à

èç åå îáëàñòè îïðåäåëåíèÿ

ìîæåò áûòü âû÷èñëåíî çíà÷åíèå ôóíêöèè f(à

, , à

). Åñëè ôóíêöèÿ

ýôôåêòèâíî âû÷èñëèìà, òî ãîâîðÿò, ÷òî ñóùåñòâóåò àëãîðèòì åå

âû÷èñëåíèÿ.

Ïîíÿòèå àëãîðèòìà èíòóèòèâíî ÿñíî è ÷àñòî èñïîëüçóåòñÿ â

ìàòåìàòèêå. Ñëîæåíèå è óìíîæåíèå ÷èñåë «ñòîëáèêîì», êîòîðîå

èçâåñòíî åùå ñî øêîëû, ôîðìóëà íàõîæäåíèÿ êîðíåé êâàäðàòíîãî

óðàâíåíèÿ, ïåðåìíîæåíèå äâóõ ìàòðèö ïî ïðàâèëó «ñòðîêà íà

ñòîëáåö» ÿâëÿþòñÿ àëãîðèòìàìè. Ìíîæåñòâî ïðèìåðîâ ìîæíî ïðî-

äîëæèòü. Â ñîâðåìåííîé ïðàêòèêå ïîä àëãîðèòìîì ÷àñòî ïîíèìàþò

ïðîãðàììó, à êðèòåðèåì ñóùåñòâîâàíèÿ àëãîðèòìà ñ÷èòàþò âîçìîæ-

íîñòü åãî çàïðîãðàììèðîâàòü. Îäíàêî ýòî íå ñîâñåì òàê. Ñíà÷àëà

äàäèì ïîíÿòèå àëãîðèòìà.

Ïîä àëãîðèòìîì ïîíèìàþò òî÷íîå ïðåäïèñàíèå î âûïîëíåíèè â

îïðåäåëåííîì ïîðÿäêå òî÷íî óêàçàííîé ïîñëåäîâàòåëüíîñòè

îïåðàöèé äëÿ ðåøåíèÿ âñåõ çàäà÷ èç äàííîãî êëàññà çàäà÷.

Ïðèâåäåííîå âûøå ïîíÿòèå àëãîðèòìà íå ÿâëÿåòñÿ òî÷íûì ìàòå-

ìàòè÷åñêèì îïðåäåëåíèåì. Ýòî ïîíÿòèå õàðàêòåðèçóåòñÿ íàáîðîì

ñâîéñòâ, ïðèñóùèõ àëãîðèòìó.

15.1.1. Ñâîéñòâà àëãîðèòìà

•Äèñêðåòíîñòü èíôîðìàöèè. Êàæäûé àëãîðèòì èìååò äåëî ñ äàííû-

ìè  âõîäíûìè, ïðîìåæóòî÷íûìè è âûõîäíûìè. Ýòè äàííûå ïðåä-

ñòàâëÿþòñÿ â âèäå êîíå÷íûõ ñëîâ â íåêîòîðîì àëôàâèòå.

•Äèñêðåòíîñòü ðàáîòû àëãîðèòìà. Àëãîðèòì âûïîëíÿåòñÿ ïî øà-

ãàì è ïðè ýòîì íà êàæäîì øàãå âûïîëíÿåòñÿ òîëüêî îäíà îïåðàöèÿ.

•Âûïîëíèìîñòü îïåðàöèé. Â àëãîðèòìå íå äîëæíî áûòü íåâûïîëíè-

ìûõ îïåðàöèé. Íàïðèìåð, íåëüçÿ â ïðîãðàììå ïðèñâîèòü ïåðåìåí-

íîé çíà÷åíèå «áåñêîíå÷íîñòü»,  òàêàÿ îïåðàöèÿ áûëà áû íåâûïîë-

íèìîé. Êàæäàÿ îïåðàöèÿ îáðàáàòûâàåò îïðåäåëåííûé ó÷àñòîê â

îáðàáàòûâàåìîì ñëîâå.

•Êîíå÷íîñòü àëãîðèòìà. Êîíå÷íîñòü àëãîðèòìà îçíà÷àåò, ÷òî îïèñà-

íèå àëãîðèòìà äîëæíî áûòü êîíå÷íûì.

•Äåòåðìèíèðîâàííîñòü àëãîðèòìà. Êàæäûé øàã àëãîðèòìà ñòðîãî

îïðåäåëåí. Ïîñëå êàæäîãî øàãà òî÷íî óêàçûâàåòñÿ, êàêîé øàã ñäå-

ëàòü äàëüøå, ëèáî óêàçûâàåòñÿ, ÷òî àëãîðèòì äîëæåí çàêîí÷èòü

ñâîþ ðàáîòó íà äàííîì øàãå. Ê êàæäîìó ó÷àñòêó ñëîâà íà êàæäîì

øàãå ïðèìåíèìà òîëüêî îäíà îïåðàöèÿ.

262 263

•Ìàññîâîñòü àëãîðèòìà. Ìàññîâîñòü àëãîðèòìà îçíà÷àåò, ÷òî àëãî-

ðèòì äîëæåí ðåøàòü âñå çàäà÷è èç äàííîãî êëàññà çàäà÷. Åñëè íàé-

äåòñÿ õîòÿ áû îäíà çàäà÷à, äëÿ êîòîðîé àëãîðèòì íåïðèìåíèì, òî

ýòó ïîñëåäîâàòåëüíîñòü îïåðàöèé íåëüçÿ ñ÷èòàòü àëãîðèòìîì äëÿ

ðåøåíèÿ äàííîãî êëàññà çàäà÷.

15.2. Àëôàâèòû è ñëîâà

15.2.1. Îñíîâíûå ïîíÿòèÿ

Îïðåäåëåíèå 15.1. Áóäåì íàçûâàòü ïðîèçâîëüíîå êîíå÷íîå ìíî-

æåñòâî À àëôàâèòîì, à ýëåìåíòû ýòîãî ìíîæåñòâà  áóêâàìè

àëôàâèòà À. Òîãäà ïðîèçâîëüíûå êîíå÷íûå ïîñëåäîâàòåëüíîñòè

áóêâ íàçûâàþòñÿ ñëîâàìè â äàííîì àëôàâèòå.

Çäåñü è äàëåå äëÿ óäîáñòâà ÷òåíèÿ áóäåì îáîçíà÷àòü: áóêâû-

êîíñòàíòû  ìàëûìè íà÷àëüíûìè ñèìâîëàìè ëàòèíñêîãî àëôàâèòà

(a, b, c,), áóêâû-ïåðåìåííûå  ïîñëåäíèìè ëàòèíñêèìè ñèìâîëàìè

(x, y, z,), àëôàâèòû è ìíîæåñòâà  áîëüøèìè íà÷àëüíûìè

ñèìâîëàìè ëàòèíñêîãî àëôàâèòà (A, B, C,), ñëîâà  áîëüøèìè

ñèìâîëàìè ëàòèíñêîãî àëôàâèòà (P, Q, R, ). Ãðå÷åñêèå ñèìâîëû

áóäóò èñïîëüçîâàòüñÿ äëÿ îáîçíà÷åíèÿ âûäåëåííûõ áóêâ çàäàííîãî

àëôàâèòà, îòëè÷íûõ îò áóêâ-êîíñòàíò è áóêâ-ïåðåìåííûõ. Ëþáîé

àëôàâèò ñîäåðæèò ïóñòîé ñèìâîë. Áóäåì îáîçíà÷àòü åãî ñèìâîëîì

Λ. Ïóñòîé ñèìâîë ÿâëÿåòñÿ è ïóñòûì ñëîâîì. Ìíîæåñòâî ñëîâ àëôà-

âèòà À áóäåì îáîçíà÷àòü À* .

Îïðåäåëåíèå 15.2. Êîëè÷åñòâî áóêâ â ñëîâå íàçûâàåòñÿ åãî äëè-

íîé è îáîçíà÷àåòñÿ âåðòèêàëüíûìè ñêîáêàìè. Íàïðèìåð, äëèíà

ñëîâà àààà ðàâíà |àààà| = 4, äëèíà ïóñòîãî ñëîâà |Λ|= 0.

Îñíîâíîé îïåðàöèåé íàä ñëîâàìè ÿâëÿåòñÿ êîíêàòåíàöèÿ.

Îïðåäåëåíèå 15.3. Êîíêàòåíàöèåé äâóõ ñëîâ P è Q íàçîâåì

ñëîâî PQ, ïîëó÷åííîå äîïèñûâàíèåì ñëîâà Q ïîñëå P.

Íàïðèìåð, êîíêàòåíàöèÿ ñëîâ aab è ba åñòü ñëîâî aabba. Îïåðà-

öèÿ êîíêàòåíàöèè íåêîììóòàòèâíà, íî àññîöèàòèâíà.

Îïðåäåëåíèå 15.4. Åñëè X  íåêîòîðîå ñëîâî àëôàâèòà A è

åñëè X ïðåäñòàâèìî â âèäå êîíêàòåíàöèè ñëîâ PQR, òî P, Q, R

íàçûâàþò ïîäñëîâàìè ñëîâà X.

Íàïðèìåð, ñëîâî añb ñîäåðæèò ïîäñëîâà a, b, ñ, añ, ñb. Åñëè

X∈A* è X= P

òî ãîâîðÿò î ïåðâîì, âòîðîì è ò. ä. âõîæäåíèè

ñëîâà Q â ñëîâî X. Ñëîâà, ñîñòàâëåííûå èç ïîñëåäîâàòåëüíîñòè

îäèíàêîâûõ áóêâ, èíîãäà çàïèñûâàþòñÿ â âèäå ñòåïåíè, íàïðèìåð,

àààbb = a

, ãäå ñòåïåíü îáîçíà÷àåò êîëè÷åñòâî âõîæäåíèé áóêâû

â ñëîâî.

Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

15.2.2. Êîäèðîâàíèå è íóìåðàöèÿ

Îïðåäåëåíèå 15.5. Ïóñòü äàíû äâà àëôàâèòà A è B. Êîäèðîâàíèå

ñëîâ àëôàâèòà A ñëîâàìè â àëôàâèòå B åñòü ôóíêöèÿ ϕ(P), êîòî-

ðàÿ îñóùåñòâëÿåò îòîáðàæåíèå ìíîæåñòâà ñëîâ â àëôàâèòå À â

ìíîæåñòâî ñëîâ â àëôàâèòå Â: ϕ(P): A* →Â*, ãäå P∈À*, ϕ(P)∈B*.

Ïðèìåð. Ïóñòü A={a, b}, B={a, b, c}. Îòîáðàæåíèå ϕ(P):

P→cPc îïðåäåëÿåò êîäèðîâàíèå ñëîâ â àëôàâèòå A ñëîâàìè â

àëôàâèòå B, íàïðèìåð, ab→cabc.

Îïðåäåëåíèå 15.6. Êîäèðîâàíèå íàçûâàåòñÿ áëî÷íûì, åñëè

êàæäîé áóêâå àëôàâèòà À ñîîòâåòñòâóåò ñëîâî â àëôàâèòå Â.

Ïðèìåð. Îòîáðàæåíèå ϕ(a): a → ac, ϕ(b): b → bc ÿâëÿåòñÿ áëî÷-

íûì êîäèðîâàíèåì. Íàïðèìåð, ϕ(ab) = acbc.

Ëþáûå ìíîæåñòâà ñëîâ â íåêîòîðîì àëôàâèòå A ìîæíî óïîðÿ-

äî÷èòü â ëåêñèêîãðàôè÷åñêîì ïîðÿäêå: åñëè R

, R

è x<y,

x, y∈A, òî R

< R

. Íàïðèìåð, ëåêñèêîãðàôè÷åñêîå óïîðÿ-

äî÷åíèå ñëîâ àëôàâèòà A={a, b} åñòü ïîñëåäîâàòåëüíîñòü: Λ,a, b,

aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, è ò.ä.

15.2.3. Ñëîâàðíûå ïðèìèòèâíî ðåêóðñèâíûå ôóíêöèè

Èñõîäíûå ôóíêöèè äëÿ àëôàâèòà A:

1. Íóëü-ôóíêöèÿ O(P)= Λ ïðåîáðàçóåò ëþáîå ñëîâî â ïóñòîå.

2. Äîáàâëåíèå ñèìâîëà x â êîíåö ñëîâà: N

(P) = Px, ãäå x ∈A.

3. Ïðîåêòèðóþùàÿ ôóíêöèÿ U

(P) = x

, ãäå j  êîëè÷åñòâî áóêâ â

ñëîâå P, x

 i-ÿ áóêâà ñëîâà P,  âûäåëÿåò çàäàííûé ñèìâîë â ñëîâå.

Ïîäñòàíîâêà. Ôóíêöèÿ f ïîëó÷åíà ñ ïîìîùüþ ïîäñòàíîâêè èç

ôóíêöèé g(P

,...,P

), h

,...,X

),, h

,...,X

), åñëè

f(X

,...,X

)=g(h

,..., X

),..., h

,..., X

)).

Ñõåìà ïðèìèòèâíîé ðåêóðñèè äëÿ àëôàâèòà A.

Ïóñòü g(X

,, X

), h

,, X

n+2

), h

,, X

n+2

),  íåêîòîðûå ôóíê-

öèè. Òîãäà ôóíêöèÿ f(X

, , X

n+1

) ïîëó÷åíà ïî ñõåìå ïðèìèòèâíîé

ðåêóðñèè, åñëè

f(X

, , X

, Λ) = g(X

, , X

f(X

, , X

, ξ) = h

, , X

, ξ, f(X

, , X

n+1

)), ξ∈A.

Ôóíêöèè, ïîëó÷åííûå èç èñõîäíûõ ñ ïîìîùüþ îïåðàöèé ïîäñòà-

íîâêè è ïðèìèòèâíîé ðåêóðñèè, ÿâëÿþòñÿ ïðèìèòèâíî ðåêóðñèâíûìè.

Ïðèìåð. Îáîçíà÷èì îïåðàöèþ êîíêàòåíàöèè con(X

, X

), X

X∈A

, A={a, b}, è ïîêàæåì, ÷òî îíà ÿâëÿåòñÿ ïðèìèòèâíî ðåêóð-

ñèâíîé.

con(X

, Λ) = X

= U

, Λ) = X

;

con(X

, a) = X

a = N

(con(X

, X

));

con(X

, b) = X

b = N

(con(X

, X

)).

264 265Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

15.2.4. Àññîöèàòèâíûå èñ÷èñëåíèÿ

Îïðåäåëåíèå 15.7. Ïîäñòàíîâêà ñëîâà P âìåñòî ïîäñëîâà Q â

ñëîâå W îçíà÷àåò çàìåíó Q íà P â ñëîâå W. Ïîäñòàíîâêà îáîçíà÷à-

åòñÿ: P→Q. Ïîäñòàíîâêà Q→P íàçûâàåòñÿ îáðàòíîé ïîäñòà-

íîâêîé. Ïîäñòàíîâêà Q → P íåïðèìåíèìà ê ñëîâó W, åñëè W íå

ñîäåðæèò Q.

Ïðèìåð. Ïóñòü äàí àëôàâèò À = {a, b} è ïîäñòàíîâêà ab→ba.

Òîãäà ðåçóëüòàò ïîñëåäîâàòåëüíîãî âûïîëíåíèÿ ýòîé ïîäñòàíîâêè

íàä ñëîâîì ababbbab áóäåò ñëåäóþùèì: 1.

ababbbab, 2. baabbbab,

ababbab, 4. bbaabbab, 5. bbababab, 6. bbbaabab, 7. bbbabaab, 8.

bbbbaa

ab, 9. bbbbaaba, 10. bbbbabaa, 11. bbbbbaaa.

Îïðåäåëåíèå 15.8. Ñîâîêóïíîñòü âñåõ ñëîâ àëôàâèòà A âìåñòå

ñ êîíå÷íîé ñèñòåìîé äîïóñòèìûõ ïîäñòàíîâîê íàçûâàåòñÿ

àññîöèàòèâíûì èñ÷èñëåíèåì.

Åñëè ñëîâî R ìîæåò áûòü ïðåîáðàçîâàíî â ñëîâî S ïóòåì îäíî-

êðàòíîãî ïðèìåíåíèÿ äîïóñòèìîé ïîäñòàíîâêè, òî è S ìîæåò áûòü

ïðåîáðàçîâàíî â R ïðèìåíåíèåì îáðàòíîé ïîäñòàíîâêè. Â ýòîì ñëó-

÷àå ñëîâà R è S íàçûâàþò ñìåæíûìè ñëîâàìè. Ïîñëåäîâàòåëüíîñòü

ñëîâ R

, R

,, R

, òàêèõ, ÷òî êàæäûå äâà ñëîâà R

, R

i+1

ñìåæíû, íàçû-

âàåòñÿ äåäóêòèâíîé öåïî÷êîé. Åñëè ñóùåñòâóåò äåäóêòèâíàÿ öåïî÷êà

îò ñëîâà R ê ñëîâó S, òî ñóùåñòâóåò è äåäóêòèâíàÿ öåïî÷êà îò S ê

R. Â ýòîì ñëó÷àå ñëîâà R è S íàçûâàþò ýêâèâàëåíòíûìè è îáîç-

íà÷àþò: R ~S. Î÷åâèäíî, ÷òî, åñëè R ~S, òî S ~R.

Îñíîâíîé ïðîáëåìîé àññîöèàòèâíûõ èñ÷èñëåíèé ÿâëÿåòñÿ ïðîá-

ëåìà ýêâèâàëåíòíîñòè ñëîâ: äëÿ ëþáûõ äâóõ ñëîâ R è S â àññîöèà-

òèâíîì èñ÷èñëåíèè îïðåäåëèòü, ñóùåñòâóåò ëè äåäóêòèâíàÿ öåïî÷êà

îò R ê S, èëè íåò. Â äàëüíåéøåì ìû ïîêàæåì, ÷òî ýòà ïðîáëåìà äëÿ

ïðîèçâîëüíîãî àññîöèàòèâíîãî èñ÷èñëåíèÿ àëãîðèòìè÷åñêè íåðàç-

ðåøèìà.

15.3. Ìàøèíà Òüþðèíãà

15.3.1. Îïðåäåëåíèå ìàøèíû Òüþðèíãà

Ìàøèíà Òüþðèíãà áûëà ïåðâîé àëãîðèòìè÷åñêîé ñõåìîé, ïðåä-

ëîæåííîé Òüþðèíãîì â êà÷åñòâå ìàòåìàòè÷åñêîãî îïðåäåëåíèÿ

àëãîðèòìà â 1937 ã. Ìàøèíà Òüþðèíãà ÿâëÿåòñÿ ãèïîòåòè÷åñêîé

ìàøèíîé: Òüþðèíã íå ñòàâèë çàäà÷è ñêîíñòðóèðîâàòü ýòî óñòðîé-

ñòâî. Êîíöåïöèÿ âû÷èñëèòåëüíîé ìàøèíû ïðèíàäëåæèò ôîí Íåé-

ìàíó, íî åå îñíîâîé ïîñëóæèëà ìàøèíà Òüþðèíãà. Çàäà÷à ìàøèíû

Òüþðèíãà  ïåðåðàáàòûâàòü âõîäíîå ñëîâî Wâ àëôàâèòå A â íåêîòî-

ðîå âûõîäíîå ñëîâî W*. Òàêèì îáðàçîì, ìàøèíà Òüþðèíãà ÿâëÿåòñÿ

çíàêîïåðåðàáàòûâàþùèì óñòðîéñòâîì.

Ìàøèíà Òüþðèíãà ñîñòîèò èç òðåõ ÷àñòåé.

1).Âíåøíÿÿ ïàìÿòü ìàøèíû Òüþðèíãà ïðåäñòàâëÿåòñÿ êàê áåñ-

êîíå÷íàÿ â îáå ñòîðîíû ëåíòà, ðàçáèòàÿ íà ÿ÷åéêè. Êîíå÷íîå ìíîæå-

ñòâî çíàêîâ A = {a, b, c,} îáðàçóåò âíåøíèé àëôàâèò ìàøèíû. Â

êàæäîé ÿ÷åéêå ìîæåò íàõîäèòüñÿ îäèí (è òîëüêî îäèí) ñèìâîë

âíåøíåãî àëôàâèòà. Èíôîðìàöèÿ çàïèñûâàåòñÿ íà ëåíòå â âèäå

ñëîâà â àëôàâèòå A. Âíåøíèé àëôàâèò ñîäåðæèò è ïóñòîé ñèìâîë

Λ. Ñ÷èòàåòñÿ, ÷òî êàæäàÿ ÿ÷åéêà ëåíòû õðàíèò ïóñòîé ñèìâîë, åñëè

â íåé íå çàïèñàí íèêàêîé äðóãîé ñèìâîë. Åñëè íà ëåíòå çàïèñàíî

ñëîâî, òî îíî îãðàíè÷åíî ñëåâà è ñïðàâà ïóñòûìè ñèìâîëàìè.

2).Ñ÷èòûâàþùàÿ ãîëîâêà ìàøèíû Òüþðèíãà â îäèí äèñêðåòíûé

ìîìåíò âðåìåíè îáîçðåâàåò îäíó ÿ÷åéêó è ìîæåò íàõîäèòüñÿ â

îäíîì èç âíóòðåííèõ ñîñòîÿíèé q

∈Q, ãäå Q  àëôàâèò âíóòðåííèõ

ñîñòîÿíèé. Ñ÷èòûâàþùàÿ ãîëîâêà ðàñïîçíàåò çàïèñàííûé â ÿ÷åéêå

ñèìâîë âíåøíåãî àëôàâèòà, çàïèñûâàåò âìåñòî íåãî äðóãîé ñèìâîë

(âîçìîæíî, òîò æå ñàìûé), ïåðåõîäèò â äðóãîå ñîñòîÿíèå (âîçìîæ-

íî â ïðåæíåå), ïîñëå ÷åãî ñäâèãàåòñÿ âïðàâî, âëåâî èëè îñòàåòñÿ

íà ìåñòå (ñì. ðèñ. 15.1). Äâèæåíèå ãîëîâêè ìàøèíû Òüþðèíãà áóäåì

îáîçíà÷àòü ñèìâîëàìè: Ï  âïðàâî, Ë âëåâî, Í  íà ìåñòå.

Ðèñ. 15.1. Ñõåìà ìàøèíû Òüþðèíãà.

Ìíîæåñòâî âíóòðåííèõ ñîñòîÿíèé Q ïðåäñòàâëÿåò ñîáîé âíóò-

ðåííþþ ïàìÿòü ìàøèíû Òüþðèíãà: êîãäà ìàøèíà â ðàçíûõ ñîñòîÿ-

íèÿõ âèäèò îäèí è òîò æå ñàìûé ñèìâîë, îíà ìîæåò âûïîëíèòü

ðàçíûå äåéñòâèÿ. Ãîâîðÿò, ÷òî â äàííûé ìîìåíò âðåìåíè ãîëîâêà

ìàøèíû îáîçðåâàåò îïðåäåëåííóþ ÿ÷åéêó ëåíòû. Òàêèì îáðàçîì,

â êàæäûé äèñêðåòíûé ìîìåíò âðåìåíè ñîñòîÿíèå ìàøèíû õàðàêòå-

ðèçóåòñÿ ñëîâîì, çàïèñàííûì íà ëåíòå, ïîëîæåíèåì ãîëîâêè è åå

ñîñòîÿíèåì. Ñëîâî, çàïèñàííîå íà ëåíòå, âìåñòå ñ ïîëîæåíèåì ãîëîâ-

êè ìàøèíû Òüþðèíãà, íàõîäÿùåéñÿ â îäíîì èç ñâîèõ âíóòðåííèõ

ñîñòîÿíèé, áóäåì íàçûâàòü êîíôèãóðàöèåé ìàøèíû Òüþðèíãà.

3).Ñëåäóþùàÿ ÷àñòü ìàøèíû Òüþðèíãà  ýòî ïðîãðàììà,

óïðàâëÿþùàÿ ãîëîâêîé è ñîñòîÿùàÿ èç êîìàíä âèäà:

→bq

ξ, ãäå ξ∈{Ë, Ï, Í}, q

∈ Q, a, b∈A.

266 267Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

Â ðåçóëüòàòå âûïîëíåíèÿ ýòîé êîìàíäû ñèìâîë a íà ëåíòå áóäåò

çàìåíåí ñèìâîëîì b, ãîëîâêà ñäâèíåòñÿ âëåâî, âïðàâî èëè îñòàíåòñÿ

íà ìåñòå â çàâèñèìîñòè îò ξ è âíóòðåííåå ñîñòîÿíèå èçìåíèòñÿ ñ q

íà q

. Ïîñëå ýòîãî áóäåò âûïîëíÿòüñÿ ñëåäóþùàÿ êîìàíäà. Ïðèìåíè-

ìîñòü òîé èëè èíîé êîìàíäû îïðåäåëÿåòñÿ êîíôèãóðàöèåé íà ëåíòå

â òåêóùèé ìîìåíò âðåìåíè. Êîìàíäà âèäà aq

→bq!ξ, ãäå q! (èëè

ïðîñòî «!»)  çàêëþ÷èòåëüíîå ñîñòîÿíèå, íàçûâàåòñÿ çàêëþ÷èòåëü-

íîé êîìàíäîé è âûçûâàåò îêîí÷àíèå (îñòàíîâ) ðàáîòû ìàøèíû

Òüþðèíãà. Ïðè âûïîëíåíèè çàêëþ÷èòåëüíîé êîìàíäû ñèìâîë a

çàìåíÿåòñÿ íà ñèìâîë b, ãîëîâêà ñäâèãàåòñÿ âëåâî, âïðàâî èëè îñòà-

åòñÿ íà ìåñòå, è ïåðåõîäèò â çàêëþ÷èòåëüíîå ñîñòîÿíèå.

Ïîñëåäîâàòåëüíîñòü êîìàíä çàäàåò àëãîðèòì ïåðåðàáîòêè ñëîâà.

Äëÿ ðàáîòû àëãîðèòìà íåîáõîäèìî çàäàòü íà÷àëüíóþ êîíôèãóðà-

öèþ: íà ëåíòó ìàøèíû Òüþðèíãà çàïèñûâàåòñÿ èñõîäíîå ñëîâî W

â àëôàâèòå A è óêàçûâàåòñÿ, êàêîé ñèìâîë îáîçðåâàåò ãîëîâêà ìàøè-

íû Òüþðèíãà â íà÷àëüíîì ñîñòîÿíèè q

. Ðàáîòà ìàøèíû Òüþðèíãà

ïðîèñõîäèò ïî òàêòàì, èëè ïî øàãàì. Íà êàæäîì øàãå âûïîëíÿåòñÿ

îäíà êîìàíäà, â ðåçóëüòàòå êîòîðîé êîíôèãóðàöèÿ íà ëåíòå ìåíÿ-

åòñÿ. Ïðè ðàáîòå ìàøèíû Òüþðèíãà âîçìîæíî ðàñøèðåíèå âíåø-

íåãî àëôàâèòà A âñïîìîãàòåëüíûìè ñèìâîëàìè, êîòîðûå ïîñëå ïåðå-

ðàáîòêè ñëîâà çàìåíÿþòñÿ ñèìâîëàìè àëôàâèòà A èëè ñòèðàþòñÿ.

Â ïðîöåññå ðàáîòû âîçìîæíû äâå ñèòóàöèè:

1. Ìàøèíà Òüþðèíãà ïåðåðàáàòûâàåò èñõîäíîå ñëîâî P â R è îñòà-

íàâëèâàåòñÿ; òîãäà ãîâîðÿò, ÷òî äàííàÿ ìàøèíà ïðèìåíèìà ê ñëîâó P.

2. Ìàøèíà Òüþðèíãà, íà÷èíàÿ ðàáîòó ñî ñëîâà P, íèêîãäà íå

îñòàíîâèòñÿ; òîãäà ãîâîðÿò, ÷òî äàííàÿ ìàøèíà Òüþðèíãà íå ïðèìå-

íèìà ê ñëîâó P.

Ïðèìåðû.

1.Ïóñòü çàäàí àëôàâèò A = {|, *}, èñõîäíîå ñëîâî â êîòîðîì ìîæåò

èìåòü âèä: P= |||*|*||. Â íà÷àëüíîì ñîñòîÿíèè q

ìàøèíà

îáîçðåâàåò êðàéíèé ëåâûé ñèìâîë. Ìàøèíà Òüþðèíãà äîëæíà

ïðåîáðàçîâàòü ýòî ñëîâî â ïóñòîå ñëîâî, ò.å. äîëæíà ðåàëèçîâûâàòü

àëãîðèòì âû÷èñëåíèÿ íóëü-ôóíêöèè: O(X) = Λ. Äëÿ ýòîãî îíà

äîëæíà, äâèãàÿñü ñëåâà íàïðàâî, çàìåíèòü êàæäûé ñèìâîë íà ëåíòå

íà ïóñòîé ñèìâîë è îñòàíîâèòüñÿ, êàê òîëüêî óâèäèò êðàéíèé ñïðàâà

ïóñòîé ñèìâîë (òàáë. 15.1).

Ïðîãðàììó äëÿ ìàøèíû Òüþðèíãà îáû÷íî

çàïèñûâàþò â âèäå òàáëèöû, ñòðîêè êîòî-

ðîé ïîìå÷àþòñÿ ñèìâîëàìè âíåøíåãî àë-

ôàâèòà, ñòîëáöû  ñèìâîëàìè àëôàâèòà

ñîñòîÿíèé. Êàæäîé ñòðîêå è ñòîëáöó ñîîò-

âåòñòâóåò îäíà êîíôèãóðàöèÿ íà ëåíòå (ëå-

âàÿ ÷àñòü êîìàíäû), â ñîîòâåòñòâóþùåé

Òàáëèöà 15.1.

A Q q

| Λ q

* Λ q

Λ !

Òàáëèöà 15.2.

|| q

Λ |! Í

êëåòêå çàïèñûâàåòñÿ ïðàâàÿ ÷àñòü êîìàíäû, óêàçûâàþùàÿ, êàê

äîëæíà èçìåíèòüñÿ êîíôèãóðàöèÿ íà ëåíòå. Íåêîòîðûå êîíôèãó-

ðàöèè ìîãóò íèêîãäà íå âîçíèêíóòü â ïðîöåññå ïåðåðàáîòêè ñëîâà,

òîãäà ñîîòâåòñòâóþùèå èì êëåòêè îñòàþòñÿ ïóñòûìè.

2.Ðàññìîòðèì ïðîãðàììó äëÿ àëãîðèòìà äîáàâëåíèÿ ñèìâîëà | ê

ñëîâó â òîì æå àëôàâèòå. Ïóñòü èñõîäíîå ñëîâî èìååò âèä: P= |||.

Ýòî ñëîâî ìîæíî ðàññìàòðèâàòü êàê ÷èñëî 3, à äîáàâëåíèå ñèìâîëà

|  êàê âû÷èñëåíèå ôóíêöèè f(X) = X+1 â óíàðíîé ñèñòåìå

ñ÷èñëåíèÿ. Ïðîãðàììà äëÿ âû÷èñëåíèÿ ýòîé ôóíêöèè íà ñàìîì

äåëå î÷åíü ïðîñòà: ãîëîâêà ìàøèíû ïðîïóñêàåò âñå ñèìâîëû |, äâèãà-

ÿñü ñëåâà íàïðàâî, è, äîéäÿ äî êðàéíåãî ïðàâîãî ïóñòîãî ñèìâîëà

Λ, äîïèñûâàåò òóäà åùå îäèí ñèìâîë |, ïîñëå ÷åãî îñòàíàâëèâàåòñÿ

â ñâîåì çàêëþ÷èòåëüíîì ñîñòîÿíèè (ñì. òàáë. 15.2).

Î÷åâèäíî, ÷òî òî÷íî òàê æå ìîæíî ñîñòàâèòü ïðîã-

ðàììó äëÿ äîáàâëåíèÿ ëþáîãî ñèìâîëà àëôàâèòà

A â êîíöå ñëîâà, ò.å. òàêîé àëãîðèòì ðåàëèçóåò

èñõîäíóþ ðåêóðñèâíóþ ôóíêöèþ N

(X)= Xy, ãäå

y∈ A.

Òðåòüÿ èñõîäíàÿ ôóíêöèÿ: ôóíêöèÿ ïðîåêöèè

(X) = x

, åñòü íå ÷òî èíîå, êàê ýëåìåíòàðíîå äåéñòâèå ìàøèíû

Òüþðèíãà  ðàñïîçíàâàíèå ñèìâîëà.

3.Ðàññìîòðèì òåïåðü âû÷èñëåíèå áîëåå ñëîæíîé ôóíêöèè:

F(X,Y)= X+Y, ãäå X, Y  ñëîâà, çàäàííûå â óíàðíîé ñèñòåìå

ñ÷èñëåíèÿ. Ïóñòü èñõîäíàÿ êîíôèãóðàöèÿ íà ëåíòå çàäàíà òàê, ÷òî

â íà÷àëüíîì ñîñòîÿíèè ãîëîâêà îáîçðåâàåò êðàéíèé ëåâûé ñèìâîë

|, (ñì. ðèñ. 15.2), ñëîâî íà ëåíòå ïðåäñòàâëÿåò ñîáîé äâà ÷èñëà, ðàç-

äåëåííûå ñèìâîëîì *.

Ðèñ. 15. 2. Âû÷èñëåíèå ôóíêöèè F(X,Y) = X+Y/

Ñîñòàâèì ìàøèíó Òüþðèíãà, ðàáîòàþùóþ ïî ñëåäóþùåìó àëãî-

ðèòìó. Â íà÷àëüíîì ñîñòîÿíèè q

ìàøèíà âèäèò êðàéíþþ ëåâóþ

ïàëî÷êó, ñòèðàåò åå è, ïåðåéäÿ â ñîñòîÿíèå q

, äâèæåòñÿ âïðàâî,

ïîêà íå óâèäèò êðàéíèé ñïðàâà ïóñòîé ñèìâîë. Òîãäà íà ìåñòå

ïóñòîãî ñèìâîëà ìàøèíà çàïèñûâàåò ïàëî÷êó, ïåðåõîäèò â íîâîå

ñîñòîÿíèå q

è äâèæåòñÿ âëåâî â òîì æå ñîñòîÿíèè q

, ïðîïóñêàÿ

âñå ñèìâîëû, ïîêà íå äîéäåò äî êðàéíåãî ñëåâà ïóñòîãî ñèìâîëà.

268 269Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

Òîãäà ìàøèíà îñòàâëÿåò åãî íà ìåñòå, ñäâèãàåòñÿ âïðàâî è ïåðåõîäèò

â ñîñòîÿíèå q

. Ïîñëå ýòîãî ïðîöåññ ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà â

ñîñòîÿíèè q

ìàøèíà íå óâèäèò ñèìâîë *. Ýòî îçíà÷àåò, ÷òî óæå

âñå ïàëî÷êè ïåðåíåñåíû ñëåâà íàïðàâî, ìàøèíà ìîæåò ñòåðåòü

ñèìâîë * è îñòàíîâèòüñÿ, ò.å. ïåðåéòè â çàêëþ÷èòåëüíîå ñîñòîÿíèå.

Ïðîãðàììà äëÿ ìàøèíû ïðåäñòàâëåíà â òàáëèöå 15.3.

Íåòðóäíî çàìåòèòü, ÷òî ïðîöåññ âû÷èñëåíèÿ ñóììû ðåêóðñèâåí:

îí îñíîâàí íà ïðåäûäóùåì àëãîðèòìå, êîãäà ê îäíîìó èç ñëàãàåìûõ

(â äàííîì ñëó÷àå, ê ïðàâîìó ñëîâó) äîáàâëÿåòñÿ ñòîëüêî åäèíèö,

ñêîëüêî èõ ñîäåðæèòñÿ â äðóãîì ñëàãàåìîì. Äëÿ ñðàâíåíèÿ âîñïðî-

èçâåäåì ïðîöåññ âû÷èñëåíèÿ ñóììû äâóõ ñëàãàåìûõ ñ ïîìîùüþ

ðåêóðñèâíîé ôóíêöèè:

f(X, 0) = X,

f(X, Y+1) = f(X, Y) + 1.

f(2, 3) = f(2, 2) + 1 = (f(2, 1) + 1) + 1 = ((f(2, 0) + 1) + 1) + 1.

Íà ýòîì çàâåðøàåòñÿ ïðÿìîé õîä ðåêóðñèè: ñîñòàâëåíà ðåêóð-

ñèâíàÿ ñõåìà âû÷èñëåíèÿ ôóíêöèè. Òåïåðü îáðàòíûé õîä ðåêóðñèè

âû÷èñëÿåò åå çíà÷åíèå: ((2 + 1) + 1) + 1 = (3 + 1) + 1 = 4 + 1 = 5.

15.3.2. Ðàñïîçíàþùàÿ ìàøèíà Òüþðèíãà

Ðàñïîçíàþùàÿ ìàøèíà Òüþðèíãà  ýòî ìàøèíà, êîòîðàÿ âû÷èñ-

ëÿåò ïðåäèêàò P(W) òàêèì îáðàçîì, ÷òî åñëè P(W) = T, òî ìàøèíà

îñòàíàâëèâàåòñÿ â ñîñòîÿíèè «äà!», à åñëè P(W)=F, òî â ñîñòîÿíèè

«íåò!».

Íàïðèìåð, ìàøèíà, ðàñïîçíàþùàÿ

÷åòíîñòü ÷èñëà, ïðåäñòàâëåííîãî â

óíàðíîé ñèñòåìå ñ÷èñëåíèÿ, ïðèâåäåíà

â òàáëèöå 15.4. Äâèãàÿñü ñëåâà íàïðàâî,

ìàøèíà îñòàíàâëèâàåòñÿ íà ïóñòîì

ñèìâîëå â ñîñòîÿíèè «äà!», åñëè ÷èñëî

÷åòíîå, è â ñîñòîÿíèè «íåò!», åñëè íå÷åòíîå.

15.3.3. Êîìïîçèöèÿ ìàøèí Òüþðèíãà

Ìîæíî âûäåëèòü íåêîòîðûé íàáîð ýëåìåíòàðíûõ àëãîðèòìîâ,

èç êîòîðûõ ìîæíî ïîëó÷àòü áîëåå ñëîæíûå àëãîðèòìû ïî ïðàâèëàì

êîìïîçèöèè ìàøèí Òüþðèíãà. Ìîæíî ïîêàçàòü, ÷òî ýëåìåíòàðíûå

ôóíêöèè:

Òàáëèöà 15.3.

| Λ q

Ï| q

* Λ ! Ï * q

Ï * q

ΛΛ ! Í| q

Ë Λ q

Òàáëèöà 15.4.

|| q

Ï | q

ΛΛ äà! Λ íåò!

•íóëü-ôóíêöèÿ O(X)= Λ;

•äîáàâëåíèå ñèìâîëà ζ: Nζ(X) = Xζ, ãäå ζ ∈A;

•ïðîåêòèðóþùàÿ ôóíêöèÿ U

(X) = x

;

•òîæäåñòâåííîå ïðåîáðàçîâàíèå Ò(X) = X;

•àëãîðèòì êîïèðîâàíèÿ ñëîâà Copy(X) = X*X;

•çàìåíÿþùèé àëãîðèòì Rep

(x), ãäå x

, x

∈ AÈB, è B âñïîìîãà-

òåëüíûé àëôàâèò (àëãîðèòì çàìåíÿåò ñèìâîë x

íà ñèìâîë x

â ñëîâåX),

âû÷èñëèìû íà ìàøèíå Òüþðèíãà. Èç ýòèõ ýëåìåíòàðíûõ àëãîðèò-

ìîâ ìîæíî îáðàçîâûâàòü áîëåå ñëîæíûå ñ ïîìîùüþ êîìïîçèöèè

ìàøèí Òüþðèíãà.

1. Ïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ. Ïóñòü Ì1 è Ì2  äâå ìàøèíû

Òüþðèíãà. Òîãäà, îòîæäåñòâèâ çàêëþ÷èòåëüíîå ñîñòîÿíèå ìàøèíû

Ì1 ñ íà÷àëüíûì ñîñòîÿíèåì ìàøèíû Ì2 è, ïðè íåîáõîäèìîñòè,

ïåðåíóìåðîâàâ âíóòðåííèå ñîñòîÿíèÿ ìàøèíû Ì2, ïîëó÷èì íîâóþ

ìàøèíó Òüþðèíãà, êîòîðàÿ, íà÷èíàÿ ðàáîòó ñî ñëîâà W, ñíà÷àëà

áóäåò âûïîëíÿòü íàä íèì ïðåîáðàçîâàíèÿ, âûïîëíÿåìûå ìàøèíîé

Ì1, à çàòåì áóäåò ðàáîòàòü êàê ìàøèíà Ì2. Ïîñëåäîâàòåëüíóþ

êîìïîçèöèþ ìàøèí Òüþðèíãà îáîçíà÷èì: M1°Ì2=M2(Ì1(W)).

Òàêèì îáðàçîì, ïîñëåäîâàòåëüíàÿ êîìïîçèöèÿ ìàøèí Òüþðèíãà

îñóùåñòâëÿåò ñóïåðïîçèöèþ ôóíêöèé.

2. Ïàðàëëåëüíàÿ êîìïîçèöèÿ. Åñëè íà ëåíòå çàïèñàíî ñëîâî W,

êîòîðîå ïðåäñòàâèìî êàê êîíêàòåíàöèÿ äâóõ ñëîâ Ð||R, òî ìîæíî

ñîñòàâèòü òàêóþ ìàøèíó Òüþðèíãà, êîòîðàÿ áóäåò ðàáîòàòü êàê

ìàøèíà M1 íàä ïîäñëîâîì P è êàê ìàøèíà M2 íàä ïîäñëîâîì R, à

çàòåì îñóùåñòâèò êîíêàòåíàöèþ ðåçóëüòàòîâ: M1(P)||M2(R).

3. Ðàçâåòâëÿþùàÿñÿ êîìïîçèöèÿ. Åñëè ñóùåñòâóþò ìàøèíû

Òüþðèíãà M1 è M2 è ðàñïîçíàþùàÿ ìàøèíà Òüþðèíãà P, òî ìîæíî

ñîñòàâèòü òàêóþ ìàøèíó Òüþðèíãà M, ÷òî, íà÷èíàÿ ðàáîòó ñî ñëîâà

W, ìàøèíà Òüþðèíãà ðàáîòàåò ñíà÷àëà êàê ðàñïîçíàþùàÿ ìàøèíà

P(W). Åñëè îíà çàêàí÷èâàåò îáðàáîòêó èñõîäíîãî ñëîâà â ñîñòîÿíèè

«äà!», òî äàëåå ðàáîòàåò ìàøèíà M1(W), à åñëè â ñîñòîÿíèè «íåò!»,

òî ìàøèíà M2(W) (ñì. ðèñ. 15.3).

4.Öèêëè÷åñêàÿ êîìïîçèöèÿ. Ìîæíî ïîñòðîèòü òàêóþ ìàøèíó

Òüþðèíãà M, êîòîðàÿ, íà÷èíàÿ ðàáîòó ñî ñëîâà W

, ñíà÷àëà ðàáîòàåò

êàê ðàñïîçíàþùàÿ ìàøèíà P, âû÷èñëÿþùàÿ ïðåäèêàò P(W

). Åñëè

îíà çàâåðøàåò ñâîþ ðàáîòó â ñîñòîÿíèè «äà», òî äàëåå îíà ðàáîòàåò

êàê ìàøèíà Òüþðèíãà M1 íàä ñëîâîì W

è çàâåðøàåò ñâîþ ðàáîòó

ñ âûõîäíûì ñëîâîì W

. Çàòåì óïðàâëåíèå ïåðåäàåòñÿ ðàñïîçíàþùåé

ìàøèíå P, âû÷èñëÿþùåé ïðåäèêàò P(W

), è òàê äàëåå, äî òåõ ïîð,

ïîêà ðàñïîçíàþùàÿ ìàøèíà Òüþðèíãà P íå îñòàíîâèòñÿ â ñîñòîÿíèè

«íåò» íà ñëîâå W

. Òîãäà ìàøèíà Òüþðèíãà M îñòàíàâëèâàåòñÿ â

ñâîåì çàêëþ÷èòåëüíîì ñîñòîÿíèè (ñì. ðèñ. 15.4).

270 271Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

Áûëî ìàòåìàòè÷åñêè äîêàçàíî, ÷òî äëÿ ðåàëèçàöèè ëþáûõ àëãî-

ðèòìîâ äîñòàòî÷íî ýòèõ ÷åòûðåõ ñòðóêòóð

15.4. Íîðìàëüíûå àëãîðèòìû Ìàðêîâà

15.4.1. Ðàáîòà àëãîðèòìà Ìàðêîâà

Îïðåäåëåíèå 15.12. Íîðìàëüíûé àëãîðèòì Ìàðêîâà  ýòî

êîíå÷íûé óïîðÿäî÷åííûé íàáîð ïîäñòàíîâîê âèäà P

→Q

, èëè

→.Q

i = 1, 2, , n. P

→Q

 îáû÷íàÿ ïîäñòàíîâêà, êîòîðàÿ

îçíà÷àåò, ÷òî êðàéíåå ëåâîå âõîæäåíèå ïîäñëîâà P

â ñëîâå W

çàìåíÿåòñÿ íà Q

, P

→.Q

 çàêëþ÷èòåëüíàÿ ïîäñòàíîâêà, ò.å.

ïîñëå åå âûïîëíåíèÿ ðàáîòà àëãîðèòìà çàâåðøàåòñÿ.

Èñõîäíîå ñëîâî W∈À* ïåðåðàáàòûâàåòñÿ ñ ïîìîùüþ àëãîðèòìà

ñëåäóþùèì îáðàçîì. Íà÷èíàÿ ñ ïåðâîé ïîäñòàíîâêè, èùåòñÿ ïåðâîå

ëåâîå âõîæäåíèå ïîäñëîâà P

â ñëîâå W. Åñëè îíî íàéäåíî, òî îíî

çàìåíÿåòñÿ íà Q

, ïîñëå ÷åãî ñïèñîê ïîäñòàíîâîê ïðîñìàòðèâàåòñÿ

ñ ñàìîãî íà÷àëà. Åñëè æå âõîæäåíèÿ P

íå áûëî íàéäåíî, òî âûáè-

ðàåòñÿ ñëåäóþùàÿ ïîäñòàíîâêà. Åñëè íà íåêîòîðîì øàãå áûëà âû-

ïîëíåíà çàêëþ÷èòåëüíàÿ ïîäñòàíîâêà, òî ïðîöåññ ïåðåðàáîòêè ñëîâà

çàâåðøàåòñÿ è òîãäà ãîâîðÿò, ÷òî àëãîðèòì ïðèìåíèì ê äàííîìó

ñëîâó. Ìîæåò îêàçàòüñÿ, ÷òî ïðîöåññ íå çàâåðøàåòñÿ, ò.å. íè îäíà

èç çàêëþ÷èòåëüíûõ ïîäñòàíîâîê íå ïðèìåíÿëàñü â ïðîöåññå ïåðåðà-

áîòêè ñëîâà. Â ýòîì ñëó÷àå ãîâîðÿò, ÷òî àëãîðèòì íå ïðèìåíèì ê

äàííîìó ñëîâó.

Ïðèìåðû.

1.Íîðìàëüíûé àëãîðèòì Ìàðêîâà äëÿ ñëîæåíèÿ äâóõ ÷èñåë â óíàð-

íîé ñèñòåìå, ò.å. àëãîðèòì âû÷èñëÿåò ôóíêöèþ f(X, Y) = X+Y â

àëôàâèòå A = {|, *}. Àëãîðèòì ñîñòîèò èç äâóõ ïîäñòàíîâîê:

1. * | →|*

2. * →. L

Ðèñ. 15.3. Ðàçâåòâëÿþùàÿñÿ

êîìïîçèöèÿ ìàøèí Òüþðèíãà.

Ðèñ. 15.4. Öèêëè÷åñêàÿ

êîìïîçèöèÿ ìàøèí Òüþðèíãà.

Êîìïîçèöèÿ ìàøèí Òüþðèíãà çàêëþ÷àåò â ñåáå îñíîâíóþ èäåþ ñòðóêòóðíîãî

ïðîãðàììèðîâàíèÿ. Èìåííî Òüþðèíãó ïðèíàäëåæèò äîêàçàòåëüñòâî ïîëíîòû

ýòèõ ÷åòûðåõ ñõåì êîìïîçèöèè äëÿ ðåàëèçàöèè ëþáîãî, ñêîëü óãîäíî ñëîæíîãî

àëãîðèòìà.

Ïðîöåññ ïåðåðàáîòêè ñëîâà çàêëþ÷àåòñÿ â ñëåäóþùåì (â ñêîáêàõ

óêàçàí íîìåð ïðèìåíÿåìîé ïîäñòàíîâêè):

| | |* | | | | ⇒ (1) | | | |* | | | ⇒ (1) | | | | |* | | ⇒ (1) | | | | | |* | ⇒ (1) | | | | | | |*⇒

⇒ (2) | | | | | | |

2. Àëãîðèòì îáðàùåíèÿ ñëîâà â àëôàâèòå A={a, b, c,, z}. Íàïðèìåð,

èñõîäíîå ñëîâî abc îáðàùàåòñÿ â ñëîâî cba. Íèæå ïðèâåäåí ñïèñîê

ïîäñòàíîâîê, â êîòîðîì ïåðåìåííûå x, y îáîçíà÷àþò ëþáîé ñèìâîë

èç àëôàâèòà A, ãðå÷åñêèìè ñèìâîëàìè α, β îáîçíà÷åíû âñïîìîãà-

òåëüíûå ñèìâîëû, íåîáõîäèìûå äëÿ ðàáîòû àëãîðèòìà.

1. αα → β

2. βx → xβ

3. βα → β

4. β → Λ

5. αyx → xαy

6. Λ→α

Äëÿ ñëîâà abc ïðîöåññ ðàáîòû àëãîðèòìà çàêëþ÷àåòñÿ â ñëåäóþùåì:

Λabc ⇒(6) αabc ⇒(5) bαac ⇒(5) bcαa ⇒(6)αbcαa⇒(5)cαbαa⇒

⇒(6) αcαbαa ⇒(6) ααcαbαa ⇒(1) βcαbαa ⇒(2) cβαbαa⇒

⇒(3)cβbαa ⇒(2) cbβαa ⇒(3) cbβa ⇒(2) cbaβ ⇒(4) cba.

15.4.2. Ýêâèâàëåíòíîñòü íîðìàëüíûõ àëãîðèòìîâ

èìàøèíû Òüþðèíãà

Òåîðåìà 15.1. Ïóñòü M  ìàøèíà Òüþðèíãà ñ âíåøíèì àëôàâè-

òîì A è âíóòðåííèì àëôàâèòîì Q. Òîãäà ñóùåñòâóåò íîðìàëüíûé

àëãîðèòì Ìàðêîâà ñ àëôàâèòîì À∪Q, ýêâèâàëåíòíûé äàííîé

ìàøèíå Òüþðèíãà.

Äîêàçàòåëüñòâî. Ïóñòü äàíà ìàøèíà Òüþðèíãà M ñ âíåøíèì

àëôàâèòîì À={x

}, ãäå i=1, 2, , n, è âíóòðåííèì àëôàâèòîì

Q={q

}, j = 0, 1, , m. Äâóìåðíóþ êîíôèãóðàöèþ íà ëåíòå ìîæíî

çàïèñàòü êàê ïîñëåäîâàòåëüíîñòü x

q

i+1

x

, ãäå ñèìâîë òåêó-

ùåãî ñîñòîÿíèÿ q

ñòîèò ïåðåä ñèìâîëîì, êîòîðûé îáîçðåâàåò ãîëîâ-

êà ìàøèíû Òüþðèíãà â äàííûé ìîìåíò âðåìåíè. Ìû ïîëó÷èì ñëîâî

â àëôàâèòå À∪Q. Òîãäà ìîæíî çàìåíèòü êàæäóþ êîìàíäó ìàøèíû

Òüþðèíãà íà ïîñëåäîâàòåëüíîñòü ïîäñòàíîâîê ñëåäóþùèì îáðàçîì.

1.Êîìàíäà âèäà q

→ x

H çàìåíÿåòñÿ ïîäñòàíîâêîé q

→ q

2.Êîìàíäà âèäà q

→ x

Ï çàìåíÿåòñÿ ñïèñêîì ïîäñòàíîâîê

i+1

→ x

i+1

, ∀x

∈A.

3.Êîìàíäà âèäà q

→ x

Ë çàìåíÿåòñÿ ñïèñêîì ïîäñòàíîâîê

i-1

→ q

i-1

, ∀x

∈A.

4.Äîïèñûâàåòñÿ ïîäñòàíîâêà q

→. Λ, ãäå q

 êîíå÷íîå ñîñòîÿíèå.

5.Â êîíåö ñïèñêà ââîäèòñÿ ïîäñòàíîâêà Λ → q

272 273Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

Òàáëèöà 15.5.

|| q

Λ | ! H

** q

Òàêèì îáðàçîì, åñëè èìååòñÿ íåêîòîðàÿ ïðîãðàììà äëÿ ìàøèíû

Òüþðèíãà, òî ñ ïîìîùüþ ýòèõ ïÿòè ïðàâèë åå ìîæíî ïðåîáðàçîâàòü

â àëãîðèòì Ìàðêîâà.

Ïðèìåð. Ïóñòü çàäàíà ïðîãðàììà äëÿ ìàøèíû Òüþðèíãà â

àëôàâèòå À = {|, *} (òàáë. 15. 5).

Íîðìàëüíûé àëãîðèòì Ìàðêîâà, ýêâèâàëåíòíûé

ýòîé ìàøèíå Òüþðèíãà, èìååò âèä:

1.q

| | → | q

2.q

|* → | q

3.q

| Λ → | q

4.q

Λ →. |

5.Λ → q

Ïðîöåññ ïåðåðàáîòêè ñëîâà: | | * | ⇒ q

| | * | ⇒ | q

| * | ⇒ | | q

* |⇒

⇒ | | *q

|⇒ | | * |q

Λ ⇒ | | * | |.

Òåîðåìà 15.2. (îáðàòíàÿ). Äëÿ êàæäîãî íîðìàëüíîãî àëãîðèòìà

Ìàðêîâà ìîæíî ïîñòðîèòü ýêâèâàëåíòíóþ åìó ìàøèíó Òüþðèíãà.

Ñõåìà äîêàçàòåëüñòâà.

1.Ïîñòðîèòü ìàøèíó Òüþðèíãà, îñóùåñòâëÿþùóþ ïîèñê ïîäñëîâà

Ð â ñëîâå W; ãîëîâêà ìàøèíû Òüþðèíãà, â ðåçóëüòàòå, áóäåò ñòîÿòü íà

ïåðâîì ñèìâîëå ïîäñëîâà P.

2.Ïîñòðîèòü ìàøèíó Òüþðèíãà, çàìåíÿþùóþ ïîäñëîâî P íà

ñëîâî Q (äëÿ êàæäîé ïîäñòàíîâêè àëãîðèòìà Ìàðêîâà ìîæíî ïî-

ñòðîèòü ìàøèíó Òüþðèíãà, âûïîëíÿþùóþ åå).

Ïîëó÷åííàÿ êîìïîçèöèÿ ìàøèí Òüþðèíãà áóäåò âûïîëíÿòü òó

æå ïðîöåäóðó ïåðåðàáîòêè ñëîâ, ÷òî è àëãîðèòì Ìàðêîâà.

Äëÿ íîðìàëüíîãî àëãîðèòìà Ìàðêîâà ìîæíî îïðåäåëèòü

ðàñïîçíàþùèé àëãîðèòì Ìàðêîâà êàê âû÷èñëÿþùèé íåêîòîðûé

ïðåäèêàò è èìåþùèé çàêëþ÷èòåëüíûå ïîäñòàíîâêè Ð→

äà

Q è

Ð→

íåò

Q; àíàëîãè÷íî ìîæíî îïðåäåëèòü ïîíÿòèå êîìïîçèöèè (ïî

òåì æå ñõåìàì, ÷òî è äëÿ ìàøèíû Òüþðèíãà).

Ïðèâåäåííûå âûøå äâå òåîðåìû óòâåðæäàþò ýêâèâàëåíòíîñòü

ìàøèíû Òüþðèíãà è íîðìàëüíîãî àëãîðèòìà Ìàðêîâà. Îòñþäà

ñëåäóåò, ÷òî, åñëè ïîñòðîåíà ìàøèíà Òüþðèíãà äëÿ ðåøåíèÿ êàêîé-

ëèáî çàäà÷è, ò.å., åñëè ôóíêöèÿ âû÷èñëèìà ïî Òüþðèíãó, òî äëÿ

íåå ñóùåñòâóåò è íîðìàëüíûé àëãîðèòì Ìàðêîâ, ò.å. îíà âû÷èñëèìà

ïî Ìàðêîâó, è íàîáîðîò, åñëè ôóíêöèÿ âû÷èñëèìà ïî Ìàðêîâó, òî

îíà Âû÷èñëèìà ïî Òüþðèíãó. Èíûìè ñëîâàìè, êëàññû ôóíêöèé,

âû÷èñëèìûõ ïî Òüþðèíãó è ïî Ìàðêîâó, ñîâïàäàþò. Ðàññìîòðèì

òåïåðü, êàêîé êëàññ ôóíêöèé âû÷èñëèì ïî Òüþðèíãó.

15.4.3. Êëàññ ôóíêöèé, âû÷èñëèìûõ ïî Òüþðèíãó

Òåîðåìà 15.3. Ôóíêöèÿ F(õ

, õ

, õ

) ðåêóðñèâíà (÷àñòè÷íî ðå-

êóðñèâíà) òîãäà è òîëüêî òîãäà, êîãäà îíà âû÷èñëèìà ïî Òüþðèíãó.

Äîêàçàòåëüñòâî.

1. Âñÿêàÿ ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà ïî Òüþðèíãó.

O(X)=Λ  íóëü-ôóíêöèÿ âû÷èñëèìà íà ìàøèíå Òüþðèíãà,

êîòîðàÿ óíè÷òîæàåò ëþáîå ñëîâî íà ëåíòå.

N(X)=X+1  âû÷èñëèìà íà ìàøèíå Òüþðèíãà, êîòîðàÿ ê

ëþáîìó ñëîâó W íà ëåíòå äîïèñûâàåò çàäàííûé ñèìâîë a :Wa .

(X)= x



ôóíêöèÿ ïðîåêöèè, êîòîðàÿ â ñëîâå W âûäåëÿåò

ñèìâîë x

, âû÷èñëèìà íà ìàøèíå Òüþðèíãà.

ϕ(X

, X

) = g(F

, X

), F

, X

))  ñóïåðïîçèöèÿ ôóíêöèé,

ðåàëèçóåòñÿ ïîñðåäñòâîì êîìïîçèöèè ìàøèí Òüþðèíãà:

=copy2(X

)°(MF

||MF

)°çàì*

||

°Ìg. Ìàøèíà M

ñíà÷àëà

êîïèðóåò èñõîäíîå ñëîâî, ðåàëèçóÿ ôóíêöèþ Copy2(X

ðåçóëüòàòîì êîòîðîé ÿâëÿåòñÿ ñëîâî X

2

||X

. Çàòåì îíî

ïåðåðàáàòûâàåòñÿ ïàðàëëåëüíîé êîìïîçèöèåé ìàøèí MF

||MF

â ñëîâî

)||F

)), çàòåì àëãîðèòì çàì*

çàìåíÿåò

âñïîìîãàòåëüíûé ðàçäåëÿþùèé ñèìâîë || íà *, è äàëåå ðàáîòàåò

ìàøèíà, âû÷èñëÿþùàÿ ôóíêöèþ g(F

,X

), F

, X

)):

)*F

)). Ðåçóëüòàòîì åå ðàáîòû ÿâëÿåòñÿ ôóíêöèÿ

ϕ(X

,X

Ñõåìà ïðèìèòèâíîé ðåêóðñèè òàêæå âû÷èñëÿåòñÿ ïîñðåäñòâîì

êîìïîçèöèè ìàøèí Òüþðèíãà. Íàïðèìåð, ñàìàÿ ïðîñòàÿ ñõåìà ïðè-

ìèòèâíîé ðåêóðñèè: ϕ(0)= c, ϕ(X+1) = F(ϕ(X)),  âû÷èñëèìà êàê

êîìïîçèöèÿ, ðåàëèçóþùàÿ èòåðàöèþ. Äëÿ ýòîãî ñòðîÿòñÿ ìàøèíû:

, êîòîðàÿ ïåðåðàáàòûâàåò òðîéêó ÷èñåë X#m#z â òðîéêó X#m+1#F(z);

, êîòîðàÿ ïåðåðàáàòûâàåò ÷èñëî X â òðîéêó X#0#c;

Ô, êîòîðàÿ ðàñïîçíàåò ñâîéñòâî m<X â òðîéêå ÷èñåë X#m#z.

Êîìïîçèöèÿ M

°ïîêà Ô ïîâòîðèòü M

çàäàåò àëãîðèòì,

êîòîðûé, èñõîäÿ èç ñëîâà X, âûðàáàòûâàåò òðîéêó X#0#c, ïîòîì

X#1#F(c), ïîòîì X#2#F(F(c)), è òàê äàëåå, äî òåõ ïîð, ïîêà íå áóäåò

ïîëó÷åíà òðîéêà X#X#ϕ(X). Òîãäà âûäåëÿþùèé àëãîðèòì, ïðèìå-

íåííûé ê ýòîìó ñëîâó, âûäåëèò êðàéíþþ ïðàâóþ êîìïîíåíòó ñëîâà,

êîòîðàÿ ÿâëÿåòñÿ ðåçóëüòàòîì âû÷èñëåíèÿ ôóíêöèè ϕ(X).

Ìàøèíà Òüþðèíãà, âû÷èñëÿþùàÿ µ-îïåðàòîð, áóäåò íàõîäèòü

ìèíèìàëüíîå ñëîâî â ëåêñèêîãðàôè÷åñêîì óïîðÿäî÷èâàíèè ñëîâ,

óäîâëåòâîðÿþùåå äàííîìó ïðåäèêàòó.

Ïîñêîëüêó âñå øåñòü ïóíêòîâ îïðåäåëåíèÿ ðåêóðñèâíûõ ôóíê-

öèé ðåàëèçóåìû â âèäå êîìïîçèöèé ìàøèí Òüþðèíãà, òî âñÿêàÿ

ðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà íà ìàøèíå Òüþðèíãà.

274 275Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

2.Âñÿêàÿ ôóíêöèÿ, âû÷èñëèìàÿ ïî Òüþðèíãó, ðåêóðñèâíà

(÷àñòè÷íî ðåêóðñèâíà).

Äîêàçàòåëüñòâî ìîæíî íàéòè â [Òðàõòåíáðîò, 1976; Êóçíåöîâ, 1980].

Òàêèì îáðàçîì, ïîêàçàíî, ÷òî êëàññ ôóíêöèé, âû÷èñëèìûõ íà

ìàøèíå Òüþðèíãà, ÿâëÿåòñÿ ÷àñòè÷íî ðåêóðñèâíûì êëàññîì.

Êðîìå ìàøèíû Òüþðèíãà è íîðìàëüíîãî àëãîðèòìà Ìàðêîâà

áûëî íàéäåíî è ïðåäëîæåíî ìíîãî äðóãèõ àëãîðèòìè÷åñêèõ ñõåì,

íàïðèìåð, ìàøèíà ôîí Íåéìàíà, ìàøèíà Ïîñòà, áëîê-ñõåìû Ïîñòà,

ôîðìàëüíîå èñ÷èñëåíèå ðåêóðñèâíûõ ôóíêöèé Ýðáðàíà  Ã¸äåëÿ

è äðóãèå. Îêàçàëîñü, ÷òî âñå îíè ýêâèâàëåíòíû ìåæäó ñîáîé, è,

ñëåäîâàòåëüíî, âû÷èñëÿþò ðåêóðñèâíûå èëè ÷àñòè÷íî ðåêóðñèâíûå

ôóíêöèè. Ýòî îáñòîÿòåëüñòâî ïîñëóæèëî ïðè÷èíîé òîìó, ÷òî ðÿä

ó÷åíûõ (×¸ð÷, Òüþðèíã, Ìàðêîâ) âûñêàçàëè ãèïîòåçó, êîòîðàÿ

èçâåñòíà êàê òåçèñ ×¸ð÷à.

15.4.4. Òåçèñ ×¸ð÷à

Êàæäàÿ ôóíêöèÿ ÿâëÿåòñÿ ýôôåêòèâíî âû÷èñëèìîé òîãäà è

òîëüêî òîãäà, êîãäà îíà ðåêóðñèâíà.

Èíûìè ñëîâàìè, òåçèñ ×¸ð÷à ïðåäëàãàåò ïîíèìàòü ïîä ýôôåê-

òèâíîé âû÷èñëèìîñòüþ ñóùåñòâîâàíèå àëãîðèòìè÷åñêîé ñõåìû, à

ïîñêîëüêó âñå íàéäåííûå àëãîðèòìè÷åñêèå ñõåìû âû÷èñëÿþò

òîëüêî êëàññ ðåêóðñèâíûõ (÷àñòè÷íî ðåêóðñèâíûõ) ôóíêöèé, òî

ïîä ýôôåêòèâíîé âû÷èñëèìîñòüþ òîãäà ïîíèìàåòñÿ ðåêóðñèâíîñòü.

Ìû óæå ãîâîðèëè, ÷òî ïîíÿòèå àëãîðèòìà íå ÿâëÿåòñÿ òî÷íûì

ìàòåìàòè÷åñêèì îïðåäåëåíèåì. Ïîïûòêè íàéòè òàêîå îïðåäåëåíèå

ïðèâåëè ê ñîçäàíèþ ìàòåìàòè÷åñêè ñòðîãèõ àëãîðèòìè÷åñêèõ ñõåì.

Çíà÷åíèå ãèïîòåçû, âûñêàçàííîé â òåçèñå ×åð÷à, çàêëþ÷àåòñÿ â òîì,

÷òî îíà óòî÷íÿåò èíòóèòèâíî ïîíÿòíîå, íî íåòî÷íîå è ðàñïëûâ÷àòîå

ïîíÿòèå àëãîðèòìà ÷åðåç áîëåå ñïåöèàëüíîå, íî ìàòåìàòè÷åñêè

òî÷íîå ïîíÿòèå àëãîðèòìè÷åñêîé ñõåìû. Òåïåðü ìîæíî ãîâîðèòü î

ðàçðåøèìîñòè íåêîòîðîãî êëàññà çàäà÷ â òåðìèíàõ ñóùåñòâîâàíèÿ

ìàøèíû Òüþðèíãà (èëè àëãîðèòìà Ìàðêîâà, èëè êàêîé-ëèáî äðóãîé

èç èçâåñòíûõ àëãîðèòìè÷åñêèõ ñõåì).

Òåçèñ ×åð÷à íå ÿâëÿåòñÿ òåîðåìîé, î åãî äîêàçàòåëüñòâå ðå÷è íå

èäåò,  ýòî óòâåðæäåíèå, ïðåäëàãàþùåå îòîæäåñòâèòü ýôôåêòèâíóþ

âû÷èñëèìîñòü ñ ñóùåñòâîâàíèåì àëãîðèòìè÷åñêîé ñõåìû. Åãî

ìîæíî ïðèíèìàòü èëè íå ïðèíèìàòü,

Óâåðåííîñòü â ñïðàâåäëèâîñòè òåçèñà ×¸ð÷à îñíîâàíà, ïðåæäå

âñåãî, íà îïûòå: â ðåçóëüòàòå ìíîãî÷èñëåííûõ èññëåäîâàíèé íå óäà-

ëîñü íàéòè êàêîé-ëèáî äðóãîé àëãîðèòìè÷åñêîé ñõåìû, êîòîðàÿ

âû÷èñëÿëà áû áîëåå øèðîêèé êëàññ ôóíêöèé, ÷åì ðåêóðñèâíûé.

Âñå íàéäåííûå àëãîðèòìè÷åñêèå ñõåìû îêàçàëèñü ýêâèâàëåíòíû

ìåæäó ñîáîé è, ñëåäîâàòåëüíî, ýêâèâàëåíòíû ìàøèíå Òüþðèíãà.

Ïîýòîìó âû÷èñëèìûìè ôóíêöèÿìè, ñîãëàñíî òåçèñó ×¸ð÷à,

ÿâëÿþòñÿ òå è òîëüêî òå, êîòîðûå ÿâëÿþòñÿ ðåêóðñèâíûìè (÷àñòè÷-

íî ðåêóðñèâíûìè). Îäíàêî, íå âñå àðèôìåòè÷åñêèå ôóíêöèè ÿâëÿ-

þòñÿ ðåêóðñèâíûìè. Ýòî íåòðóäíî ïîêàçàòü.

Åñëè ïðèíèìàòü òåçèñ ×åð÷à, òî ìíîæåñòâî ýôôåêòèâíî âû÷èñ-

ëèìûõ ôóíêöèé ñîâïàäàåò ñ ìíîæåñòâîì âñåõ ìàøèí Òüþðèíãà,

òàê êàê êàæäàÿ ìàøèíà Òüþðèíãà âû÷èñëÿåò êàêóþ-ëèáî àðèôìåòè-

÷åñêóþ ôóíêöèþ. Ëþáàÿ ïðîãðàììà äëÿ ìàøèíû Òüþðèíãà ìîæåò

áûòü çàêîäèðîâàíà íåêîòîðûì êîäîì. Ïóñòü Ì åñòü íåêîòîðàÿ

ìàøèíà Òüþðèíãà. Òîãäà ïðîãðàììó ìàøèíû Ì âìåñòå ñ âõîäíûì

ñëîâîì W ìîæíî çàïèñàòü â âèäå ïîñëåäîâàòåëüíîñòè: x

Ïq

;

Ëq

;x

Ïq

*W, ãäå êàæäàÿ êîìàíäà x

→x

ξq

çàïèñàíà

êàê x

ξq

(ξ∈{Ï, Ë, Í}), êîìàíäû ðàçäåëåíû ñèìâîëîì «;». Òàêàÿ

ïîñëåäîâàòåëüíîñòü íàçûâàåòñÿ êîäîì ìàøèíû Òüþðèíãà è

îáîçíà÷àåòñÿ d(Ì). Êîä ìàøèíû Òüþðèíãà ìîæíî ïðåäñòàâèòü

÷èñëîì â íåêîòîðîé ñèñòåìå ñ÷èñëåíèÿ. Áóäåì îáîçíà÷àòü ñîñòîÿíèÿ

ìàøèíû Òüáðèíãà äåñÿòè÷íûìè ÷èñëàìè, òîãäà äëÿ îáîçíà÷åíèÿ

ñîñòîÿíèé ïîòðåáóåòñÿ 10 ñèìâîëîâ. Â êà÷åñòâå âõîäíîãî àëôàâèòà

âûáåðåì àëôàâèò èç äâóõ ñèìâîëîâ 0 è 1 (âîçìîæíîñòü êîäèðîâàíèÿ

ñëîâ ëþáîãî àëôàâèòà â äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ íå âûçûâàåò

ñîìíåíèé). Ñîõðàíèì ñèìâîëû äâèæåíèÿ ãîëîâêè: Ë, Ï, Í, è

ðàçäåëèòåëüíûå ñèìâîëû «;» è «*». Òîãäà êîäó êàæäîé ìàøèíû

Òüþðèíãà áóäåò ñîîòâåòñòâîâàòü ÷èñëî â ïÿòíàäöàòèðè÷íîé ñèñòåìå

ñ÷èñëåíèÿ, êîòîðîå ìîæíî ïåðåâåñòè â äåñÿòè÷íóþ ñèñòåìó

ñ÷èñëåíèÿ, è ðàçëè÷íûì ìàøèíàì áóäóò ñîîòâåòñòâîâàòü ðàçëè÷íûå

÷èñëà. Ýòî ÷èñëî, ñîîòâåòñòâóþùåå êîäó ìàøèíû, íàçûâàþò

èíäåêñîì ìàøèíû Òüþðèíãà. Âû÷èñëåíèå èíäåêñà îïðåäåëÿåò

èíúåêöèþ ìíîæåñòâà âñåõ ìàøèí Òüþðèíãà â áåñêîíå÷íîå

ïîäìíîæåñòâî íàòóðàëüíûõ ÷èñåë. Îòñþäà ñëåäóåò, ÷òî ìíîæåñòâî

ìàøèí Òüþðèíãà ñ÷åòíî. Îäíàêî ìíîæåñòâî âñåõ àðèôìåòè÷åñêèõ

ôóíêöèé íåñ÷åòíî, îòêóäà ñëåäóåò, ÷òî ñóùåñòâóþò íåâû÷èñëèìûå

ôóíêöèè è àëãîðèòìè÷åñêè íåðàçðåøèìûå ïðîáëåìû.

15.5. Àëãîðèòìè÷åñêè íåðàçðåøèìûå ïðîáëåìû

15.5.1. Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà

Ìàøèíà Òüþðèíãà ñîäåðæèò îñíîâíûå èäåè ñîâðåìåííûõ âû-

÷èñëèòåëüíûõ ìàøèí, â êîòîðûõ ïîñëåäîâàòåëüíîñòü âû÷èñëåíèé

óïðàâëÿåòñÿ ïðîãðàììîé. Òüþðèíãó ïðèíàäëåæèò òàêæå èäåÿ

ïîñòðîåíèÿ óíèâåðñàëüíîé âû÷èñëèòåëüíîé ìàøèíû, êîòîðàÿ

ñíà÷àëà ïðîâåðÿåò ïðàâèëüíîñòü ââåäåííîé â íåå ïðîãðàììû, à çàòåì

âûïîëíÿåò åå íàä çàäàííûìè èñõîäíûìè äàííûìè. Ýòà èäåÿ ðåàëè-

çîâàíà â ñîâðåìåííûõ âû÷èñëèòåëüíûõ ìàøèíàõ. Öåëüþ Òüþðèíãà

276 277Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

ïðè ðàçðàáîòêå óíèâåðñàëüíîé ìàøèíû áûëî ñîçäàíèå ìàòåìàòè÷åñ-

êîãî àïïàðàòà äëÿ ìîäåëèðîâàíèÿ ðàáîòû ëþáîé ìàøèíû Òüþðèíãà.

Ìîæíî ïîñòðîèòü òàêóþ ìàøèíó Ì′(d(Ì)*W), íà âõîä êîòîðîé

áóäåò ïîäàâàòüñÿ êîä ìàøèíû Òüþðèíãà d(Ì) âìåñòå ñ âõîäíûì

ñëîâîì W. Òîãäà ìàøèíà Ì′ ñíà÷àëà ïðîâåðÿåò, ÿâëÿåòñÿ ëè d(Ì)

ñèíòàêñè÷åñêè ïðàâèëüíûì ïðîãðàììíûì êîäîì äëÿ ìàøèíû Òüþ-

ðèíãà, è åñëè ýòî òàê, òî âûïîëíÿåò ïðîãðàììó ìàøèíû Ì íàä ñëî-

âîì W; åñëè æå íåò, òî îíà îñòàíàâëèâàåòñÿ â ñîñòîÿíèè «íåò!». Òàêàÿ

ìàøèíà Òüþðèíãà íàçûâàåòñÿ óíèâåðñàëüíîé ìàøèíîé Òüþðèíãà.

Àíàëîãè÷íî ìîæíî ïîñòðîèòü è óíèâåðñàëüíûé àëãîðèòì

Ìàðêîâà.

15.5.2. Ïðîáëåìà îñòàíîâà äëÿ ìàøèíû Òüþðèíãà

Èñòîðè÷åñêè ïåðâîé àëãîðèòìè÷åñêè íåðàçðåøèìîé ïðîáëåìîé,

äîêàçàííîé Òüþðèíãîì, áûëà ïðîáëåìà îñòàíîâà äëÿ ìàøèíû

Òüþðèíãà. Îíà ôîðìóëèðóåòñÿ òàê: ìîæíî ëè ïîñòðîèòü òàêóþ

óíèâåðñàëüíóþ ìàøèíó Òüþðèíãà Ì′, ÷òî áóäó÷è ïðèìåíåííîé ê

ñëîâó (d(Ì)*W), îíà áóäåò îñòàíàâëèâàòüñÿ â «äà!» ñîñòîÿíèè,

åñëè ìàøèíà Òüþðèíãà Ì ïðèìåíèìà ê ñëîâó W, ò.å. îñòàíàâëèâà-

åòñÿ íà ýòîì ñëîâå, è îñòàíàâëèâàòüñÿ â «íåò!» ñîñòîÿíèè, åñëè

ìàøèíà Ì íå ïðèìåíèìà ê ñëîâó W.

Òåîðåìà 15.5. Ïðîáëåìà îñòàíîâà äëÿ ìàøèíû Òüþðèíãà àëãî-

ðèòìè÷åñêè íåðàçðåøèìà.

Äîêàçàòåëüñòâî.

Ïðåäïîëîæèì, ÷òî óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà Ì′,

ðàñïîçíàþùàÿ îñòàíîâ äëÿ ëþáîé ìàøèíû Òüþðèíãà, ïîñòðîåíà.

Òîãäà â åå ïðîãðàììå åñòü êîìàíäû: q′σ→σäà! è q′′τ→τíåò!,

ò.å. â ñîñòîÿíèè q′ íà ñèìâîëå σìàøèíà Ì′ îñòàíàâëèâàåòñÿ â äà!-

ñîñòîÿíèè, à â ñîñòîÿíèè q′′ íà ñèìâîëå τ â íåò!-ñîñòîÿíèè.

Ïîñòðîèì òåïåðü ìàøèíó Òüþðèíãà Ì′′ òàê, ÷òî èçìåíèì â íåé

òîëüêî îäíó êîìàíäó: â ñîñòîÿíèè q′ íà ñèìâîëå σ ìàøèíà Ì′′

âûäàåò ñèãíàë äà (ïåðåõîäèò â ñîñòîÿíèå äà), íî íå îñòàíàâëèâàåòñÿ,

à ïðîäîëæàåò áåñêîíå÷íî ïèñàòü ñèìâîë σ â îäíó è òó æå ÿ÷åéêó.

Òîãäà â ïðîãðàììå ìàøèíû Ì′′ áóäóò êîìàíäû: q′σ→σäàÍ è

q′′τ→τíåò!.

Òåïåðü íà âõîä ìàøèíû Ì′ ïîäàäèì åå ñîáñòâåííûé êîä, à â

êà÷åñòâå âõîäíîãî ñëîâà  êîä ìàøèíû Ì′′: Ì′(d(M′)*d(M′′)).

Ñìîæåò ëè òåïåðü ìàøèíà Ì′ ðàñïîçíàòü, îñòàíîâèòñÿ ëè îíà ñàìà

íà êîäå ìàøèíû Òüþðèíãà Ì′′?

Óíèâåðñàëüíàÿ ìàøèíà Òüþðèíãà ðàáîòàåò òàê, êàê ìàøèíà, êîä

êîòîðîé ïîäàí íà åå ëåíòó, ñëåäîâàòåëüíî, äîéäÿ äî ñèìâîëà σ â

ñîñòîÿíèè q′ â êîäå ìàøèíû Ì′′, ìàøèíà Ì′ îñòàíîâèòñÿ â

ñîñòîÿíèè «äà!», â òî âðåìÿ êàê Ì′′ íå îñòàíàâëèâàåòñÿ! È íàîáîðîò,

êîãäà â ñîñòîÿíèè q′′ ìàøèíà Ì′′ âèäèò ñèìâîë τ, îíà âûäàåò

ñîîáùåíèå «íåò» è îñòàíàâëèâàåòñÿ, à ìàøèíà Ì′ äëÿ ýòîé ñèòóàöèè

òîæå îñòàíàâëèâàåòñÿ â ñîñòîÿíèè «íåò», ò.å. îíà âûäàåò ñîîáùåíèå

î òîì, ÷òî ìàøèíà Ì′′ íå îñòàíàâëèâàåòñÿ!

Òàêèì îáðàçîì, ìàøèíà Òüþðèíãà Ì′ íå ðàñïîçíàåò ñâîé ñîá-

ñòâåííûé îñòàíîâ íà êîäå ìàøèíû Ì′′. Ñàì ôàêò âîçìîæíîñòè ïîñòðî-

åíèÿ òàêîé ìàøèíû Òüþðèíãà, êîòîðàÿ íå ìîæåò ðàñïîçíàòü îñòàíîâ,

äîêàçûâàåò àëãîðèòìè÷åñêóþ íåðàçðåøèìîñòü ýòîé ïðîáëåìû.

15.5.3. Ïðîáëåìà ñàìîïðèìåíèìîñòè

Áóäåì ãîâîðèòü, ÷òî ìàøèíà Òüþðèíãà Ì ñàìîïðèìåíèìà, åñëè

îíà îñòàíàâëèâàåòñÿ íà ñâîåì ñîáñòâåííîì êîäå d(Ì), è íå

ñàìîïðèìåíèìà, åñëè îíà íå îñòàíàâëèâàåòñÿ íà ñâîåì êîäå d(Ì).

Òåîðåìà 15.6. Ïðîáëåìà ðàñïîçíàâàíèÿ ñàìîïðèìåíèìîñòè

ìàøèíû Òüþðèíãà àëãîðèòìè÷åñêè íå ðàçðåøèìà.

Äîêàçàòåëüñòâî. Ïðåäïîëîæèì, ÷òî ïîñòðîåíà óíèâåðñàëüíàÿ

ðàñïîçíàþùàÿ ìàøèíà Òüþðèíãà Ì′, êîòîðàÿ îñòàíàâëèâàåòñÿ â

«äà!» ñîñòîÿíèè, åñëè ìàøèíà, êîä êîòîðîé ïîäàåòñÿ íà åå âõîä,

ñàìîïðèìåíèìà, è â «íåò!» ñîñòîÿíèè, åñëè íå ñàìîïðèìåíèìà.

Òîãäà â ïðîãðàììå ìàøèíû Òüþðèíãà Ì′ ïðèñóòñòâóþò äâå êîìàíäû

âèäà: q′σ→ σäà!, q′′τ → τíåò! Àíàëîãè÷íî ïðåäûäóùåìó äîêàçàòåëü-

ñòâó, ïîñòðîèì ìàøèíó Ì′′, èçìåíèâ îäíó êîìàíäó: q′σ → σäàÍ

(ò.å. â ñîñòîÿíèè q′ ìàøèíà íå îñòàíàâëèâàåòñÿ, à áåñêîíå÷íî ïèøåò

ñèìâîë σ íà ëåíòå). Òåïåðü, åñëè íà âõîä Ì′ ïîäàòü d(Ì′′):

Ì′(d(Ì′′)) ìàøèíà áóäåò âûäàâàòü «äà!»,  ò.å. ñîîáùàòü, ÷òî Ì′′

ñàìîïðèìåíèìà, â òî âðåìÿ êàê îíà íåñàìîïðèìåíèìà, òàê êàê íå

îñòàíàâëèâàåòñÿ, è, íàîáîðîò, îíà áóäåò âûäàâàòü ñîîáùåíèå «íåò!»,

åñëè ìàøèíà Ì′′ íå îñòàíàâëèâàåòñÿ, ò.å. åñëè îíà ñàìîïðèìåíèìà.

Òàêèì îáðàçîì, äîêàçàòåëüñòâî íåðàçðåøèìîñòè ïðîáëåìû ñàìî-

ïðèìåíèìîñòè ñâîäèòñÿ ê äîêàçàòåëüñòâó íåâîçìîæíîñòè ðàñïîçíà-

âàíèÿ îñòàíîâà ìàøèíû Òüþðèíãà. Îòñþäà âîçíèê è îáùèé ìåòîä

äîêàçàòåëüñòâà àëãîðèòìè÷åñêîé íåðàçðåøèìîñòè äðóãèõ çàäà÷:

ìåòîä ñâåäåíèÿ ïðîáëåì. Îí çàêëþ÷àåòñÿ â òîì, ÷òî íîâàÿ ïðîáëåìà

ñâîäèòñÿ ê íåêîòîðîé äðóãîé ïðîáëåìå, äëÿ êîòîðîé óæå äîêàçàíà

àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü. Îñîáåííî ÷àñòî ïðîáëåìà ñâî-

äèòñÿ â ïðîáëåìå ñàìîïðèìåíèìîñòè. Â êà÷åñòâå ïðèìåðà ðàññìîò-

ðèì ïðîáëåìó ýêâèâàëåíòíîñòè ñëîâ â àññîöèàòèâíûõ èñ÷èñëåíèÿõ.

Òåîðåìà 15.7. (Ìàðêîâà  Ïîñòà). Ñóùåñòâóåò àññîöèàòèâíîå

èñ÷èñëåíèå, â êîòîðîì ïðîáëåìà ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè

ñëîâ àëãîðèòìè÷åñêè íåðàçðåøèìà.

278 279Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ

Äîêàçàòåëüñòâî. Ïóñòü ìàøèíà Òüþðèíãà Ì íà÷èíàåò ðàáîòó

ñî ñëîâà R ñ íà÷àëüíîé êîíôèãóðàöèåé q

a è çàêàí÷èâàåò ðàáîòó

ñëîâîì S ñ êîíå÷íîé êîíôèãóðàöèåé q

b. Ïðîáëåìà ðàñïîçíàâàíèÿ

ýêâèâàëåíòíîñòè ñëîâ R è S â òàêîé ïîñòàíîâêå çàêëþ÷àåòñÿ â

íàõîæäåíèè àëãîðèòìà, êîòîðûé ïî êîäó ìàøèíû Ì ðàñïîçíàåò,

îñòàíîâèòñÿ ëè îíà â ñîñòîÿíèè q

, íà÷èíàÿ ðàáîòó ñ êîíôèãóðàöèè

a, èëè íåò. Ïîäàäèì êîä ýòîé ìàøèíû âìåñòå ñî ñëîâîì R íà

âõîä óíèâåðñàëüíîé ìàøèíû Ì′: Ì′(d(M)*R). Äëÿ ìàøèíû Ì′

ïðîáëåìà îñòàíîâà íåðàçðåøèìà. Îòñþäà ñëåäóåò, ÷òî ïðîáëåìà

ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè ñëîâ òàêæå àëãîðèòìè÷åñêè íåðàç-

ðåøèìà. Ïîêàæåì, ÷òî îíà íåðàçðåøèìà òàêæå è â íåêîòîðîì àññî-

öèàòèâíîì èñ÷èñëåíèè. Äëÿ ýòîãî âîñïîëüçóåìñÿ òåì ñâîéñòâîì,

÷òî äëÿ ëþáîé ìàøèíû Òüþðèíãà ìîæíî ïîñòðîèòü ýêâèâàëåíòíîå

åìó àññîöèàòèâíîå èñ÷èñëåíèå.

Ïîñëåäíåå ñâîéñòâî áûëî äîêàçàíî íàìè äëÿ íîðìàëüíûõ àëãî-

ðèòìîâ Ìàðêîâà. Íîðìàëüíûé àëãîðèòì Ìàðêîâà ìîæíî ðàñ-

ñìàòðèâàòü êàê àññîöèàòèâíîå èñ÷èñëåíèå ñ îäíîíàïðàâëåííûìè

ïîäñòàíîâêàìè, ÷òî íåïîñðåäñòâåííî ñëåäóåò èç îïðåäåëåíèÿ ýòèõ

ñèñòåì. Ïðè íåîáõîäèìîñòè äëÿ êàæäîé ïîäñòàíîâêè íîðìàëüíîãî

àëãîðèòìà ìîæíî îïðåäåëèòü îáðàòíóþ ïîäñòàíîâêó è ïîëó÷èòü

àññîöèàòèâíîå èñ÷èñëåíèå ñ äâóíàïðàâëåííûìè ïîäñòàíîâêàìè.

Ïîñòðîèì àññîöèàòèâíîå èñ÷èñëåíèå G(M), âûïîëíÿþùåå òîò

æå àëãîðèòì, ÷òî è ìàøèíà Ì, â ÷àñòíîñòè, ïåðåðàáàòûâàþùåå ñëîâî

R â ñëîâî S, è ïðèñîåäèíèì ê íåìó ñèñòåìó ïîäñòàíîâîê âèäà

→q

. Ïîëó÷èì íîâîå èñ÷èñëåíèå G′(M). Â ýòîì èñ÷èñëåíèè

òàêæå ïåðåðàáàòûâàþòñÿ ñëîâà âèäà R â ñëîâà âèäà S, íî âñå

çàêëþ÷èòåëüíûå êîíôèãóðàöèè Ì â G′(M) ýêâèâàëåíòíû. Ïîýòîìó

â G(M) ñëîâà q

a è q

ýêâèâàëåíòíû, åñëè è òîëüêî åñëè ìàøèíà

Ì, íà÷àâ ðàáîòó ñî ñëîâà q

a, îñòàíîâèòñÿ. Ââèäó íåðàçðåøèìîñòè

ïðîáëåìû îñòàíîâà äëÿ Ì′, ïðîáëåìà ýêâèâàëåíòíîñòè ñëîâ q

a è

òàêæå íåðàçðåøèìà.

Èç ýòîé òåîðåìû ñëåäóåò, ÷òî ïðîáëåìà ðàñïîçíàâàíèÿ ýêâèâà-

ëåíòíîñòè ñëîâ â îáùåì ñëó÷àå (ò.å. äëÿ âñåãî ìíîæåñòâà àññîöèà-

òèâíûõ èñ÷èñëåíèé) àëãîðèòìè÷åñêè íåðàçðåøèìà. Îòñþäà ñëåäóåò

òàêæå, ÷òî ïðîáëåìà ýêâèâàëåíòíîñòè àëãîðèòìîâ íåðàçðåøèìà:

ïî äâóì çàäàííûì àëãîðèòìàì â îáùåì ñëó÷àå íåâîçìîæíî

îïðåäåëèòü, âû÷èñëÿþò îíè îäíó è òó æå ôóíêöèþ èëè íåò.

Èñòîðè÷åñêè àëãîðèòìè÷åñêàÿ íåðàçðåøèìîñòü ñíà÷àëà áûëà

óñòàíîâëåíà äëÿ ïðîáëåì, âîçíèêàþùèõ â ìàòåìàòè÷åñêîé ëîãèêå,

ïðîáëåì âûâîäèìîñòè â ôîðìàëüíûõ òåîðèÿõ. Äîêàçàòåëüñòâî

íåðàçðåøèìîñòè ïðîáëåì ñàìîïðèìåíèìîñòè è ýêâèâàëåíòíîñòè

ïîêàçàëî, ÷òî àëãîðèòìè÷åñêèå ñõåìû ìîãóò ñëóæèòü àïïàðàòîì

èññëåäîâàíèÿ ðàçðåøèìîñòè è ïîëíîòû ôîðìàëüíûõ òåîðèé. Ïðîá-

ëåìó âûâîäèìîñòè â ôîðìàëüíîé òåîðèè ìîæíî èíòåðïðåòèðîâàòü

êàê ïðîáëåìó ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè ñëîâ: ñ ïîìîùüþ

çàäàííîé ñèñòåìû ïðàâèë âûâîäà íåîáõîäèìî îïðåäåëèòü, ÿâëÿåòñÿ

ëè ôîðìóëà âûâîäèìîé èç çàäàííîé ñèñòåìû àêñèîì è èñõîäíîãî

ìíîæåñòâà ïîñûëîê. Òîãäà èç àëãîðèòìè÷åñêîé íåðàçðåøèìîñòè

ðàñïîçíàâàíèÿ ýêâèâàëåíòíîñòè ñëîâ ñëåäóåò íåðàçðåøèìîñòü (â

îáùåì ñëó÷àå!) ïðîáëåìû âûâîäèìîñòè. Ìû çíàåì, ÷òî èñ÷èñëåíèå

âûñêàçûâàíèé ðàçðåøèìî: ïîñòðîåíèå òàáëèöû èñòèííîñòè

ôîðìóëû ÿâëÿåòñÿ àëãîðèòìîì, ñ ïîìîùüþ êîòîðîãî äîêàçûâàåòñÿ,

÷òî ôîðìóëà ÿâëÿåòñÿ (èëè íå ÿâëÿåòñÿ) òàâòîëîãèåé ëîãèêè âûñêà-

çûâàíèé, à, ñëåäîâàòåëüíî, è òåîðåìîé èñ÷èñëåíèÿ âûñêàçûâàíèé.

Ñóùåñòâîâàíèå íåðàçðåøèìûõ ïðåäëîæåíèé ôîðìàëüíîé àðèôìå-

òèêè (òåîðåìà Ã¸äåëÿ î íåïîëíîòå) äîêàçûâàåò åå íåðàçðåøèìîñòü.

Äîêàçàòåëüñòâî òåîðåìû Ã¸äåëÿ ñóùåñòâåííî îñíîâûâàëîñü íà

ðåêóðñèâíîñòè ïðåäñòàâèìûõ â S ôóíêöèé è îòíîøåíèé. Ñëåäîâà-

òåëüíî, òîò æå ñàìûé ðåçóëüòàò ìîæíî ïîëó÷èòü, èñïîëüçóÿ àïïàðàò

àëãîðèòìè÷åñêèõ ñõåì, â ÷àñòíîñòè, ìàøèíû Òüþðèíãà. Â 1936 ã.

ýòîò ðåçóëüòàò: ïðîáëåìà ðàñïîçíàâàíèÿ âûâîäèìîñòè â èñ÷èñëåíèè

ïðåäèêàòîâ àëãîðèòìè÷åñêè íåðàçðåøèìà, áûë ïîëó÷åí ×¸ð÷åì.

Äëÿ äàëüíåéøèõ äîêàçàòåëüñòâ ââåäåì íåêîòîðûå íîâûå ïîíÿòèÿ.

15.5.4. Ðåêóðñèâíûå è ðåêóðñèâíî ïåðå÷èñëèìûå

ìíîæåñòâà

Îïðåäåëåíèå 15.13. Ðåêóðñèâíî ïåðå÷èñëèìûì ìíîæåñòâîì

ÿâëÿåòñÿ ëèáî ïóñòîå ìíîæåñòâî, ëèáî ìíîæåñòâî çíà÷åíèé

íåêîòîðîé ðåêóðñèâíîé ôóíêöèè F(x).

Ïðèíèìàÿ òåçèñ ×¸ð÷à, ýòî ìîæíî èíòåðïðåòèðîâàòü òàê, ÷òî

äëÿ ðåêóðñèâíî ïåðå÷èñëèìîãî ìíîæåñòâà ñóùåñòâóåò ýôôåêòèâíàÿ

ïðîöåäóðà ïîñëåäîâàòåëüíîãî ïîðîæäåíèÿ (ïåðå÷èñëåíèÿ) âñåõ åãî

ýëåìåíòîâ; èíûìè ñëîâàìè, ñóùåñòâóåò ìàøèíà Òüþðèíãà, êîòîðàÿ,

íà÷èíàÿ ðàáîòó ñ ïóñòîé ëåíòû, âûïèñûâàåò íà íåå âñå ýëåìåíòû

ýòîãî ìíîæåñòâà.

Îïðåäåëåíèå 15.14. Ìíîæåñòâî S ÿâëÿåòñÿ ðåêóðñèâíûì, åñëè

ñóùåñòâóåò ðåêóðñèâíàÿ ôóíêöèÿ f(x) òàêàÿ, ÷òî

∈





∉



1, åñëè ,

()

0, åñëè .

Â òåðìèíàõ ýôôåêòèâíîé âû÷èñëèìîñòè ýòî îçíà÷àåò, ÷òî

ñóùåñòâóåò ýôôåêòèâíàÿ ïðîöåäóðà äëÿ âûÿñíåíèÿ âîïðîñà, ïðè-

íàäëåæèò èëè íå ïðèíàäëåæèò ïðîèçâîëüíûé ýëåìåíò ýòîìó ìíî-

æåñòâó. Òîãäà ñóùåñòâóåò ìàøèíà Òüþðèíãà, êîòîðàÿ äëÿ ëþáîãî x

îñòàíàâëèâàåòñÿ â «äà!» ñîñòîÿíèè, åñëè x ïðèíàäëåæèò ìíîæåñòâó

S, è â «íåò!» ñîñòîÿíèè, åñëè x íå ïðèíàäëåæèò S.