Справочник от Автор24
Поделись лекцией за скидку на Автор24

Математическая логика и теория алгоритмов. Нормальный алгоритм Маркова. Эквивалентность алгоритмических моделей. Разрешимость алгебраических проблем

  • ⌛ 2020 год
  • 👀 338 просмотров
  • 📌 277 загрузок
Выбери формат для чтения
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Конспект лекции по дисциплине «Математическая логика и теория алгоритмов. Нормальный алгоритм Маркова. Эквивалентность алгоритмических моделей. Разрешимость алгебраических проблем» pdf
Ìàòåìàòè÷åñêàÿ ëîãèêà è òåîðèÿ àëãîðèòìîâ. Ëåêöèÿ 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) ñóùåñòâóåò íàòóðàëüíîå ÷èñëî ngˆA, êîòîðîå îäíîçíà÷íî îïðåäåëÿåòñÿ ïî A; 2) äëÿ âñåõ n, ïðèíàäëåæàùèõ ìíîæåñòâó íàòóðàëüíûõ ÷èñåë N, âûïîëíÿåòñÿ îäíî èç äâóõ óñëîâèé:  ëèáî íå ñóùåñòâóåò îáúåêòà A, ïðèíàäëåæàùåãî ìíîæåñòâó M , òàêîãî, ÷òî n ngˆA;  ëèáî ñóùåñòâóåò åäèíñòâåííûé îáúåêò A, ïðèíàäëåæàùèé M , òàêîé, ÷òî n ngˆA è ýòîò îáúåêò îäíîçíà÷íî âîññòàíàâëèâàåòñÿ ïî 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, . . .. Ïîñòðîèì îäíîìåñòíóþ ôóíêöèþ hˆx, îòëè÷íóþ îò âñåõ ôóíêöèé ìíîæåñòâà M . Òåì ñàìûì ìû äîêàæåì ñóùåñòâîâàíèå ôóíêöèé, íå ÿâëÿþùèõñÿ âû÷èñëèìûìè. ×òîáû ñäåëàòü ïîñòðîåíèå ôóíêöèè hˆx áîëåå íàãëÿäíûì, ñîñòàâèì áåñêîíå÷íóþ ìàòðèöó, ñòðîêàìè êîòîðîé áóäóò ñëóæèòü ïîñëåäîâàòåëüíîñòè çíà÷åíèé ôóíêöèé f0 ˆx, f1 ˆx, f2 ˆx, . . ., à ñòîëáöàìè  íàòóðàëüíûå ÷èñëà 0, 1, 2, . . ., íà êîòîðûõ âû÷èñëÿþòñÿ çíà÷åíèÿ ýòèõ ôóíêöèé. ÌËÒÀ. Ëåêöèÿ 4 2020 22 / 27 Âîïðîñû Îïðåäåëèì ôóíêöèþ hˆx êàê ôóíêöèþ, ïîñëåäîâàòåëüíîñòü çíà÷åíèé êîòîðîé ïîëó÷àåòñÿ èç ïîñëåäîâàòåëüíîñòè çíà÷åíèé, ñòîÿùèõ â ïîñòðîåííîé òàáëèöå íà äèàãîíàëè, óâåëè÷åíèåì êàæäîãî èç íèõ íà åäèíèöó, ò.å. hˆa fa ˆa  1. ÌËÒÀ. Ëåêöèÿ 4 2020 23 / 27 Âîïðîñû Ýòà ôóíêöèÿ ñóùåñòâóåò â ñèëó êîíñòðóêòèâíîãî ïîñòðîåíèÿ, íî ôóíêöèÿ hˆx íå ïðèíàäëåæèò ìíîæåñòâó M , ò.ê. îíà îòëè÷àåòñÿ îò f0 ˆx ñâîèì çíà÷åíèåì äëÿ àðãóìåíòà 0, îò f1 ˆx ñâîèì çíà÷åíèåì äëÿ àðãóìåíòà 1 è ò.ä. Äðóãèìè ñëîâàìè, åñëè hˆx > M , òî ñóùåñòâóåò òàêîé íàòóðàëüíûé íîìåð m, ÷òî äëÿ âñåõ x ñïðàâåäëèâî hˆx fm ˆx. Òîãäà ïîäñòàâëÿÿ âìåñòî ïåðåìåííîé x ÷èñëî m ïîëó÷èì hˆm 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
«Математическая логика и теория алгоритмов. Нормальный алгоритм Маркова. Эквивалентность алгоритмических моделей. Разрешимость алгебраических проблем» 👇
Готовые курсовые работы и рефераты
Купить от 250 ₽
Решение задач от ИИ за 2 минуты
Решить задачу
Помощь с рефератом от нейросети
Написать ИИ
Получи помощь с рефератом от ИИ-шки
ИИ ответит за 2 минуты

Тебе могут подойти лекции

Смотреть все 938 лекций
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot