Математическая логика и теория алгоритмов. Нормальный алгоритм Маркова. Эквивалентность алгоритмических моделей. Разрешимость алгебраических проблем
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Ìàòåìàòè÷åñêàÿ ëîãèêà è òåîðèÿ àëãîðèòìîâ.
Ëåêöèÿ 4.
Íîðìàëüíûé àëãîðèòì Ìàðêîâà. Ýêâèâàëåíòíîñòü
àëãîðèòìè÷åñêèõ ìîäåëåé. Ðàçðåøèìîñòü
àëãîðèòìè÷åñêèõ ïðîáëåì.
2020
ÌËÒÀ. Ëåêöèÿ 4
2020
1 / 27
Îïðåäåëåíèå àëãîðèòìà Ìàðêîâà
Ðàññìîòðèì äðóãóþ òî÷êó çðåíèÿ íà àëãîðèòì: êàæäûé àëãîðèòì
ïðåîáðàçóåò èñõîäíûå äàííûå â ðåçóëüòàòû, ïðè÷åì èñõîäíûå äàííûå è ðåçóëüòàòû êàêèìòî ñïîñîáîì çàïèñûâàþòñÿ â êà÷åñòâå òåêñòîâûõ ñòðîê. Òîãäà âñÿêèé àëãîðèòì ïðåîáðàçóåò çàïèñü äàííûõ â
çàïèñü ðåçóëüòàòîâ. Ïîýòîìó ìîæíî ñêàçàòü, ÷òî âñÿêèé àëãîðèòì
ïðåîáðàçóåò öåïî÷êó íàä íåêîòîðûì àëôàâèòîì â äðóãèå öåïî÷êè.
ÌËÒÀ. Ëåêöèÿ 4
2020
2 / 27
Îïðåäåëåíèå àëãîðèòìà Ìàðêîâà
Ïóñòü Σ àëôàâèò, à P, Q öåïî÷êè íàä ýòèì àëôàâèòîì. Ðàññìîòðèì ïðàâèëà ïîäñòàíîâêè âèäà
P
Q
P
QY
Ïåðâîå èç ýòèõ ïðàâèë íàçûâàåòñÿ îáû÷íûì ïðàâèëîì ïîäñòàíîâêè,
à âòîðîå çàêëþ÷èòåëüíûì. Îáà ýòè ïðàâèëà ïðèìåíÿþòñÿ êî âõîäíûì öåïî÷êàì îäèíàêîâî, ðàçíèöà çàêëþ÷àåòñÿ ëèøü â òîì, ÷òî ïîñëå çàêëþ÷èòåëüíîãî ïðàâèëà ðàáîòà àëãîðèòìà çàêàí÷èâàåòñÿ, à ïîñëå îáû÷íîãî ìîæåò áûòü ïðîäîëæåíà. Ïðèìåíåíèå ïðàâèëà P Q Y
ê öåïî÷êå x çàêëþ÷àåòñÿ â òîì, ÷òî ñàìîå ëåâîå âõîæäåíèå P â x çàìåíÿåòñÿ íà Q:
x yPz yQz.
Ïîëó÷åííîå ñëîâî íàçûâàåòñÿ ðåçóëüòàòîì ïðèìåíåíèÿ ìàðêîâñêîé
ïîäñòàíîâêè P, Q ê ñëîâó x.
ÌËÒÀ. Ëåêöèÿ 4
2020
3 / 27
Îïðåäåëåíèå àëãîðèòìà Ìàðêîâà
Ïðåîáðàçóåìîå ñëîâî
541551678
øðàì
ôóíêöèÿ
êíèãà
ìàìà
äîæäü
Ìàðêîâñêàÿ ïîäñòàíîâêà
(41551,00)
(ðà, àð)
ε, Γ
(êí,ε)
ε, ε
(äà, Ò)
ÌËÒÀ. Ëåêöèÿ 4
Ðåçóëüòàò
50078
øàðì
Γôóíêöèÿ
èãà
ìàìà
íå ïðèìåíèìà
2020
4 / 27
Îïðåäåëåíèå àëãîðèòìà Ìàðêîâà
Îïðåäåëåíèå
Àëãîðèòìîì Ìàðêîâà (íîðìàëüíûì àëãîðèòìîì) íàä àëôàâèòîì
Σ íàçûâàåòñÿ óïîðÿäî÷åííàÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü ïðàâèë
ïîäñòàíîâêè:
P1 Q1 Y
...
Pk
Qk
Y
Àëãîðèòì Ìàðêîâà ðàáîòàåò ñëåäóþùèì îáðàçîì: íà êàæäîì øàãå
ïðèìåíÿåòñÿ ïðàâèëî ïîäñòàíîâêè ñ ìèíèìàëüíî âîçìîæíûì íîìåðîì. Àëãîðèòì çàêàí÷èâàåò ðàáîòó ëèáî ïîñëå ïðèíÿòèÿ çàêëþ÷èòåëüíîãî ïðàâèëà, ëèáî ïðè îòñóòñòâèè ïðèìåíèìûõ ïðàâèë.
ÌËÒÀ. Ëåêöèÿ 4
2020
5 / 27
Àëãîðèòì Ìàðêîâà
Ïðèìåð
Ïîñòðîèòü àëãîðèòì Ìàðêîâà, âû÷èñëÿþùèé ôóíêöèþ
f x, y
x y 1, x B 2,
0,
x A 2.
Î÷åâèäíî, ÷òî äëÿ âû÷èñëåíèÿ ôóíêöèè íåîáõîäèìî âûïîëíèòü àíàëèç óñëîâèÿ x A 2. Åñëè àðãóìåíòû, êàê è ðàíåå, áóäåì çàïèñûâàòü
â óíàðíîì êîäå, òî íàëè÷èå õîòÿ áû òðåõ åäèíèö ïåðåä çíàêîì ""
îçíà÷àåò ñïðàâåäëèâîñòü x A 2.
ÌËÒÀ. Ëåêöèÿ 4
2020
6 / 27
Àëãîðèòì Ìàðêîâà
Òîãäà ôóíêöèþ f x, y âû÷èñëÿåò ñëåäóþùèé àëãîðèòì Ìàðêîâà:
Uf 111
1Y
1
®
1®
®
®
®
®
Y
Ñëåäóåò îáðàòèòü âíèìàíèå íà ïîðÿäîê ïðàâèë â àëãîðèòìå Uf . Åñëè ïîìåíÿòü ìåñòàìè ïåðâîå è âòîðîå ïðàâèëî, òî àëãîðèòì áóäåò
âû÷èñëÿòü ôóíêöèþ x y 1 äëÿ ëþáûõ àðãóìåíòîâ.
ÌËÒÀ. Ëåêöèÿ 4
2020
7 / 27
Àëãîðèòì Ìàðêîâà
Òðåíàæåð ìîæíî íàéòè ïî ññûëêå:
http://kpolyakov.spb.ru/prog/nma.htm
ÌËÒÀ. Ëåêöèÿ 4
2020
8 / 27
Àëãîðèòì Ìàðêîâà
Çàìå÷àíèå
Èíîãäà àëãîðèòì Ìàðêîâà äîëæåí âûïîëíÿòü ðàçëè÷íûå äåéñòâèÿ
íà ó÷àñòêàõ öåïî÷êè, ðàçíûõ ïî ìåñòîïîëîæåíèþ, íî îäèíàêîâûõ ïî
ñòðóêòóðå. Äëÿ ðàçëè÷åíèÿ òàêèõ ó÷àñòêîâ óäîáíî ïðèìåíÿòü áåãóùèé ìàðêåð, êîòîðûé ñòàâèòñÿ â íà÷àëå öåïî÷êè ñ ïîìîùüþ ïðàâèëà
ε ®. Ýòî ïðàâèëî ìîæåò áûòü òîëüêî ñàìûì ïîñëåäíèì â ïîñëåäîâàòåëüíîñòè ïðàâèë, ò.ê. â ïðîòèâíîì ñëó÷àå îíî çàïðåòèò âîçìîæíîñòü
ïðèíÿòèÿ âñåõ ñòîÿùèõ çà íèì ïðàâèë ïî òîé ïðè÷èíå, ÷òî ε åñòü â
ëþáîé öåïî÷êå íà ëþáîì ìåñòå.
Íàïðèìåð, àëãîðèòì Ìàðêîâà U ε
1 íèêîãäà íå îñòàíîâèòñÿ íà
ëþáîé öåïî÷êå, âñòàâëÿÿ äî áåñêîíå÷íîñòè ïåðåä íåé ñèìâîëû 1.
ÌËÒÀ. Ëåêöèÿ 4
2020
9 / 27
Âû÷èñëèìîñòü ôóíêöèé ïî Ìàðêîâó
Îïðåäåëåíèå
Ôóíêöèÿ f , çàäàííàÿ íà ìíîæåñòâå ñëîâ àëôàâèòà Σ, íàçûâàåòñÿ íîðìàëüíî âû÷èñëèìîé, åñëè íàéäåòñÿ òàêîå ðàñøèðåíèå Σ àëôàâèòà
Σ è òàêîé àëãîðèòì Ìàðêîâà â Σ , ÷òî êàæäîå ñëîâî x â àëôàâèòå
Σ, ïðèíàäëåæàùåå îáëàñòè îïðåäåëåíèÿ ôóíêöèè, ïåðåðàáàòûâàåòñÿ
àëãîðèòìîì â f x.
ÌËÒÀ. Ëåêöèÿ 4
2020
10 / 27
Ïðèíöèï Ìàðêîâà
Ïðèíöèï Ìàðêîâà
Âñÿêèé àëãîðèòì ìîæåò áûòü ðåàëèçîâàí àëãîðèòìîì Ìàðêîâà.
ÌËÒÀ. Ëåêöèÿ 4
2020
11 / 27
Ýêâèâàëåíòíîñòü àëãîðèòìè÷åñêèõ ìîäåëåé
Òåîðåìà 5.3.
Âñÿêàÿ ÷àñòè÷íîðåêóðñèâíàÿ ôóíêöèÿ âû÷èñëèìà ïî Òüþðèíãó.
Òåîðåìà 5.4.
Ëþáàÿ âû÷èñëèìàÿ ïî Òüþðèíãó ôóíêöèÿ ÿâëÿåòñÿ ÷àñòè÷íîðåêóðñèâíîé ôóíêöèåé.
Òåîðåìà 5.5.
Äëÿ ïðîèçâîëüíîé ìàøèíû Òüþðèíãà ìîæíî ïîñòðîèòü ýêâèâàëåíòíûé àëãîðèòì Ìàðêîâà.
ÌËÒÀ. Ëåêöèÿ 4
2020
12 / 27
Ýêâèâàëåíòíîñòü àëãîðèòìè÷åñêèõ ìîäåëåé
Òåîðåìà 5.6.
Äëÿ ïðîèçâîëüíîãî àëãîðèòìà Ìàðêîâà ìîæíî ïîñòðîèòü ýêâèâàëåíòíóþ ìàøèíó Òüþðèíãà.
Ñëåäñòâèå.
Îïðåäåëåíèÿ àëãîðèòìà â âèäå ìàøèíû Òüþðèíãà, àëãîðèòìà Ìàðêîâà è ÷àñòè÷íîðåêóðñèâíîé ôóíêöèè ýêâèâàëåíòíû.
ÌËÒÀ. Ëåêöèÿ 4
2020
13 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Íåîáõîäèìîñòü íóìåðàöèè ïðîèçâîëüíûõ îáúåêòîâ âûçâàíà íåîáõîäèìîñòüþ àíàëèçà ðàçëè÷íûõ çàäà÷, êîòîðûå äîëæíû îáðàáàòûâàòü
àëãîðèòìû â êà÷åñòâå èñõîäíîé èíôîðìàöèè. Ðàññìàòðèâàÿ îïðåäåëåíèå àëãîðèòìà â âèäå ÷àñòè÷íîðåêóðñèâíîé ôóíêöèè èëè ìàøèíû
Òüþðèíãà, ìû ïðèõîäèì ê ïîíèìàíèþ òîãî, ÷òî èñõîäíàÿ èíôîðìàöèÿ äëÿ ýòèõ àëãîðèòìè÷åñêèõ ìîäåëåé ïðåäñòàâèìà â îäíîì è òîì
æå âèäå â âèäå íàòóðàëüíûõ ÷èñåë.
ÌËÒÀ. Ëåêöèÿ 4
2020
14 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Ñ÷èòàåòñÿ, ÷òî ââåäåíà ñèñòåìà Ãåäåëåâñêîé íóìåðàöèè äëÿ âñåõ îáúåêòîâ A, ïðèíàäëåæàùèõ íåêîòîðîìó ìíîæåñòâó M , åñëè âûïîëíÿþòñÿ ñëåäóþùèå äâà òðåáîâàíèÿ:
1) ñóùåñòâóåò íàòóðàëüíîå ÷èñëî ngA, êîòîðîå îäíîçíà÷íî îïðåäåëÿåòñÿ ïî A;
2) äëÿ âñåõ n, ïðèíàäëåæàùèõ ìíîæåñòâó íàòóðàëüíûõ ÷èñåë N, âûïîëíÿåòñÿ îäíî èç äâóõ óñëîâèé:
ëèáî íå ñóùåñòâóåò îáúåêòà A, ïðèíàäëåæàùåãî ìíîæåñòâó M , òàêîãî, ÷òî n ngA;
ëèáî ñóùåñòâóåò åäèíñòâåííûé îáúåêò A, ïðèíàäëåæàùèé M , òàêîé,
÷òî n ngA è ýòîò îáúåêò îäíîçíà÷íî âîññòàíàâëèâàåòñÿ ïî n.
ÌËÒÀ. Ëåêöèÿ 4
2020
15 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Èçâåñòíî, ÷òî ëþáàÿ ìàøèíà Òüþðèíãà
T
K, Σ, δ, q1 , q0 , ε, ,
çàäàåòñÿ ìíîæåñòâîì êîìàíä âèäà
pi aj
pk al r,
ãäå pi , pk > K ñîñòîÿíèÿ, aj , ai > Σ ñèìâîëû àëôàâèòà ëåíòû,
r > R, L, E íàïðàâëåíèå äâèæåíèÿ ãîëîâêè.
Çàíóìåðóåì âñå ñîñòîÿíèÿ è ñèìâîëû àëôàâèòà íà- òóðàëüíûìè ÷èñëàìè: K
p 0 , p 1 , . . . , p z è Σ
a0 , a1 , . . . , as . Áóäåì ñ÷èòàòü, ÷òî
ñîñòîÿíèå p0 q1 ñ íóëåâûì íîìåðîì íà÷àëüíîå è ñîñòîÿíèå pz q0
ñ ìàêñèìàëüíûì íîìåðîì z çàêëþ÷èòåëüíîå.
ÌËÒÀ. Ëåêöèÿ 4
2020
16 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Ðàññìîòðèì ñíà÷àëà îäíó êîìàíäó pi aj
pk al r,. Èíäåêñû i, j, k, l
ýòî íàòóðàëüíûå ÷èñëà, êîòîðûå ìîæíî çàïèñàòü â êàêîéëèáî ñèñòåìå ñ÷èñëåíèÿ. Âûáåðåì äâîè÷íóþ ñèñòåìó ñ÷èñëåíèÿ, òîãäà â çàïèñè êàæäîé êîìàíäû èñïîëüçóþòñÿ òîëüêî ñëåäóþùèå ñèìâîëû:
p, a, 0, 1, R, L, E.
ÌËÒÀ. Ëåêöèÿ 4
2020
17 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó ñèìâîëó äåñÿòè÷íóþ öèôðó:
p
1, a
2, 0
3, 1
4, R
5, L
6, E
7.
Òîãäà êàæäîé êîìàíäå ñòàâèòñÿ â ñîîòâåòñòâèå öåëîå ÷èñëî â äåñÿòè÷íîé ñèñòåìå ñ÷èñëåíèÿ.
Íàïðèìåð, êîìàíäå ñ äåñÿòè÷íûìè èíäåêñàìè
p3 a0
p5 a2 R
èëè â äâîè÷íîì ýêâèâàëåíòå
p11 a0 p101 a10 R
ñîîòâåòñòâóåò ÷èñëî 1442314342435.
ÌËÒÀ. Ëåêöèÿ 4
2020
18 / 27
Ãåäåëåâñêèé íîìåð ìàøèíû Òüþðèíãà
Ïîñêîëüêó ëþáàÿ ìàøèíà Òüþðèíãà çàäàåòñÿ íàáîðîì êîìàíä, òî
êàæäîé êîìàíäå ñòàâèòñÿ â ñîîòâåòñòâèå îäíî ÷èñëî, à âñåìó íàáîðó
êîìàíä îäíî äëèííîå ÷èñëî, ïîëó÷åííîå ïîñëåäîâàòåëüíîé çàïèñüþ ñîîòâåòñòâóþùèõ êàæäîé êîìàíäå ÷èñåë.
Äëÿ îäíîçíà÷íîãî îïðåäåëåíèÿ òàêîãî äëèííîãî ÷èñëà áóäåì ôîðìèðîâàòü åãî èç îòäåëüíûõ ÷èñåë â âîçðàñòàþùåé ïîñëåäîâàòåëüíîñòè.
ÌËÒÀ. Ëåêöèÿ 4
2020
19 / 27
Âîïðîñû
Îïðåäåëèâ íóìåðàöèþ Ãåäåëÿ äëÿ ìàøèí Òüþðèíãà, ìû ìîæåì ñòàâèòü âîïðîñ î òîì, êàêèå ñâîéñòâà àëãîðèòìîâ ìîæíî ðàñïîçíàòü ïî
íîìåðàì ìàøèí Òüþðèíãà.
Âîïðîñ
Ñóùåñòâóåò ëè àëãîðèòì, ïîçâîëÿþùèé äëÿ ïðîèçâîëüíîãî íîìåðà
n ìàøèíû Òüþðèíãà óçíàòü, îñòàíîâèòñÿ ëè ñîîòâåòñòâóþùèé àëãîðèòì, îáðàáàòûâàÿ çàäàííûå èñõîäíûå äàííûå, èëè îí çàöèêëèòñÿ?
×àñòíûì ñëó÷àåì ýòîé ïðîáëåìû ÿâëÿåòñÿ àíàëèç ôóíêöèè, êîòîðóþ âû÷èñëÿåò çàäàííàÿ ìàøèíà Òüþðèíãà: íåîáõîäèìî îïðåäåëèòü,
ïðèìèòèâíî ðåêóðñèâíà ýòà ôóíêöèÿ èëè íåò.
ÌËÒÀ. Ëåêöèÿ 4
2020
20 / 27
Âîïðîñû
Ïî òåçèñó Òüþðèíãà êàæäûé àëãîðèòì ìîæåò áûòü ðåàëèçîâàí ìàøèíîé Òüþðèíãà. Âîçìîæíîñòü íóìåðàöèè ìàøèí Òüþðèíãà îçíà÷àåò, ÷òî ëþáîé âû÷èñëèìîé ôóíêöèè ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå
åå íîìåð.
Âîïðîñ
Âñå ëè ôóíêöèè âû÷èñëèìû?
Äëÿ îòâåòà íà âîïðîñ íåîáõîäèìî âûÿñíèòü ñóùåñòâîâàíèå ôóíêöèé,
íå âû÷èñëèìûõ íèêàêèìè àëãîðèòìàìè. Èçâåñòíî, ÷òî ëþáîé êîðòåæ
a1 , a2 , . . . , an ìîæíî ïðåäñòàâèòü îäíèì íàòóðàëüíûì ÷èñëîì, èñïîëüçóÿ ñîîòâåòñòâóþùóþ íóìåðàöèþ. Ïîýòîìó ìîæåì ðàññìîòðåòü
òîëüêî ôóíêöèè îäíîãî àðãóìåíòà.
ÌËÒÀ. Ëåêöèÿ 4
2020
21 / 27
Âîïðîñû
Äîïóñòèì, ÷òî âñå îäíîìåñòíûå ôóíêöèè íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë âû÷èñëèìû. Òîãäà êàæäîé âû÷èñëèìîé ôóíêöèè ìîæíî
ïîñòàâèòü â ñîîòâåòñòâèå íàòóðàëüíîå ÷èñëî ãåäåëåâñêèé íîìåð
ìàøèíû Òüþðèíãà, âû÷èñëÿþùåé ýòó ôóíêöèþ.
Ïóñòü
M
ìíîæåñòâî
âñåõ
âû÷èñëèìûõ
ôóíêöèé,
M f0 x, f1 x, f2 x, . . .. Ïîñòðîèì îäíîìåñòíóþ ôóíêöèþ hx,
îòëè÷íóþ îò âñåõ ôóíêöèé ìíîæåñòâà M . Òåì ñàìûì ìû äîêàæåì
ñóùåñòâîâàíèå ôóíêöèé, íå ÿâëÿþùèõñÿ âû÷èñëèìûìè.
×òîáû ñäåëàòü ïîñòðîåíèå ôóíêöèè hx áîëåå íàãëÿäíûì, ñîñòàâèì
áåñêîíå÷íóþ ìàòðèöó, ñòðîêàìè êîòîðîé áóäóò ñëóæèòü ïîñëåäîâàòåëüíîñòè çíà÷åíèé ôóíêöèé f0 x, f1 x, f2 x, . . ., à ñòîëáöàìè íàòóðàëüíûå ÷èñëà 0, 1, 2, . . ., íà êîòîðûõ âû÷èñëÿþòñÿ çíà÷åíèÿ ýòèõ
ôóíêöèé.
ÌËÒÀ. Ëåêöèÿ 4
2020
22 / 27
Âîïðîñû
Îïðåäåëèì ôóíêöèþ hx êàê ôóíêöèþ, ïîñëåäîâàòåëüíîñòü çíà÷åíèé êîòîðîé ïîëó÷àåòñÿ èç ïîñëåäîâàòåëüíîñòè çíà÷åíèé, ñòîÿùèõ â
ïîñòðîåííîé òàáëèöå íà äèàãîíàëè, óâåëè÷åíèåì êàæäîãî èç íèõ íà
åäèíèöó, ò.å.
ha fa a 1.
ÌËÒÀ. Ëåêöèÿ 4
2020
23 / 27
Âîïðîñû
Ýòà ôóíêöèÿ ñóùåñòâóåò â ñèëó êîíñòðóêòèâíîãî ïîñòðîåíèÿ, íî
ôóíêöèÿ hx íå ïðèíàäëåæèò ìíîæåñòâó M , ò.ê. îíà îòëè÷àåòñÿ îò
f0 x ñâîèì çíà÷åíèåì äëÿ àðãóìåíòà 0, îò f1 x ñâîèì çíà÷åíèåì äëÿ
àðãóìåíòà 1 è ò.ä.
Äðóãèìè ñëîâàìè, åñëè hx > M , òî ñóùåñòâóåò òàêîé íàòóðàëüíûé
íîìåð m, ÷òî äëÿ âñåõ x ñïðàâåäëèâî hx fm x. Òîãäà ïîäñòàâëÿÿ âìåñòî ïåðåìåííîé x ÷èñëî m ïîëó÷èì hm fm m fm m 1,
÷òî íåâîçìîæíî. Ïîëó÷åííîå ïðîòèâîðå÷èå äîêàçûâàåò ñóùåñòâîâàíèå ôóíêöèé, íå ïðèíàäëåæàùèõ ìíîæåñòâó âû÷èñëèìûõ ôóíêöèé.
Âîçíèêàþò íîâûå âîïðîñû î ñóùåñòâîâàíèè èëè íåñóùåñòâîâàíèè àëãîðèòìîâ, ðåøàþùèõ íåêîòîðóþ ïîñòàâëåííóþ ïðîáëåìó.
ÌËÒÀ. Ëåêöèÿ 4
2020
24 / 27
Ïðîáëåìà îñòàíîâêè ìàøèíû Òüþðèíãà
Ïðîáëåìà îñòàíîâêè àëãîðèòìà çàêëþ÷àåòñÿ â îïðåäåëåíèè äëÿ ïðîèçâîëüíîãî àëãîðèòìà è ïðîèçâîëüíûõ èñõîäíûõ äàííûõ, ïîñòóïàþùèõ íà âõîä ýòîìó àëãîðèòìó, ïðèíöèïà îáðàáîòêè óêàçàííûì àëãîðèòìîì ïðåäëîæåííûõ èñõîäíûõ äàííûõ:
îñòàíîâèòñÿ àëãîðèòì ÷åðåç íåêîòîðîå êîíå÷íîå ÷èñëî øàãîâ ñ ïîëó÷åííûì â ïðîöåññå ðàáîòû ðåçóëüòàòîì;
íå îñòàíîâèòñÿ íèêîãäà.
Òåîðåìà 5.1.
Ïðîáëåìà îñòàíîâêè íåðàçðåøèìà.
Ñëåäñòâèå.
Ïðîáëåìà ðåçóëüòàòèâíîñòè ïðîãðàììû íåðàçðåøèìà.
Íåðàçðåøèìîñòü ïðîáëåìû îñòàíîâêè íå èñêëþ÷àåò òîãî, ÷òî äëÿ
îòäåëüíûõ êëàññîâ ìàøèí Òüþðèíãà îíà ìîæåò áûòü ðåøåíà.
ÌËÒÀ. Ëåêöèÿ 4
2020
25 / 27
Ïðîáëåìà ðàñïîçíàâàíèÿ ïåðåâîäèìîñòè
Äëÿ ëþáîé çàäàííîé ìàøèíû Òüþðèíãà è ëþáûõ äâóõ êîíôèãóðàöèé t1 , t2 â íåé òðåáóåòñÿ âûÿñíèòü: åñëè â êà÷åñòâå íà÷àëüíîé êîíôèãóðàöèè âçÿòà t1 , òî ïåðåéä¼ò ëè ìàøèíà (ïîñëå êîíå÷íîãî ÷èñëà
òàêòîâ) â êîíôèãóðàöèþ t2 èëè íåò?
Òåîðåìà.
Ïðîáëåìà ïåðåâîäèìîñòè àëãîðèòìè÷åñêè íåðàçðåøèìà.
ÌËÒÀ. Ëåêöèÿ 4
2020
26 / 27
Òåîðåìà Ðàéñà.
Òåîðåìà Ðàéñà.
Íèêàêîå íåòðèâèàëüíîå ñâîéñòâî âû÷èñëèìûõ ôóíêöèé íå ÿâëÿåòñÿ
àëãîðèòìè÷åñêè ðàçðåøèìûì.
Êàêîå áû ñâîéñòâî âû÷èñëèìûõ ôóíêöèé íè âçÿòü (ïåðèîäè÷íîñòü,
îãðàíè÷åííîñòü, ðàâåíñòâî äðóãîé, íàïåð¼ä çàäàííîé ôóíêöèè è ò.
ä.), íåëüçÿ ïîñòðîèòü îáùèé àëãîðèòì, íàïðèìåð, ìàøèíó Òüþðèíãà, êîòîðûé ïî ïðîèçâîëüíîìó àëãîðèòìó U îïðåäåëÿë áû, îáëàäàåò
âû÷èñëÿåìàÿ èì ôóíêöèÿ fU ýòèì ñâîéñòâîì èëè íåò.
ÌËÒÀ. Ëåêöèÿ 4
2020
27 / 27
