Таран Т.А. Основы дискретной математики
Подождите немного. Документ загружается.
280 281Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ
Ðåêóðñèâíûå ìíîæåñòâà íàçûâàþò òàêæå ðàçðåøèìûìè ìíîæå-
ñòâàìè.
Ìîæíî äîêàçàòü ñëåäóþùèå òåîðåìû î ðåêóðñèâíûõ è
ðåêóðñèâíî ïåðå÷èñëèìûõ ìíîæåñòâàõ.
Òåîðåìà 15.8. Åñëè ìíîæåñòâà R è S ðåêóðñèâíî ïåðå÷èñëèìû,
òî èõ îáúåäèíåíèå R∪S è ïåðåñå÷åíèå R∩S òàêæå ðåêóðñèâíî
ïåðå÷èñëèìû.
Äîêàçàòåëüñòâî.
Èç óñëîâèÿ òåîðåìû ñëåäóåò, ÷òî ñóùåñòâóþò äâå ìàøèíû Ì
R
è Ì
S
, êîòîðûå ïîðîæäàþò ýëåìåíòû ìíîæåñòâ R è S ñîîòâåòñòâåííî.
Òîãäà ìîæíî ïîñòðîèòü ìàøèíó Òüþðèíãà Ì
R
∪Ì
S
, âûïèñû-
âàþùóþ íà ëåíòó ïîñëåäîâàòåëüíî ýëåìåíòû r
1
, s
1
, r
2
, s
2
, , óäàëÿÿ
ïîâòîðÿþùèåñÿ ýëåìåíòû. Ìîæíî ïîñòðîèòü òàêæå ìàøèíó
Ì
R
∩Ì
S
, êîòîðàÿ â ýòîé ïîñëåäîâàòåëüíîñòè áóäåò îñòàâëÿòü
òîëüêî òå ýëåìåíòû, êîòîðûå âõîäÿò îäíîâðåìåííî è â R, è â S.
Òåîðåìà 15.9. Ìíîæåñòâî S ðåêóðñèâíî òîãäà è òîëüêî òîãäà,
êîãäà S è åãî äîïîëíåíèå S′ ðåêóðñèâíî ïåðå÷èñëèìû.
Äîêàçàòåëüñòâî.
1.Ïðåäïîëîæèì, ÷òî S ⊆ N è S ðåêóðñèâíî. Òîãäà ñóùåñòâóåò
ìàøèíà Òüþðèíãà Ì
S
, êîòîðàÿ äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà
n∈N ðàñïîçíàåò, ïðèíàäëåæèò ëè îíî ìíîæåñòâó S, èëè íåò. Òîãäà
ìîæíî ïîñòðîèòü òàêóþ êîìïîçèöèþ, ÷òî åñëè Ì
S
(n) îñòàíàâ-
ëèâàåòñÿ â ñîñòîÿíèè «äà!», ò.å. n∈S, òî íà÷èíàåò ðàáîòó ìàøèíà
Ì1, êîòîðàÿ âûïèñûâàåò íà ñâîþ ëåíòó âñå ýëåìåíòû S, à åñëè
Ì
S
(n) îñòàíàâëèâàåòñÿ â ñîñòîÿíèè «íåò!», ò.å. n∉S, òî íà÷èíàåò
ðàáîòàòü ìàøèíà Ì2, êîòîðûå âûïèñûâàåò âñå ýëåìåíòû, íå ïðèíàä-
ëåæàùèå S, íà ñâîþ ëåíòó. Òîãäà ìàøèíà Ì1 ïîðîæäàåò âñå ýëåìåí-
òû S, à Ì2 åãî äîïîëíåíèÿ S′. Ñîãëàñíî îïðåäåëåíèþ, ýòî îçíà÷àåò,
÷òî S è åãî äîïîëíåíèå S′ ðåêóðñèâíî ïåðå÷èñëèìû.
2.Ïðåäïîëîæèì, ÷òî S è S′ ðåêóðñèâíî ïåðå÷èñëèìû. Ñëåäîâà-
òåëüíî, ñóùåñòâóþò ïîðîæäàþùèå èõ ìàøèíû Ì
S
è Ì
S
′. Òîãäà
ìîæíî ïîñòðîèòü ìàøèíó Ì(x), êîòîðàÿ äëÿ êàæäîãî x áóäåò çàïóñ-
êàòü ïîïåðåìåííî Ì
S
è Ì
S
′ è ñðàâíèâàòü x ñ î÷åðåäíûì ýëåìåíòîì
s
i
. Åñëè x = s
i
, ïîðîæäåííîìó ìàøèíîé Ì
S
, òî ìàøèíà Ì(x) îñòàíàâ-
ëèâàåòñÿ â «äà!» ñîñòîÿíèè, à åñëè ìàøèíîé Ì
S
′ òî â «íåò!»
ñîñòîÿíèè. Òîãäà ìàøèíà Ì(x) ðàáîòàåò êàê ðàñïîçíàþùàÿ ìàøèíà
Òüþðèíãà äëÿ âû÷èñëåíèÿ ïðåäèêàòà x∈S. Ñóùåñòâîâàíèå òàêîé
ìàøèíû îçíà÷àåò, ÷òî ìíîæåñòâî S ðåêóðñèâíî.
Òåîðåìà 15.10. Ñóùåñòâóþò ðåêóðñèâíî ïåðå÷èñëèìûå, íî íåðå-
êóðñèâíûå ìíîæåñòâà.
 ñèëó òåîðåìû 15.9 ýòî îçíà÷àåò, ÷òî ñóùåñòâóåò òàêîå ìíîæå-
ñòâî S, êîòîðîå ðåêóðñèâíî ïåðå÷èñëèìî, íî åãî äîïîëíåíèå S′ íå
ÿâëÿåòñÿ ðåêóðñèâíî ïåðå÷èñëèìûì.
Äîêàçàòåëüñòâî.
Ïðåäïîëîæèì, ÷òî âñå ðåêóðñèâíî ïåðå÷èñëèìûå ìíîæåñòâà ìû
ìîæåì ïåðåïèñàòü â âèäå ñïèñêà (çàíóìåðîâàòü): S
1
, S
2
,, S
i
,. Òîãäà
ñóùåñòâóåò ìàøèíà Òüþðèíãà Ì(n), òàêàÿ, ÷òî äëÿ êàæäîãî íàòó-
ðàëüíîãî ÷èñëà n = 1, 2, 3, îíà ïðîâåðÿåò, ïðèíàäëåæèò ëè ÷èñëî
n, ñîîòâåòñòâóþùåå èíäåêñó ìíîæåñòâà S
n
, ñàìîìó ýòîìó ìíîæåñòâó,
(ò.å. n ∈S
n
), èëè íåò. Òîãäà, åñëè n∈S
n
, îíà âûäàåò ñîîáùåíèå
«äà» è çàïèñûâàåò ýòî ÷èñëî â ìíîæåñòâî U, à åñëè n∉S
n
, òî îíà
âûäàåò «íåò», è çàïèñûâàåò ÷èñëî n â ìíîæåñòâî U′. Òàêèì îáðàçîì,
U áóäåò ñîäåðæàòü íåêîòîðîå ïîäìíîæåñòâî íàòóðàëüíûõ ÷èñåë è
áóäåò ðåêóðñèâíî ïåðå÷èñëèìî. Î÷åâèäíî, ÷òî U′ áóäåò
äîïîëíåíèåì ìíîæåñòâà U äî ìíîæåñòâà âñåõ íàòóðàëüíûõ ÷èñåë.
Äîêàæåì òåïåðü, ÷òî ìíîæåñòâî U′ íå ðåêóðñèâíî ïåðå÷èñëèìî.
Äåéñòâèòåëüíî, åñëè U′ ðåêóðñèâíî ïåðå÷èñëèìî, òî U′ âõîäèò
â íàø ïåðåñ÷åò ñ íåêîòîðûì íîìåðîì k, ò.å. U′ = S
k
. Òîãäà, åñëè
k∈S
k
, òî k ∈ U, ò.å. k ∉U′, íî òîãäà k ∉ S
k
; à åñëè k ∉ S
k
, òî k ∈ U′,
ò.å. k ∈ S
k
.
Òàêèì îáðàçîì, ñóùåñòâóåò ýëåìåíò k, êîòîðûé íåëüçÿ îòíåñòè
íè ê òîìó, íè ê äðóãîìó ìíîæåñòâó. Ïîëó÷åííîå ïðîòèâîðå÷èå
äîêàçûâàåò, ÷òî íàøå ïðåäïîëîæåíèå î ñóùåñòâîâàíèè òàêîé
ðàñïîçíàþùåé ìàøèíû Òüþðèíãà áûëî íåâåðíûì, è ìíîæåñòâî U′
íå ðåêóðñèâíî ïåðå÷èñëèìî, è, ñëåäîâàòåëüíî, U íå ðåêóðñèâíî.
Èç äîêàçàòåëüñòâà ýòîé òåîðåìû ñòàíîâèòñÿ ïîíÿòíûì, ÷òî àëãî-
ðèòìè÷åñêàÿ íåðàçðåøèìîñòü è íåðåêóðñèâíîñòü ýòî âçàèìîñâÿ-
çàííûå ñâîéñòâà. Ñïîñîá êîäèðîâàíèÿ ïðîãðàìì ìàøèí Òüþðèíãà,
îïèñàííûé âûøå, çàäàåò ýôôåêòèâíóþ ïðîöåäóðó, ïîðîæäàþùóþ
ìíîæåñòâî èíäåêñîâ ìàøèí Òüþðèíãà. Îòñþäà ñëåäóåò, ÷òî ìíîæå-
ñòâî âñåõ ìàøèí Òüþðèíãà ðåêóðñèâíî ïåðå÷èñëèìî. Ðåêóðñèâíî
ïåðå÷èñëèìûì ÿâëÿåòñÿ òàêæå ìíîæåñòâî âñåõ ìàøèí, êîòîðûå
çàêàí÷èâàþò ñâîþ ðàáîòó çà êîíå÷íîå ÷èñëî øàãîâ. Ïðè äîêàçàòåëü-
ñòâå àëãîðèòìè÷åñêîé íåðàçðåøèìîñòè ïðîáëåìû îñòàíîâà äëÿ
ìàøèíû Òüþðèíãà áûëî ïîêàçàíî, ÷òî ìîæíî ïîñòðîèòü òàêóþ
ìàøèíó Òüþðèíãà, äëÿ êîòîðîé íåâîçìîæíî ðàñïîçíàòü îñòàíîâ.
Ýòî ïîñòðîåíèå äîêàçûâàåò, ÷òî ìíîæåñòâî âñåõ ìàøèí Òüþðèíãà,
êîòîðûå íå îñòàíàâëèâàþòñÿ íà íåêîòîðîì ñëîâå, íå ÿâëÿåòñÿ
ðåêóðñèâíî ïåðå÷èñëèìûì. Ñëåäîâàòåëüíî, ìíîæåñòâî âñåõ ìàøèí,
êîòîðûå îñòàíàâëèâàþòñÿ, íåðåêóðñèâíî (íåðàçðåøèìî). Íåðåêóð-
ñèâíîñòü ìíîæåñòâà îçíà÷àåò, ÷òî åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ,
ðàñïîçíàþùàÿ ïðèíàäëåæíîñòü ýëåìåíòà ýòîìó ìíîæåñòâó, ÿâëÿåòñÿ
íåâû÷èñëèìîé. Ïîñòðîèì òàêóþ ôóíêöèþ.
282 283Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ
15.6. Íåâû÷èñëèìûå ôóíêöèè
Îïðåäåëèì ïðåäèêàò T(i, a, x), ãäå i èíäåêñ ìàøèíû Òüþðèíãà,
êîòîðàÿ, áóäó÷è ïðèìåíèìà ê ñëîâó a, çàêàí÷èâàåò ðàáîòó â ìîìåíò
âðåìåíè x, âû÷èñëÿÿ ïðè ýòîì ôóíêöèþ ϕ
i
(a). Ñóùåñòâîâàíèå
ìîìåíòà âðåìåíè x ãàðàíòèÿ îñòàíîâà ìàøèíû. Ýòîò ïðåäèêàò
áóäåò ðàçðåøèìûì (ò.å. èñòèííûì ïðè íåêîòîðûõ çíà÷åíèÿõ i, a,x).
Äåéñòâèòåëüíî, ìîæíî ïîñòðîèòü òàêóþ óíèâåðñàëüíóþ ìàøèíó
Òüþðèíãà Ì′, êîòîðàÿ äëÿ ëþáîé ìàøèíû áóäåò îïðåäåëÿòü, ÿâëÿ-
åòñÿ ëè i ïðàâèëüíûì êîäîì ìàøèíû Òüþðèíãà. Åñëè i íå ÿâëÿåòñÿ
êîäîì, òî Ì′ îñòàíîâèòñÿ â ñîñòîÿíèè «íåò!»; òîãäà |T(i, a, x)|=F.
Åñëè i ÿâëÿåòñÿ ïðàâèëüíûì êîäîì ìàøèíû Òüþðèíãà, òî Ì′ áóäåò
ðàáîòàòü íàä ñëîâîì a è îñòàíîâèòñÿ â ñîñòîÿíèè «äà!», åñëè â ìî-
ìåíò x ìàøèíà âû÷èñëèò çíà÷åíèå ôóíêöèè ϕ
i
(a). Òîãäà |T(i, a,x)|=T.
Ýòè ðàññóæäåíèÿ ïîêàçûâàþò, ÷òî ïðåäèêàò T(i, a, x)ðàçðåøèì
â èíòóèòèâíîì ñìûñëå. Åñëè ïðèíèìàòü òåçèñ ׸ð÷à, òî ýòîò ïðåäè-
êàò ðàçðåøèì è â ñòðîãîì ñìûñëå, ò.å. ìîæíî ïîñòðîèòü òàêóþ
ìàøèíó Òüþðèíãà, êîòîðàÿ âû÷èñëÿåò õàðàêòåðèñòè÷åñêóþ ôóíê-
öèþ ïðåäèêàòà:
0, åñëè ( , , ) ,
(, , )
1, åñëè ( , , ) .
Tiax F
iax
Tiax T
=
τ=
=
Òàêèì îáðàçîì, âî-ïåðâûõ, ïðåäèêàò T(i, a, x) ðàçðåøèì, à âî-
âòîðûõ, ϕ
i
(a) âû÷èñëèìà êàê ÷àñòè÷íàÿ ôóíêöèÿ îò x.
Äåéñòâèòåëüíî, îíà îïðåäåëåíà íå äëÿ âñåõ i è a, à òîëüêî äëÿ òåõ,
äëÿ êîòîðûõ ñóùåñòâóåò ìîìåíò âðåìåíè x, êîãäà ìàøèíà Òüþðèíãà
îñòàíîâèòñÿ. Ïîýòîìó ϕ
i
(a) ÿâëÿåòñÿ ÷àñòè÷íî îïðåäåëåííîé
ôóíêöèåé è âû÷èñëèìà êàê ÷àñòè÷íàÿ ôóíêöèÿ îò i è x, ò.å. òîãäà,
êîãäà |∀a∃xT(i,a, x)|=T.
Îïðåäåëèì òåïåðü ñëåäóþùóþ ôóíêöèþ:
() 1,åñëè (,, ),
()
0 â ïðîòèâíîì ñëó÷àå.
a
axTaax
a
ϕ+ ∃
ψ=
Òåîðåìà 15.11. (×åð÷à). Ôóíêöèÿ ψ(a) íåâû÷èñëèìà.
Äîêàçàòåëüñòâî.
Ïðåäïîëîæèì, ÷òî ψ(a) âû÷èñëèìà. Òîãäà ñóùåñòâóåò ìàøèíà
Òüþðèíãà Ì
P
, âû÷èñëÿþùàÿ ψ(a), è p èíäåêñ ýòîé ìàøèíû,
ò.å.ψ(a)=ϕ
ð
(a) äëÿ âñåõ a. Ïîäñòàâëÿÿ p âìåñòî a, ïîëó÷èì:
ψ(p)=ϕ
ð
(p). Òîãäà ïðåäèêàò |∃xÒ(ð, à, x)| = Ò äëÿ äàííîãî p è äëÿ
ëþáîãî a, â òîì ÷èñëå è äëÿ à=ð, ò.å. |∃xÒ(ð, ð, x)| = Ò. Íî òîãäà, ïî
îïðåäåëåíèþ ôóíêöèè ψ(a), ψ(ð)= ϕ
ð
(ð)+1, ÷òî ïðîòèâîðå÷èò
ïîëó÷åííîìó ðàíåå ðàâåíñòâó. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçû-
âàåò óòâåðæäåíèå òåîðåìû.
Òåîðåìà ׸ð÷à äàåò êîíñòðóêòèâíûé ñïîñîá ïîñòðîåíèÿ
íåâû÷èñëèìîé ôóíêöèè.
Ïðèìåð.  êà÷åñòâå ïðèìåðà îïðåäåëåíèÿ íåâû÷èñëèìîé ôóíê-
öèè ðàññìîòðèì ñëåäóþùóþ çàäà÷ó. Ïðåäñòàâèì ñåáå áîëüøóþ áèá-
ëèîòåêó, â êîòîðîé êíèãè ðàññòàâëåíû ïî ðàçäåëàì. Äëÿ êàæäîãî
ðàçäåëà ñîñòàâëåí êàòàëîã. Êàæäàÿ êíèãà èìååò íàçíà÷åííóþ åé
öåíó, à ïîñêîëüêó êàòàëîã ðàçäåëà ñîäåðæèò ñâåäåíèÿ îáî âñåõ êíè-
ãàõ, îí äîëæåí áûòü ñàìîé öåííîé êíèãîé. Ïîýòîìó åãî ñòîèìîñòü
îïðåäåëåíà êàê ôóíêöèÿ îò ñòîèìîñòè ñàìîé äîðîãîé êíèãè â
ðàçäåëå: Ñ
ê
= Ñ
max
+ 1. Êíèã â áèáëèîòåêå îêàçàëîñü íàñòîëüêî ìíîãî,
÷òî âñå êàòàëîãè áûëè ñîñòàâëåíû â îòäåëüíûé ðàçäåë ðàçäåë
êàòàëîãîâ, äëÿ êîòîðîãî òàêæå áûë ñîñòàâëåí êàòàëîã êàòàëîã
êàòàëîãîâ. Åìó òàêæå äîëæíà áûòü íàçíà÷åíà öåíà ïî îïðåäåëåí-
íîìó âûøå ïðàâèëó: ñòîèìîñòü åãî Ñ
ê
ê
äîëæíà áûòü ñàìîé âûñîêîé
â ýòîì ðàçäåëå, ò.å. Ñ
ê
ê
= Ñ
êmax
, è äîëæíà áûòü íà åäèíèöó áîëüøå
öåíû ñàìîé äîðîãîé êíèãè â ðàçäåëå: Ñ
ê
ê
= Ñ
êmax
+1. Íî ïîñêîëüêó
êàòàëîã êàòàëîãîâ ñàì ÿâëÿåòñÿ êàòàëîãîì, òî åãî öåíà äîëæíà áûòü
íà åäèíèöó áîëüøå åãî ñîáñòâåííîé ñòîèìîñòè: Ñ
ê
ê
= Ñ
ê
ê
+1. Òàêèì
îáðàçîì, îêàçàëîñü, ÷òî ñòîèìîñòü åãî íåâîçìîæíî âû÷èñëèòü ïî
çàäàííîìó ïðàâèëó.
Íåâû÷èñëèìàÿ ôóíêöèÿ ׸ð÷à óæå âñòðå÷àëàñü íàì è ðàíåå:
ïðè äîêàçàòåëüñòâå íåñ÷åòíîñòè ìíîæåñòâà âñåõ àðèôìåòè÷åñêèõ
ôóíêöèé, ïðè äîêàçàòåëüñòâå íåðåêóðñèâíîñòè ìíîæåñòâà, èìåþ-
ùåãî íå ïåðå÷èñëèìîå ðåêóðñèâíî äîïîëíåíèå. Íî â òåîðåìå ׸ð÷à
ýòà ôóíêöèÿ îïðåäåëåíà ÷åðåç ïðåäèêàò Ò(ð, à, x), ñóùåñòâåííî
èñïîëüçóþùèé óñëîâèå îñòàíîâà äëÿ ìàøèíû Òüþðèíãà
ïåðåìåííóþ x. Ïðåäèêàò ∃xÒ(ð, ð, x) ôîðìóëèðóåò óñëîâèå îñòàíîâà
ìàøèíû Òüþðèíãà íà ñâîåì ñîáñòâåííîì êîäå, ò.å. óñëîâèå
ñàìîïðèìåíèìîñòè. Ïîëó÷åííîå â òåîðåìå ïðîòèâîðå÷èå
äîêàçûâàåò, ÷òî ýòîò ïðåäèêàò íåðàçðåøèì (ò.å. ïðåäïîëîæåíèå î
åãî ðàçðåøèìîñòè áûëî ëîæíûì). Òåì ñàìûì òåîðåìà ׸ð÷à åùå
ðàç äîêàçûâàåò íåðàçðåøèìîñòü ïðîáëåìû ñàìîïðèìåíèìîñòè, à â
òåðìèíàõ òåîðèè ïðåäèêàòîâ ñóùåñòâîâàíèå íåðàçðåøèìîãî
ïðåäëîæåíèÿ: ïðåäëîæåíèÿ î ðàñïîçíàâàíèè îñòàíîâà äëÿ ìàøèíû
Òüþðèíãà íà ñâîåì ñîáñòâåííîì êîäå. Ñóùåñòâîâàíèå íåðàçðåøèìî-
ãî ïðåäèêàòà äîêàçûâàåò íåðàçðåøèìîñòü èñ÷èñëåíèÿ ïðåäèêàòîâ,
ñîäåðæàùåãî àðèôìåòèêó, âñïîìíèì, ÷òî ôîðìóëà G, ïîñòðîåííàÿ
øäåëåì, òàêæå óòâåðæäàåò ñâîþ ñîáñòâåííóþ íåâûâîäèìîñòü, à
ïîñêîëüêó åå äåéñòâèòåëüíî íåëüçÿ íè äîêàçàòü, íè îïðîâåðãíóòü,
òî ýòî ðàâíîçíà÷íî íåðàçðåøèìîñòè ïðîáëåìû ñàìîïðèìåíèìîñòè.
Èíòóèòèâíî íàì óæå ïîíÿòíî, ÷òî íåðàçðåøèìîñòü òåîðèè
ïðåäèêàòîâ ñâÿçàíà ñ íåðåêóðñèâíîñòüþ ìíîæåñòâà âñåõ òåîðåì
ôîðìàëüíîé òåîðèè. Àðèôìåòèçàöèÿ ôîðìàëüíîé òåîðèè S (è
284 285Ãëàâà 15 Òåîðèÿ àëãîðèòìîâ
ñïîñîá, ïðåäëîæåííûé øäåëåì äëÿ àðèôìåòèçàöèè ëþáîé ôîðìàëü-
íîé òåîðèè) ïîçâîëÿåò íàì ãîâîðèòü î íèõ â òåðìèíàõ ðåêóðñèâíûõ
è ðåêóðñèâíî ïåðå÷èñëèìûõ ìíîæåñòâ. Òîãäà ñòàíîâèòñÿ ïîíÿòíûì,
÷òî ñóùåñòâîâàíèå íåðàçðåøèìîãî ïðåäëîæåíèÿ, èñòèííîãî â
ñîäåðæàòåëüíîé òåîðèè, íî íåâûâîäèìîãî â ôîðìàëüíîé òåîðèè,
îçíà÷àåò ñóùåñòâîâàíèå òàêîãî ã¸äåëåâà íîìåðà (íàòóðàëüíîãî
÷èñëà), êîòîðîå íå ïðèíàäëåæèò íè ìíîæåñòâó ã¸äåëåâûõ íîìåðîâ
òåîðåì (âûâîäèìûõ ïðåäëîæåíèé), íè ìíîæåñòâó ã¸äåëåâûõ íîìå-
ðîâ íåâûâîäèìûõ ïðåäëîæåíèé. Èíûìè ñëîâàìè, ýòî îçíà÷àåò, ÷òî
ìíîæåñòâî ã¸äåëåâûõ íîìåðîâ òåîðåì (è, ñëåäîâàòåëüíî, ìíîæåñòâî
ñàìèõ òåîðåì) òåîðèè ïðåäèêàòîâ ïåðâîãî ïîðÿäêà íåðåêóðñèâíî.
Ôîðìàëüíî ýòî äîêàçûâàåòñÿ ñëåäóþùåé òåîðåìîé, äîêàçàòåëü-
ñòâî êîòîðîé èçâåñòíî êàê äîêàçàòåëüñòâî Ðîññåðà òåîðåìû Ãåäåëÿ.
Òåîðåìà 15.12. Ïóñòü ñóùåñòâóþò äâà ðåêóðñèâíî ïåðå÷èñëè-
ìûõ íåïóñòûõ ìíîæåñòâà C
0
è C
1
, òàêèå, ÷òî C
0
∩ C
1
= ∅, è
ñóùåñòâóþò äâà ðåêóðñèâíî ïåðå÷èñëèìûõ ìíîæåñòâà D
0
è D
1
,
òàêèå, ÷òî C
0
⊆D
0
, C
1
⊆D
1
è D
0
∩D
1
= ∅. Òîãäà ìîæíî íàéòè
òàêîå ÷èñëî f, ÷òî f∉D
0
è f∉D
1
.
Äîêàçàòåëüñòâî.
Îïðåäåëèì ìíîæåñòâà C
0
è C
1
ñëåäóþùèì îáðàçîì:
C
0
= {a | ϕ
a
(a) îïðåäåëåíà è ϕ
a
(a) = 0},
C
1
= {a | ϕ
a
(a) îïðåäåëåíà è ϕ
a
(a) ≠ 0}.
Ïîíÿòíî, ÷òî ìíîæåñòâà C
0
è C
1
íåïóñòû è íå ïåðåñåêàþòñÿ.
Ïóñòü ñóùåñòâóþò ìíîæåñòâà D
0
è D
1
, óäîâëåòâîðÿþùèå óñëî-
âèÿì òåîðåìû.
Òîãäà èç òîãî, ÷òî D
0
ðåêóðñèâíî ïåðå÷èñëèìî, ñëåäóåò ñóùåñòâî-
âàíèå ìàøèíû Òüþðèíãà, ïåðå÷èñëÿþùåé ýëåìåíòû D
0
, ò.å. âû÷èñ-
ëÿþùåé ôóíêöèþ ϕ
0
(D
0
), è èç òîãî, ÷òî D
1
ðåêóðñèâíî ïåðå÷èñëèìî,
ñëåäóåò ñóùåñòâîâàíèå ìàøèíû Òüþðèíãà, ïåðå÷èñëÿþùåé
ýëåìåíòû D
1
, ò.å. âû÷èñëÿþùåé ôóíêöèþ ϕ
1
(D
1
). Òîãäà ìîæíî
ïîñòðîèòü ìàøèíó Òüþðèíãà Ì, êîòîðàÿ äëÿ ëþáîãî ÷èñëà a îïðå-
äåëÿåò, ïðèíàäëåæèò ýòî ÷èñëî íóìåðàöèè ϕ
0
èëè íóìåðàöèè ϕ
1
.
Ïðè ýòîì, åñëè ìàøèíà Òüþðèíãà Ì íàõîäèò ÷èñëî a â íóìåðàöèè
ϕ
0
, òî îíà ïå÷àòàåò «1» è îñòàíàâëèâàåòñÿ, à åñëè ÷èñëî a ïðèíàäëå-
æèò íóìåðàöèè ϕ
1
, òî ìàøèíà ïå÷àòàåò «0» è îñòàíàâëèâàåòñÿ. Åñëè
a∉ϕ
0
è a∉ϕ
1
, òî ìàøèíà Òüþðèíãà íå îñòàíàâëèâàåòñÿ.
Ïðåäïîëîæèì, ÷òî ñóùåñòâóåò ÷èñëî f∈D
0
. Òîãäà f∉D
1
.
Ñëåäîâàòåëüíî, ÷èñëî f∈ϕ
0
, ò.å. âñòðå÷àåòñÿ â íóìåðàöèè ϕ
0
, è
f∉ϕ
1
(íå âñòðå÷àåòñÿ â íóìåðàöèè ϕ
1
).
Ïîäàäèì ÷èñëî f íà âõîä ìàøèíû Òüþðèíãà Ì. Òàê êàê f∈ϕ
0
,
òî ìàøèíà íàïå÷àòàåò «1», ò. å. ϕ
f
(f) = 1. Òîãäà, ïî îïðåäåëåíèþ
ìíîæåñòâ C
0
è C
1
, ÷èñëî f ñëåäóåò îòíåñòè ê C
1
: f∈C
1
; à ïîñêîëüêó
C
1
⊆D
1
, òî f∈D
1
, ò.å. f∉D
0
. È íàîáîðîò, åñëè f∈D
1
, òî ϕ
f
(f) = 0,
ñëåäîâàòåëüíî, f∈C
0
, à çíà÷èò è f∈D
0
, ñëåäîâàòåëüíî, f∉D
1
.
Òàêèì îáðàçîì, f íå ïîïàäàåò íè â îäíî, íè â äðóãîå ìíîæåñòâî.
Ýòî ïðîòèâîðå÷èå äîêàçûâàåò òåîðåìó.
Òåîðåìà Ðîññåðà íå òîëüêî äîêàçûâàåò òåîðåìó øäåëÿ â äðóãèõ
òåðìèíàõ, íî è ïîêàçûâàåò, ÷òî î âû÷èñëèìîñòè, âûâîäèìîñòè è
ðàçðåøèìîñòè ìîæíî ãîâîðèòü â òåðìèíàõ ðåêóðñèâíûõ è ðåêóð-
ñèâíî ïåðå÷èñëèìûõ ìíîæåñòâ. Ïîýòîìó ìîæíî ñäåëàòü ñëåäóþùèå
âûâîäû, îáîáùàþùèå ðåçóëüòàòû, ïîëó÷åííûå øäåëåì, ׸ð÷åì,
Ðîññåðîì è äðóãèìè ìàòåìàòèêàìè îòíîñèòåëüíî ðàçðåøèìîñòè
ôîðìàëüíûõ òåîðèé.
Òåîðåìà 15.13. (Òåîðåìà øäåëÿ â ôîðìå Ðîññåðà). Ïóñòü K
òåîðèÿ ïåðâîãî ïîðÿäêà ñ òåìè æå ñèìâîëàìè, ÷òî è òåîðèÿ S, è
ïóñòü, êðîìå òîãî, K óäîâëåòâîðÿåò ñëåäóþùèì óñëîâèÿì:
(1) âñÿêîå ðåêóðñèâíîå âûðàæåíèå âûðàçèìî â K;
(2) ìíîæåñòâî ã¸äåëåâûõ íîìåðîâ ñîáñòâåííûõ àêñèîì òåîðèè
K ðåêóðñèâíî;
(3) âûïîëíåíû óñëîâèÿ: èìååòñÿ ôîðìóëà u ≤ v òàêàÿ, ÷òî
(i) äëÿ âñÿêîé ôîðìóëû A(x) è äëÿ âñÿêîãî íàòóðàëüíîãî k
|
K
A(0) & A(1) & ... & A(k) → ∀x(x ≤ k → A(x));
(ii) äëÿ âñÿêîãî íàòóðàëüíîãî ÷èñëà
|
K
x ≤ k ∨ k ≤ x.
Òîãäà äëÿ òåîðèè K ñïðàâåäëèâà òåîðåìà øäåëÿ â ôîðìå Ðîññåðà:
åñëè òåîðèÿ K íåïðîòèâîðå÷èâà, òî ñóùåñòâóåò íåðàçðåøèìîå â
ýòîé òåîðèè ïðåäëîæåíèå. (Çàìåòèì, ÷òî óñëîâèå (1) âûïîëíÿåòñÿ,
åñëè â K ïðåäñòàâèìà êàæäàÿ ðåêóðñèâíàÿ ôóíêöèÿ).
Îïðåäåëåíèå 15.15. Íàçîâåì òåîðèþ K ðåêóðñèâíî àêñèîìàòèçè-
ðóåìîé, åñëè ñóùåñòâóåò òàêàÿ òåîðèÿ K′ ñ òåì æå, ÷òî è ó K,
ìíîæåñòâîì òåîðåì, ÷òî ìíîæåñòâî ã¸äåëåâûõ íîìåðîâ ñîáñòâåí-
íûõ àêñèîì K′ ðåêóðñèâíî.
Îïðåäåëåíèå 15.16. Òåîðèÿ íàçûâàåòñÿ ýôôåêòèâíî àêñèîìàòè-
çèðîâàííîé, åñëè ñóùåñòâóåò ýôôåêòèâíàÿ ïðîöåäóðà, ïîçâîëÿ-
þùàÿ äëÿ êàæäîé ôîðìóëû ýòîé òåîðèè óçíàâàòü, ÿâëÿåòñÿ ëè
îíà åå àêñèîìîé.
Ñëåäñòâèå. Òåîðåìà øäåëÿ â ôîðìå Ðîññåðà ñïðàâåäëèâà äëÿ
êàæäîãî íåïðîòèâîðå÷èâîãî ðåêóðñèâíî àêñèîìàòèçèðóåìîãî
ðàñøèðåíèÿ òåîðèè S, ò.å. äëÿ êàæäîãî òàêîãî ðàñøèðåíèÿ
ñóùåñòâóåò ïðåäëîæåíèå, íåðàçðåøèìîå â íåì.
286 Ãëàâà 15
Äîêàçàòåëüñòâî.
Òàê êàê âñå ðåêóðñèâíûå îòíîøåíèÿ âûðàçèìû â S, òî îíè
âûðàçèìû è âî âñÿêîì ðàñøèðåíèè S. Òî÷íî òàê æå, åñëè óñëîâèÿ
(i) (ii) âûïîëíåíû â S, òî îíè âûïîëíåíû è âî âñÿêîì ðàñøèðåíèè
S. Ïîýòîìó, íà îñíîâàíèè òåîðåìû 14.9, òåîðåìà øäåëÿ â ôîðìå
Ðîññåðà ïðèìåíèìà ê ëþáîìó íåïðîòèâîðå÷èâîìó ðåêóðñèâíî
àêñèîìàòèçèðóåìîìó ðàñøèðåíèþ òåîðèè S.
Åñëè ïðèíèìàòü òåçèñ ׸ð÷à, òî ïîñëåäíåå ñëåäñòâèå óòâåðæäàåò,
÷òî òåîðèÿ S ñóùåñòâåííî íåïîëíà, ò.å., ÷òî ëþáîå íåïðîòèâîðå÷èâîå
ýôôåêòèâíî àêñèîìàòèçèðîâàííîå ðàñøèðåíèå òåîðèè S èìååò
íåðàçðåøèìûå ïðåäëîæåíèÿ.
Ñïèñîê ëèòåðàòóðû
1. Àðáèá Ì. Ìîçã, ìàøèíà è ìàòåìàòèêà. Ì.: Íàóêà, 1968.
2. Áåðæ Ê. Òåîðèÿ ãðàôîâ è åå ïðèëîæåíèÿ. Ì.: Èçä-âî èíîñòð. ëèò., 1962.
3. Áèðêãîô Ã. Òåîðèÿ ðåøåòîê. Ì.: Íàóêà, 1984.
4. Áóëîñ Äæ., Äæåôôðè Ð. Âû÷èñëèìîñòü è ëîãèêà. Ì.: Ìèð, 1994.
5. Ãèëüáåðò Ä., Áåðíàéñ Ï. Îñíîâàíèÿ ìàòåìàòèêè. Ëîãè÷åñêèå èñ÷èñëåíèÿ
è ôîðìàëèçàöèÿ àðèôìåòèêè. Ì.: Íàóêà, 1979.
6. Ãèíäèêèí Ñ. Ã. Àëãåáðà ëîãèêè â çàäà÷àõ. Ì.: Íàóêà, 1972.
7. Ãëóøêîâ Â.Ì. Ââåäåíèå â êèáåðíåòèêó. Ê.: Èçä-âî ÀÍ ÓÑÑÐ, 1964.
8. Ãîðáàòîâ Â. À. Îñíîâû äèñêðåòíîé ìàòåìàòèêè. Ì.: Âûñø. øê., 1986.
9. Ãýðè Ì., Äæîíñîí Ä. Âû÷èñëèòåëüíûå ìàøèíû è òðóäíîðåøàåìûå çàäà÷è.
Ì.: Ìèð, 1982.
10. Äîíñêîé Â.È. Äèñêðåòíàÿ ìàòåìàòèêà. Ñèìôåðîïîëü: ÑÎÍÀÒ, 2000.
11. Åðøîâ Þ.À., Ïàëþòèí Å.À. Ìàòåìàòè÷åñêàÿ ëîãèêà. Ì.: Íàóêà, 1979.
12. Çàäå Ë. Ïîíÿòèå ëèíãâèñòè÷åñêîé ïåðåìåííîé è åãî ïðèìåíåíèå ê ïðèíÿ-
òèþ ïðîáëåìíûõ ðåøåíèé. Ì.: Ìèð, 1976.
13. Êàððè Õ.Á. Îñíîâàíèÿ ìàòåìàòè÷åñêîé ëîãèêè. Ì.: Ìèð, 1969.
14. Êëèíè Ñ. Ê. Ââåäåíèå â ìåòàìàòåìàòèêó. Ì.: Ìèð, 1957.
15. Êëèíè Ñ. Ê. Ìàòåìàòè÷åñêàÿ ëîãèêà. Ì.: Ìèð, 1973.
16. Êîëìîãîðîâ À. Í., Äðàãàëèí À. Ã. Ââåäåíèå â ìàòåìàòè÷åñêóþ ëîãèêó. Ì.:
Èçä-âî Ìîñê. óí-òà, 1982.
17. Êîôìàí À. Ââåäåíèå â òåîðèþ íå÷åòêèõ ìíîæåñòâ. Ì.: Ðàäèî è ñâÿçü, 1982.
18. Êîýí Ï. Äæ. Òåîðèÿ ìíîæåñòâ è êîíòèíóóì-ãèïîòåçà. Ì.: Ìèð, 1973.
19. Êóçèí Ë. Ò. Îñíîâû êèáåðíåòèêè: Â 2 ò. Ò. 2. Ì.: Ýíåðãèÿ, 1979.
20. Êóçíåöîâ Î. Ï., Àäåëüñîí-Âåëüñêèé Ã. Ì. Äèñêðåòíàÿ ìàòåìàòèêà äëÿ èíæå-
íåðà. Ì.: Ýíåðãèÿ, 1980.
21. Êóðàòîâñêèé Ê., Ìîñòîâñêèé À. Òåîðèÿ ìíîæåñòâ. Ì.: Ìèð, 1970.
22. Êýððîë Ë. Èñòîðèÿ ñ óçåëêàìè. Ì.: Ìèð, 1973.
23. Ëàâðîâ È. À., Ìàêñèìîâà Ë. Ë. Çàäà÷è ïî òåîðèè ìíîæåñòâ, ìàòåìàòè÷åñêîé
ëîãèêå è òåîðèè àëãîðèòìîâ. Ì.: Íàóêà, 1975.
24. Ëèíäîí Ð. Çàìåòêè ïî ëîãèêå. Ì.: Ìèð, 1968.
25. Ëîãè÷åñêèé ïîäõîä ê èñêóññòâåííîìó èíòåëëåêòó / Òåéç Ô., Ãðèáîìîí Ï.,
Ëóè Æ. è äð. Ì.: Ìèð, 1990.
26. Ìàëüöåâ À.È. Àëãåáðàè÷åñêèå ñèñòåìû. Ì.: Íàóêà, 1975.
27. Ìàíèí. Þ. È. Âû÷èñëèìîå è íåâû÷èñëèìîå. Ì.: Ñîâ. Ðàäèî, 1980.
28. Ìåíäåëüñîí Ý. Ââåäåíèå â ìàòåìàòè÷åñêóþ ëîãèêó. Ì.: Íàóêà, 1976.
29. Íàãåëü Ý., Íüþìåí Ä. Òåîðåìà Ãåäåëÿ. Ì.: Çíàíèå, 1970.
30. Íåôåäîâ Â. Í., Îñèïîâà Â. À. Êóðñ äèñêðåòíîé ìàòåìàòèêè. Ì.: ÌÀÈ, 1992.
31. Íîâèêîâ Ï.Ñ. Ýëåìåíòû ìàòåìàòè÷åñêîé ëîãèêè. Ì.: Ôèçìàòãèç, 1959.
32. Íüþñîì Ê. Â., Èâñ Ã. Î ìàòåìàòè÷åñêîé ëîãèêå è ôèëîñîôèè ìàòåìàòèêè.
Ì.: Çíàíèå. 1968.
33. Îðå Î. Òåîðèÿ ãðàôîâ. Ì.: Íàóêà. 1968.
34. Ðîáåðòñ Ô. Ñ. Äèñêðåòíûå ìàòåìàòè÷åñêèå ìîäåëè ñ ïðèëîæåíèÿìè ê
ñîöèàëüíûì, áèîëîãè÷åñêèì è ýêîëîãè÷åñêèì çàäà÷àì. Ì.: Íàóêà, 1986.
35. Ñòîëë Ð. Ìíîæåñòâî, ëîãèêà, àêñèîìàòè÷åñêèå òåîðèè. Ì.: Ïðîñâåùåíèå,
1968.
Îãëàâëåíèå
Ïðåäèñëîâèå ...................................................................... 3
Ãëàâà 1. ÌÍÎÆÅÑÒÂÀ ......................................................... 5
Ãëàâà 2. ÒÅÎÐÈß ÎÒÍÎØÅÍÈÉ ............................................ 15
Ãëàâà 3. ÎÒÎÁÐÀÆÅÍÈß. ÔÓÍÊÖÈÈ .................................... 25
Ãëàâà 4. ÌÎÙÍÎÑÒÜ ÌÍÎÆÅÑÒÂ ....................................... 37
Ãëàâà 5. ÎÒÍÎØÅÍÈÅ ÏÎÐßÄÊÀ .......................................... 61
Ãëàâà 6. ÐÅØÅÒÊÈ ............................................................. 74
Ãëàâà 7. ÑÒÐÎÅÍÈÅ È ÏÐÅÄÑÒÀÂËÅÍÈÅ ÐÅØÅÒÎÊ ................... 90
Ãëàâà 8. ÃÐÀÔÛ ............................................................... 109
Ãëàâà 9. ÁÓËÅÂÀ ÀËÃÅÁÐÀ ................................................. 148
Ãëàâà 10. ËÎÃÈÊÀ ÂÛÑÊÀÇÛÂÀÍÈÉ .................................... 168
Ãëàâà 11. ÔÎÐÌÀËÜÍÛÅ ÒÅÎÐÈÈ. ÈÑ×ÈÑËÅÍÈÅ ÂÛÑÊÀÇÛÂÀÍÈÉ 181
Ãëàâà 12. ÒÅÎÐÈß ÏÐÅÄÈÊÀÒΠÏÅÐÂÎÃÎ ÏÎÐßÄÊÀ .............. 198
Ãëàâà 13. ÀÂÒÎÌÀÒÈ×ÅÑÊÎÅ ÄÎÊÀÇÀÒÅËÜÑÒÂÎ ÒÅÎÐÅÌ ...... 223
Ãëàâà 14. ÑÂÎÉÑÒÂÀ ÒÅÎÐÈÉ ÏÅÐÂÎÃÎ ÏÎÐßÄÊÀ ................. 242
Ãëàâà 15. ÒÅÎÐÈß ÀËÃÎÐÈÒÌÎÂ......................................... 261
Ñïèñîê ëèòåðàòóðû........................................................... 287
36. Òàðàí Ò. À. Îñíîâû äèñêðåòíîé ìàòåìàòèêè: Ó÷åá. ïîñîáèå. Ê.: Ïðîñâ³òà, 1998.
37. Òàðàí Ò. À. Îñíîâû ìàòåìàòè÷åñêîé ëîãèêè. Ê.: ÊÏÈ, 1996.
38. Òàðàí Ò.À., Ìûöåíêî Í.À., Òåìíèêîâà Å.Ë. Ñáîðíèê çàäà÷ ïî äèñêðåòíîé
ìàòåìàòèêå. Ê.: Ïðîñâ³òà, 2001.
39. Òðàõòåíáðîò Â.À. Àëãîðèòìû è âû÷èñëèòåëüíûå àâòîìàòû. Ì.: Ñîâ.
ðàäèî, 1974.
40. Òðàõòåíáðîò Â.À. Àëãîðèòìû è ìàøèííîå ðåøåíèå çàäà÷. Ì.: Ôèçìàò-
ãèç, 1960.
41. Óñïåíñêèé Â. À. Òåîðåìà øäåëÿ î íåïîëíîòå. Ì.: Íàóêà, 1982.
42. Õàðàðè Ô. Òåîðèÿ ãðàôîâ. Ì.: Ìèð, 1973.
43. Õàóñäîðô Ô. Òåîðèÿ ìíîæåñòâ. Ì.: ÎÍÒÈ, 1937.
44. ×åíü ×., Ëè Ð. Ìàòåìàòè÷åñêàÿ ëîãèêà è àâòîìàòè÷åñêîå äîêàçàòåëüñòâî
òåîðåì. Ì.: Íàóêà, 1983.
45. ×åð÷ À. Ââåäåíèå â ìàòåìàòè÷åñêóþ ëîãèêó. Ì.: Èçä-âî èíîñòð. ëèò., 1961.
46. Øèõàíîâè÷ Þ. À. Ââåäåíèå â ñîâðåìåííóþ ìàòåìàòèêó. Ì.: Íàóêà, 1965.
47. Øðåéäåð Þ. À. Ðàâåíñòâî, ñõîäñòâî, ïîðÿäîê. Ì.: Íàóêà, 1971.
48. ßáëîíñêèé Ñ.Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó. Ì.: Íàóêà, 1979.