Математическая логика и теория алгоритмов. Машины Тьюринга

Ìàòåìàòè÷åñêàÿ ëîãèêà è òåîðèÿ àëãîðèòìîâ. Ëåêöèÿ 3. Ìàøèíû Òüþðèíãà. 2020 ÌËÒÀ. Ëåêöèÿ 3 2020 1 / 34 Íåôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Îïðåäåëåíèå Ìàøèíà Òüþðèíãà (ÌÒ) ýòî àâòîìàò, êîòîðûé èìååò ïîòåíöèàëüíî áåñêîíå÷íóþ â îáå ñòîðîíû ëåíòó, ñ÷èòûâàþùóþ ãîëîâêó è óïðàâëÿþùåå óñòðîéñòâî. ÌËÒÀ. Ëåêöèÿ 3 2020 2 / 34 Íåôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Ëåíòà ðàçäåëåíà íà ÿ÷åéêè, â îäíîé ÿ÷åéêå èëè çàïèñàí îäèí ñèìâîë íåêîòîðîãî àëôàâèòà èëè îíà ïóñòà. Ïîòåíöèàëüíàÿ áåñêîíå÷íîñòü ëåíòû ïîíèìàåòñÿ â òîì ñìûñëå, ÷òî â êàæäûé äàííûé ìîìåíò âðåìåíè îíà èìååò êîíå÷íóþ çàïîëíåííóþ ÷àñòü, è âìåñòå ñ òåì ê ýòîé çàïîëíåííîé ÷àñòè âñåãäà ìîæíî äîáàâèòü êàê ñëåâà, òàê è ñïðàâà ëþáûå çàïîëíåííûå ÿ÷åéêè.  êàæäûé ìîìåíò ôóíêöèîíèðîâàíèÿ ìàøèíû Òüþðèíãà ìîæåò áûòü çàïîëíåíî òîëüêî êîíå÷íîå ÷èñëî ÿ÷ååê. Èìååòñÿ íåêîòîðîå êîíå÷íîå ìíîæåñòâî ñèìâîëîâ ëåíòû, êîòîðîå íàçûâàåòñÿ àëôàâèòîì ëåíòû è â êàæäûé ìîìåíò âðåìåíè êàæäàÿ ÿ÷åéêà ëåíòû ìîæåò áûòü çàïîëíåíà íå áîëåå ÷åì îäíèì ñèìâîëîì. Èìååòñÿ ÷èòàþùàÿ ãîëîâêà, êîòîðàÿ â êàæäûé äàííûé ìîìåíò âðåìåíè îáîçðåâàåò îäíó èç ÿ÷ååê ëåíòû. ÌËÒÀ. Ëåêöèÿ 3 2020 3 / 34 Íåôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Ìàøèíà äåéñòâóåò íå íåïðåðûâíî, à ïî òàêòàì, â äèñêðåòíûå ìîìåíòû âðåìåíè. Íà êàæäîì òàêòå ðàáîòû ìàøèíà Òüþðèíãà ìîæåò ñ÷èòàòü ñèìâîë, çàïèñàòü âìåñòî íåãî íîâûé è ñäâèíóòü ãîëîâêó íà îäíó ÿ÷åéêó èëè âëåâî, èëè âïðàâî èëè îñòàâèòü åå íà ìåñòå. Äëÿ òîãî, ÷òîáû ñ ïóñòîé ÿ÷åéêîé ìàøèíà Òüþðèíãà ìîãëà äåéñòâîâàòü òàê æå, êàê è ñ çàïîëíåííîé íåêîòîðûì ñèìâîëîì ÿ÷åéêîé, ââîäèòñÿ ñïåöèàëüíûé ñèìâîë àëôàâèòà, îáîçíà÷àþùèé ïóñòóþ ÿ÷åéêó. Òàêèì îáðàçîì, âñåãäà ìîæíî ñ÷èòàòü, ÷òî â ëþáîé ìîìåíò âðåìåíè ÷èòàþùàÿ ãîëîâêà îáîçðåâàåò ÿ÷åéêó ñ íåêîòîðûì ñèìâîëîì àëôàâèòà. ÌËÒÀ. Ëåêöèÿ 3 2020 4 / 34 Íåôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Ìàøèíà îáëàäàåò íåêîòîðûì êîíå÷íûì ìíîæåñòâîì âíóòðåííèõ ñîñòîÿíèé.  êàæäûé ìîìåíò âðåìåíè ìàøèíà íàõîäèòñÿ â òî÷íîñòè òîëüêî â îäíîì èç ýòèõ ñîñòîÿíèé. Óïðàâëÿþùåå óñòðîéñòâî îòâåòñòâåííî çà ôóíêöèîíèðîâàíèå ìàøèíû Òüþðèíãà ïî òàêòàì. Íà êàæäîì òàêòå óïðàâëÿþùåå óñòðîéñòâî íàõîäèòñÿ â êàêîì ëèáî ñîñòîÿíèè èç êîíå÷íîãî ìíîæåñòâà ñîñòîÿíèé è îáîçðåâàåò ñèìâîë èç êîíå÷íîãî àëôàâèòà ëåíòû.  çàâèñèìîñòè îò òåêóùåãî ñîñòîÿíèÿ è ïðî÷èòàííîãî ñèìâîëà çàïèñûâàåò âìåñòî ïðî÷èòàííîãî ñèìâîëà íîâûé, ñäâèãàåò ãîëîâêó íà îäíó ïîçèöèþ èëè îñòàâëÿåò åå íà ìåñòå è ïåðåõîäèò â íîâîå ñîñòîÿíèå. ÌËÒÀ. Ëåêöèÿ 3 2020 5 / 34 Íåôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà  ìíîæåñòâå ñîñòîÿíèé âûäåëÿþòñÿ äâà ñïåöèàëüíûõ ñîñòîÿíèÿ: íà÷àëüíîå è çàêëþ÷èòåëüíîå. Ìàøèíà Òüþðèíãà íà÷èíàåò ðàáîòó èç íà÷àëüíîãî ñîñòîÿíèÿ è çàâåðøàåò åå, êîãäà ïåðåõîäèò â çàêëþ÷èòåëüíîå ñîñòîÿíèå. ÌËÒÀ. Ëåêöèÿ 3 2020 6 / 34 Ôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Îïðåäåëåíèå Àëôàâèò ýòî íåêîòîðîå êîíå÷íîå ìíîæåñòâî ñèìâîëîâ. Îïðåäåëåíèå Öåïî÷êà íàä àëôàâèòîì ýòî ïîñëåäîâàòåëüíîñòü ñèìâîëîâ àëôàâèòà. Ïðèìåð Àëôàâèò: Σ ˜ 0, 1, öåïî÷êà 0110011. Îïðåäåëåíèå Äëèíà öåïî÷êè ýòî ÷èñëî ñèìâîëîâ â öåïî÷êå. Ïðèìåð Åñëè ε  ïóñòàÿ öåïî÷êà, òî SεS 0, S0110011S ÌËÒÀ. Ëåêöèÿ 3 7. 2020 7 / 34 Ôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Ìíîæåñòâî âñåõ öåïî÷åê íàä àëôàâèòîì Σ îáîçíà÷àåòñÿ Σ‡ . Çàìå÷àíèå Ïóñòàÿ öåïî÷êà ε ÿâëÿåòñÿ öåïî÷êîé íàä ëþáûì àëôàâèòîì. Îïðåäåëåíèå ßçûêîì íàä àëôàâèòîì Σ íàçûâàåòñÿ íåêîòîðîå ïîäìíîæåñòâî ìíîæåñòâà Σ‡ . Îïðåäåëåíèå Êîíêàòåíàöèåé öåïî÷åê x è y íàçûâàåòñÿ öåïî÷êà, ïîëó÷åííàÿ ïðèïèñûâàíèåì ñèìâîëîâ öåïî÷êè y ê öåïî÷êå x ñïðàâà. Äëÿ ïðîèçâîëüíîé öåïî÷êè x è ïóñòîé öåïî÷êè ε ñïðàâåäëèâî ðàâåíñòâî xε εx x, ïîýòîìó öåïî÷êà ε èãðàåò ðîëü åäèíèöû äëÿ îïåðàöèè êîíêàòåíàöèè. ÌËÒÀ. Ëåêöèÿ 3 2020 8 / 34 Ôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà Îïðåäåëåíèå Ìàøèíîé Òüþðèíãà íàçûâàåòñÿ ñåìåðêà âèäà: T ˆ K, Σ, δ, q1 , q0 , ε, ‡, ãäå K  êîíå÷íîå ìíîæåñòâî ñîñòîÿíèé, Σ  àëôàâèò ëåíòû, q1  íà÷àëüíîå ñîñòîÿíèå, q0  çàêëþ÷èòåëüíîå ñîñòîÿíèå, ε  ñèìâîë äëÿ îáîçíà÷åíèÿ ïóñòîé ÿ÷åéêè, ‡  ñïåöèàëüíûé ñèìâîë  ðàçäåëèòåëü öåïî÷åê íà ëåíòå, δ ôóíêöèÿ ïåðåõîäîâ, êîòîðàÿ îïèñûâàåò ïîâåäåíèå ìàøèíû Òüþðèíãà è ïðåäñòàâëÿåò ñîáîé îòîáðàæåíèå âèäà δ  K  Σ K  Σ  S, ãäå S ˜R, L, E  íàïðàâëåíèÿ ñäâèãà ãîëîâêè ïî ëåíòå. ÌËÒÀ. Ëåêöèÿ 3 2020 9 / 34 Ôîðìàëüíîå îïðåäåëåíèå ìàøèíû Òüþðèíãà  ñîîòâåòñòâèè ñ íåôîðìàëüíûì òðåáîâàíèÿì ê àëãîðèòìó â îïðåäåëåíèè ìàøèíû Òüþðèíãà ìîæíî âûäåëèòü ñëåäóþùèå õàðàêòåðíûå ÷åðòû: 1) èìååòñÿ âû÷èñëèòåëü  ñàìà ìàøèíà Òüþðèíãà; 2) ìàøèíà Òüþðèíãà ðàáîòàåò ïî òàêòàì, ÷òî ñîîòâåòñòâóåò äèñêðåòíîñòè âûïîëíåíèÿ àëãîðèòìà; 3) ñîáëþäàåòñÿ òðåáîâàíèå êîíå÷íîñòè àëãîðèòìà, ò.ê. ìíîæåñòâà K è Σ êîíå÷íû, à, ñëåäîâàòåëüíî, êîíå÷íî è îòîáðàæåíèå δ ; 4) òðåáîâàíèå äåòåðìèíèðîâàííîñòè Ìàøèíû Òüþðèíãà ñîîòâåòñòâóåò äåòåðìèíèðîâàííîñòè îòîáðàæåíèÿ δ (ýòî çíà÷èò, ÷òî ìíîæåñòâî êîìàíä ìàøèíû Òüþðèíãà íå ñîäåðæèò ðàçëè÷íûõ êîìàíä ñ îäèíàêîâûìè ëåâûìè ÷àñòÿìè). Âûâîä: äëÿ ñîãëàñîâàíèÿ îïðåäåëåíèÿ ìàøèíû Òüþðèíãà ñ òðåáîâàíèÿìè ê àëãîðèòìó òðåáóåòñÿ ðàññìàòðèâàòü òîëüêî äåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà (ýòî òðåáîâàíèå óæå ó÷òåíî â îïðåäåëåíèè ôóíêöèè ïåðåõîäîâ). ÌËÒÀ. Ëåêöèÿ 3 2020 10 / 34 Êîíôèãóðàöèè Îïðåäåëåíèå Êîíôèãóðàöèåé ìàøèíû Òüþðèíãà T ˆK, Σ, δ, q1 , q0 , ε, ‡ íàçûâàåòñÿ t `αqaβ e, ãäå α  öåïî÷êà ñëåâà îò ãîëîâêè, α > Σ‡ ; q  ñîñòîÿíèå ìàøèíû Òüþðèíãà, q > K ; a  ñèìâîë ïîä ãîëîâêîé, a > Σ; β  öåïî÷êà ñïðàâà îò ãîëîâêè, β > Σ‡ . Êîíôèãóðàöèÿ `11 ‡ 1q6 ‡ ‡e îçíà÷àåò, ÷òî ìàøèíà Òüþðèíãà íàõîäèòñÿ â ñîñòîÿíèè q6 , èìååò íà ëåíòå öåïî÷êó 11 ‡ 1 ‡ ‡, ïðè÷åì, ñëåâà îò ãîëîâêè íàõîäèòñÿ ÷àñòü ýòîé öåïî÷êè 11 ‡ 1, ÷èòàþùàÿ ãîëîâêà îáîçðåâàåò ñèìâîë ‡, ñïðàâà îò ãîëîâêè íàõîäèòñÿ öåïî÷êà ‡. ÌËÒÀ. Ëåêöèÿ 3 2020 11 / 34 Êîíôèãóðàöèè Îïðåäåëåíèå Ýëåìåíò ôóíêöèè ïåðåõîäîâ qa pbr (ãäå q, p > K , a, b > Σ, r > S) íàçûâàåòñÿ êîìàíäîé ìàøèíû Òüþðèíãà è îïèñûâàåò îäèí òàêò åå ôóíêöèîíèðîâàíèÿ. Îäèí òàêò ðàáîòû îçíà÷àåò ñëåäóþùåå: åñëè â ñîñòîÿíèè q ìàøèíà Òüþðèíãà îáîçðåâàåò íà ëåíòå ñèìâîë a, òî îíà ïåðåõîäèò â ñîñòîÿíèå p, çàïèñûâàåò âìåñòî a íîâûé ñèìâîë b è ñäâèãàåò ãîëîâêó â íàïðàâëåíèè r. ÌËÒÀ. Ëåêöèÿ 3 2020 12 / 34 Êîíôèãóðàöèè Îïðåäåëåíèå Êîíôèãóðàöèÿ `αqaβ e íåïîñðåäñòâåííî ïåðåõîäèò â êîíôèãóðàöèþ `αn qn an βn e, åñëè íîâàÿ êîíôèãóðàöèÿ ïîëó÷èëàñü â ðåçóëüòàòå ïðèìåíåíèÿ îäíîé êîìàíäû ê èñõîäíîé êîíôèãóðàöèè: 1) êîìàíäà qa qn an E, òîãäà α αn , β βn (`αn qaβn e `αn qn an βn e), 2) êîìàíäà qa qn bR, òîãäà à) β x ε, β an βn , αn αb (`αqaan βn e `αbqn an βn e), á) β ε, an ε, βn ε, αn αb (`αqaεe `αbqn εεe), 3) êîìàíäà qa qn bL, òîãäà à) α x ε, α αn an , βn bβ (`αn an qaβ e `αn qn an bβ e), á) α ε, an ε, αn ε, βn bβ (`εqaβ e `εqn εbβ e), 4) åñëè â ìíîæåñòâå êîìàíä îòñóòñòâóåò êîìàíäà ñ ëåâîé ÷àñòüþ qa; òî ìàøèíà Òüþðèíãà îêàçûâàåòñÿ áëîêèðîâàííîé, ò.å. îíà íèêàê íå ðåàãèðóåò íà ñèìâîë a è äî áåñêîíå÷íîñòè ïðîäîëæàåò îñòàâàòüñÿ â îäíîé è òîé æå êîíôèãóðàöèè.      ÌËÒÀ. Ëåêöèÿ 3 2020 13 / 34 Êîíôèãóðàöèè Îïðåäåëåíèå Êîíôèãóðàöèÿ t ïåðåõîäèò â êîíôèãóðàöèþ p (îáîçíà÷àåòñÿ t åñëè ñóùåñòâóþò òàêèå êîíôèãóðàöèè t1 , t2 , . . . , tk , ÷òî: t t1  t2  t3  . . .  tk ‡ p), p. Îïðåäåëåíèå Êîíôèãóðàöèÿ `αq1 aβ e ìàøèíû Òüþðèíãà T ˆK, Σ, δ, q1 , q0 , ε, ‡, ñîäåðæàùàÿ íà÷àëüíîå ñîñòîÿíèå q1 , íàçûâàåòñÿ íà÷àëüíîé, à êîíôèãóðàöèÿ `αq0 aβ e; ñîäåðæàùàÿ çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 , íàçûâàåòñÿ çàêëþ÷èòåëüíîé, ïðè÷åì åñëè â äàííîé êîíôèãóðàöèè öåïî÷êà α ñëåâà îò ãîëîâêè ïóñòàÿ (α ε), òî ñîîòâåòñòâåííî íà÷àëüíàÿ êîíôèãóðàöèÿ íàçûâàåòñÿ ñòàíäàðòíîé íà÷àëüíîé êîíôèãóðàöèåé, à çàêëþ÷èòåëüíàÿ  ñòàíäàðòíîé çàêëþ÷èòåëüíîé. ÌËÒÀ. Ëåêöèÿ 3 2020 14 / 34 Ñïîñîáû ïðåäñòàâëåíèÿ ÌÒ 1) ïðåäñòàâëåíèå ìàøèíû Òüþðèíãà ñ ïîìîùüþ ìíîæåñòâà êîìàíä. Ïðàâèëà ôîðìèðîâàíèÿ êîìàíä: à) íà÷àëüíîìó ïóíêòó àëãîðèòìà ñòàâèòñÿ â ñîîòâåòñòâèå íà÷àëüíîå ñîñòîÿíèå q1 ìàøèíû Òüþðèíãà; á) öèêëû â àëãîðèòìå ðåàëèçóþòñÿ òàê, ÷òîáû ïîñëåäíåå äåéñòâèå öèêëà ñîîòâåòñòâîâàëî ïåðåõîäó â òî ñîñòîÿíèå, êîòîðîå ñîîòâåòñòâóåò íà÷àëó öèêëà; â) ïîñëåäîâàòåëüíîå âûïîëíåíèå ïóíêòîâ àëãîðèòìà îáåñïå÷èâàåòñÿ ïåðåõîäîì â ñîîòâåòñòâóþùèå ýòèì ïóíêòàì ñìåæíûå ñîñòîÿíèÿ; ã) ïîñëåäíèé ïóíêò àëãîðèòìà âûçûâàåò ïåðåõîä â çàêëþ÷èòåëüíîå ñîñòîÿíèå q0 . ÌËÒÀ. Ëåêöèÿ 3 2020 15 / 34 Ñïîñîáû ïðåäñòàâëåíèÿ ÌÒ 2) ïðåäñòàâëåíèå ìàøèíû Òüþðèíãà ãðàôîì. Äëÿ òîãî, ÷òîáû ïðåäñòàâèòü ìàøèíó Òüþðèíãà â âèäå ãðàôà, íàäî êàæäîå ñîñòîÿíèå ñäåëàòü âåðøèíîé ýòîãî ãðàôà, à êàæäîé êîìàíäå ïîñòàâèòü â ñîîòâåòñòâèå ïîìå÷åííóþ äóãó. Êîìàíäå pa qbr ñîîòâåòñòâóåò äóãà èç âåðøèíû p â âåðøèíó q ñ ìåòêîé a br. Äëÿ òîãî, ÷òîáû îáîçíà÷èòü íà÷àëüíóþ è êîíå÷íóþ âåðøèíû, èõ îáû÷íî âûäåëÿþò ñïåöèàëüíûì îáðàçîì (Y  íà÷àëüíàÿ âåðøèíà, X  êîíå÷íàÿ âåðøèíà). ÌËÒÀ. Ëåêöèÿ 3 2020 16 / 34 Ñïîñîáû ïðåäñòàâëåíèÿ ÌÒ 3) ïðåäñòàâëåíèå ìàøèíû Òüþðèíãà òàáëèöåé. Åñëè êàæäîìó ñîñòîÿíèþ ïîñòàâèì â ñîîòâåòñòâèå ñòîëáåö òàáëèöû, à êàæäîìó ñèìâîëó  ñòðîêó, òî äëÿ îäíîé êîìàíäû pa qbr íà ïåðåñå÷åíèè ñòðîêè a (÷èòàåìûé ñèìâîë a) è ñòîëáöà p (èñõîäíîå ñîñòîÿíèå p) óêàçûâàåòñÿ âûïîëíÿåìîå äåéñòâèå brq (çàïèñàòü ñèìâîë b, ïåðåéòè â ñîñòîÿíèå q è ñäâèíóòü ãîëîâêó â íàïðàâëåíèè r). ÌËÒÀ. Ëåêöèÿ 3 2020 17 / 34 Ïðèìåð Ïðèìåð Ïîñòðîèòü ìàøèíó Òüþðèíãà, êîòîðàÿ äëÿ çàäàííîé öåïî÷êè èç 0 è 1 ñòðîèò åå èíâåðñèþ, ò. å. çàìåíÿåò â öåïî÷êå âñå çíàêè 0 íà 1 è çíàêè 1 íà 0. Áóäåì ïðåäïîëàãàòü, ÷òî â íà÷àëüíûé ìîìåíò ìàøèíà Òüþðèíãà îáîçðåâàåò ïåðâûé ñèìâîë èñõîäíîé öåïî÷êè, à ïîñëå ïðåîáðàçîâàíèÿ öåïî÷êè ãîëîâêà âîçâðàùàåòñÿ ê íà÷àëüíîìó ñèìâîëó ðåçóëüòàòà. ÌËÒÀ. Ëåêöèÿ 3 2020 18 / 34 Ïðèìåð Àëãîðèòì â ñëîâåñíîé ôîðìå: à) Ïîêà íå ε, ÷èòàåì 0 èëè 1, çàïèñûâàÿ èíâåðñèþ ïðî÷èòàííûõ ñèìâîëîâ  ñèìâîëû 1 èëè 0 ñîîòâåòñòâåííî, è ñäâèãàåì ãîëîâêó ïðàâî. Òåì ñàìûì ìû ïîñëåäîâàòåëüíî èíâåðòèðóåì êàæäûé ñèìâîë è â ðåçóëüòàòå ñäâèãàåì ãîëîâêó â ïîçèöèþ, íåïîñðåäñòâåííî ñëåäóþùóþ çà ïðåîáðàçîâàííîé öåïî÷êîé. Çà ïðåîáðàçîâàííîé öåïî÷êîé íàõîäèòñÿ ÿ÷åéêà ñ "ïóñòûì" ñèìâîëîì. á) ×èòàåì ε, ïèøåì ε, ñäâèãàåì ãîëîâêó âëåâî. Ñëåäîâàòåëüíî, ãîëîâêà îáîçðåâàåò ïîñëåäíèé ñèìâîë ðåçóëüòèðóþùåé öåïî÷êè. Òåïåðü íåîáõîäèìî âåðíóòüñÿ ê íà÷àëó öåïî÷êè. â) Ïîêà íå ε, ÷èòàåì 0 èëè 1 ñ âîññòàíîâëåíèåì è ñäâèãàåì ãîëîâêó âëåâî (òåðìèí "÷èòàòü ñ âîññòàíîâëåíèåì" îçíà÷àåò, ÷òî ïðî÷èòàííûé ñèìâîë çàïèñûâàåòñÿ íà ëåíòó áåç èçìåíåíèÿ). ã) ×èòàåì ε ñ âîññòàíîâëåíèåì è ñäâèãàåì ãîëîâêó âïðàâî; òåì ñàìûì óñòàíîâèëè ãîëîâêó íà ïåðâûé ñèìâîë ðåçóëüòèðóþùåé öåïî÷êè. ÌËÒÀ. Ëåêöèÿ 3 2020 19 / 34 Ïðèìåð Êîìàíäû ìàøèíû Òüþðèíãà: q1 1 q1 0R, q1 0 q1 1R, q1 ε q2 εL, q2 0 q2 0L, q2 1 q2 1L, q2 ε q0 R. Òàáëèöà: q1 q2 0 1Rq1 0Lq1 1 0Rq1 1Lq1 ε εLq2 εRq0 Ðèñ.: 1 ÌËÒÀ. Ëåêöèÿ 3 2020 20 / 34 Ïðèìåð Òðåíàæåð ìîæíî íàéòè ïî ññûëêå: http://kpolyakov.spb.ru/prog/turing.htm ÌËÒÀ. Ëåêöèÿ 3 2020 21 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Ìû ìîæåì ñ êàæäîé ìàøèíîé Òüþðèíãà ñâÿçàòü íåêîòîðûé àëãîðèòì. Âîçüìåì ïðîèçâîëüíóþ öåïî÷êó íàä àëôàâèòîì Σ, çàïèøåì åå íà ëåíòå è çàïóñòèì ìàøèíó Òüþðèíãà T ˆK, Σ, δ, q1 , q0 , ε, ‡ èç íà÷àëüíîãî ñîñòîÿíèÿ q1 . Åñëè ìàøèíà Òüþðèíãà êîãäàíèáóäü îñòàíîâèòñÿ, òî ïîÿâèâøóþñÿ íà ëåíòå öåïî÷êó ìîæíî ðàññìàòðèâàòü êàê ðåçóëüòàò ðàáîòû àëãîðèòìà. Ìîæíî íà ëþáîì àëôàâèòå ðàññìàòðèâàòü ìàøèíû Òüþðèíãà, êîòîðûå: à) íèêîãäà íå ïðåêðàùàþò ðàáîòó; á) íà ëþáûõ èñõîäíûõ äàííûõ ìàøèíà Òüþðèíãà âñåãäà çàêîí÷èò ñâîþ ðàáîòó ÷åðåç êîíå÷íîå ÷èñëî øàãîâ; â) íà íåêîòîðûõ èñõîäíûõ äàííûõ ìàøèíà Òüþðèíãà ðàáîòàåò áåñêîíå÷íî, à íà íåêîòîðûõ çàâåðøàåò ðàáîòó. ÌËÒÀ. Ëåêöèÿ 3 2020 22 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Äëÿ ïðîñòîòû áóäåì çàïèñûâàòü íàòóðàëüíûå ÷èñëà â åäèíè÷íîì (óíàðíîì) êîäå, â êîòîðîì ÷èñëî k ïðåäñòàâëÿåòñÿ ñëîâîì 11 . . . 1 1k , ´ ¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¶ k ñîñòîÿùèì èç k åäèíèö. Äëÿ ðàçäåëåíèÿ ÷èñëîâûõ àðãóìåíòîâ 1x1 , 1x2 , . . . , 1xn ôóíêöèè f ˆx1 , x2 , . . . , xn  áóäåì èñïîëüçîâàòü ñèìâîë  ðàçäåëèòåëü ‡. Òîãäà àðãóìåíòû ôóíêöèè f ˆx1 , x2 , . . . , xn  âñåãäà èìåþò 1x1 ‡ 1x2 ‡ . . . ‡ 1xn . Ïðèìåð Ïóñòü äàíà ôóíêöèÿ f ˆx, y, z x  y  z, òîãäà çàïèñü àðãóìåíòîâ ýòîé ôóíêöèè íà ëåíòå ìàøèíû Òüþðèíãà èìååò âèä 1x ‡ 1y ‡ 1z , à çíà÷åíèå ôóíêöèè  âèä 1xyz . ÌËÒÀ. Ëåêöèÿ 3 2020 23 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Îïðåäåëåíèå Ìàøèíà Òüþðèíãà T ˆK, Σ, δ, q1 , q0 , ε, ‡ âû÷èñëÿåò ôóíêöèþ f ˆx1 , x2 , . . . , xn , åñëè âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ: 1) äëÿ ëþáûõ x1 , x2 , . . . , xn , ïðèíàäëåæàùèõ îáëàñòè îïðåäåëåíèÿ Domˆf  ôóíêöèè f , ìàøèíà Òüþðèíãà èç íà÷àëüíîé êîíôèãóðàöèè, èìåÿ íà ëåíòå ïðåäñòàâëåíèå àðãóìåíòîâ x1 , x2 , . . . , xn , ïåðåõîäèò â çàêëþ÷èòåëüíóþ êîíôèãóðàöèþ, èìåÿ íà ëåíòå ïðåäñòàâëåíèå çíà÷åíèÿ ôóíêöèè: ‡ A1 q1 A2 B1 q0 B2 , A1 A2 1x1 ‡ . . . ‡ 1xn , B1 B2 1f ˆx1 ,x2 ,...,xn  . 2) äëÿ ëþáûõ x1 , x2 , . . . , xn , íå ïðèíàäëåæàùèõ Domˆf , ìàøèíà Òüþðèíãà T èç íà÷àëüíîé êîíôèãóðàöèè, èìåÿ íà ëåíòå ïðåäñòàâëåíèå ‡ àðãóìåíòîâ x1 , x2 , . . . , xn , ðàáîòàåò áåñêîíå÷íî: A1 q1 A2 ª.   ÌËÒÀ. Ëåêöèÿ 3 2020 24 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Îïðåäåëåíèå Åñëè íà÷àëüíàÿ êîíôèãóðàöèÿ ÿâëÿåòñÿ ñòàíäàðòíîé íà÷àëüíîé êîíôèãóðàöèåé, à çàêëþ÷èòåëüíàÿ  ñòàíäàðòíîé çàêëþ÷èòåëüíîé, òî ãîâîðÿò, ÷òî ìàøèíà Òüþðèíãà ïðàâèëüíî âû÷èñëÿåò ôóíêöèþ f : ‡ 1)q1 1x1 ‡ . . . ‡ 1xn q0 1f ˆx1 ,x2 ,...,xn  ; ‡ 2)q1 1x1 ‡ . . . ‡ 1xn q0 ª.   Îïðåäåëåíèå Ôóíêöèÿ íàçûâàåòñÿ âû÷èñëèìîé (ïðàâèëüíî âû÷èñëèìîé), åñëè ñóùåñòâóåò ìàøèíà Òüþðèíãà, âû÷èñëÿþùàÿ (ïðàâèëüíî âû÷èñëÿþùàÿ) ýòó ôóíêöèþ. Çàìå÷àíèå  äàëüíåéøåì, åñëè íå îãîâîðåíî ïðîòèâíîå, ïîä âû÷èñëèìîñòüþ áóäåì ïîíèìàòü ïðàâèëüíóþ âû÷èñëèìîñòü. ÌËÒÀ. Ëåêöèÿ 3 2020 25 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Äëÿ òîãî, ÷òîáû äîêàçàòü âû÷èñëèìîñòü ôóíêöèè, à â ïåðñïåêòèâå è ñóùåñòâîâàíèå àëãîðèòìà, íåîáõîäèìî ïîñòðîèòü ñîîòâåòñòâóþùóþ ìàøèíó Òüþðèíãà. Íåïîñðåäñòâåííûå ïîñòðîåíèÿ òðóäîåìêè, à ÷àñòî ïðåäñòàâëÿþò ïðàêòè÷åñêè íåâûïîëíèìûé ïðîöåññ â ñèëó ãðîìîçäêîñòè è íåîáîçðèìîñòè òàêîãî ïîñòðîåíèÿ. Ïîýòîìó íåîáõîäèìî ðàññìîòðåòü îïåðàöèè íàä ìàøèíàìè Òüþðèíãà, ÷òîáû ïîëó÷èòü èíñòðóìåíòû äëÿ ïîñòðîåíèÿ ñëîæíûõ ìàøèí Òüþðèíãà èç ïðîñòûõ ìàøèí. ÌËÒÀ. Ëåêöèÿ 3 2020 26 / 34 Ôóíêöèè, âû÷èñëèìûå ïî Òüþðèíãó Ïðèìåð Ïîñòðîèòü ìàøèíó Òüþðèíãà, ïðàâèëüíî âû÷èñëÿþùóþ ôóíêöèþ f ˆx, y x  y  1.  ñîîòâåòñòâèè ñ îïðåäåëåíèåì òðåáóåìàÿ ìàøèíà Òüþðèíãà äîëæíà âûïîëíÿòü ñëåäóþùèå äåéñòâèÿ: q1 ‡ , x  y 0, q0 1xy1 , x  y  1 A 0. ª œ Óêàçàííûå äåéñòâèÿ âûïîëíÿåò ñëåäóþùàÿ ìàøèíà Òüþðèíãà: ÌËÒÀ. Ëåêöèÿ 3 2020 27 / 34 Êîìïîçèöèÿ ìàøèí Òüþðèíãà Òåîðåìà 4.1. Êîìïîçèöèÿ äâóõ âû÷èñëèìûõ ôóíêöèé åñòü ôóíêöèÿ âû÷èñëèìàÿ. Äîêàçàòåëüñòâî. Ïóñòü gˆx f2 ˆf1 ˆx, ãäå f1 , f2  ïðàâèëüíî âû÷èñëèìûå ôóíêöèè. Òîãäà ñóùåñòâóþò äâå ìàøèíû Òüþðèíãà, ïðàâèëüíî âû÷èñëÿþùèå f1 è f2 : T1 T2 K1 , Σ1 , δ1 , q11 , q01 , ε1 , ‡1  ˆ 4.1 K2 , Σ2 , δ2 , q12 , q02 , ε2 , ‡2 . ˆ 4.2 ˆ ˆ Åñëè íóæíî, ïåðåîáîçíà÷èì ñèìâîëû ïóñòîé ÿ÷åéêè è ðàçäåëèòåëÿ òàê, ÷òîáû îíè ñîâïàäàëè: ε1 ε2 ε, ‡1 ‡2 ‡, à òàêæå ïåðåîáîçíà÷èì K1 è K2 òàê, ÷òîáû îíè íå ïåðåñåêàëèñü. ÌËÒÀ. Ëåêöèÿ 3 2020 28 / 34 Êîìïîçèöèÿ ìàøèí Òüþðèíãà Ïîñòðîèì ìàøèíó Òüþðèíãà: T q ˆ K1 8 K2 ƒ˜q01 , Σ1 8 Σ2 , Tq12 ˆδ1 8 δ2 , q11 , q02 , ε, ‡ 4.3 ˆ 01 Ïîñòðîåííàÿ ìàøèíà Òüþðèíãà T âûïîëíÿåò ñëåäóþùèå äåéñòâèÿ: q11 1x ‡ ˆT  q011f ˆx 1 1 q12 1f1 ˆx ‡ ˆT  q021f ˆf ˆx. 2 1 2 Åñëè gˆx íå îïðåäåëåíà â òî÷êå x  ýòî çíà÷èò, ÷òî íå îïðåäåëåíà ëèáî f1 ˆx, ëèáî f2 ˆt, ãäå t f1 ˆx.  ýòîì ñëó÷àå T çàöèêëèòñÿ ñîîòâåòñòâåííî ëèáî íà ïåðâîì ó÷àñòêå, ðàáîòàÿ êàê T1 , ëèáî íà âòîðîì, ðàáîòàÿ êàê T2 . Îïðåäåëåíèå Ìàøèíà Òüþðèíãà T íàçûâàåòñÿ êîìïîçèöèåé ìàøèí Òüþðèíãà T1 è T2 , åñëè îíà ïîñòðîåíà ïî ïðàâèëàì ˆ4.1, ˆ4.2, ˆ4.3. ÌËÒÀ. Ëåêöèÿ 3 2020 29 / 34 Êîìïîçèöèÿ ìàøèí Òüþðèíãà Òåîðåìà 4.2. Êîìïîçèöèÿ n ïðàâèëüíî âû÷èñëèìûõ ôóíêöèé f1 ˆx, f2 ˆx, . . . , fn ˆx, åñòü ïðàâèëüíî âû÷èñëèìàÿ ôóíêöèÿ f1 ˆf2 ˆ. . . fn ˆx . . .. Òåîðåìà 4.3. Ôóíêöèÿ, ïðàâèëüíî âû÷èñëèìàÿ íà ìàøèíå Òüþðèíãà ñ îáû÷íîé ëåíòîé, ïðàâèëüíî âû÷èñëèìà íà ìàøèíå Òüþðèíãà ñ ïðàâîé ïîëóëåíòîé. Òåîðåìà 4.4. Ôóíêöèÿ, ïðàâèëüíî âû÷èñëèìàÿ íà ìàøèíå Òüþðèíãà ñ îáû÷íîé ëåíòîé, ïðàâèëüíî âû÷èñëèìà íà ìàøèíå Òüþðèíãà ñ ëåâîé ïîëóëåíòîé. ÌËÒÀ. Ëåêöèÿ 3 2020 30 / 34 Ñóïåðïîçèöèÿ ìàøèí Òüþðèíãà Îïðåäåëåíèå Ìàøèíà Òüþðèíãà âû÷èñëÿåò ôóíêöèþ f ñ âîññòàíîâëåíèåì, åñëè: ‡ q1 1x1 ‡ . . . ‡ 1xn q0 1f ˆx1 ,...,xn  ‡ 1x1 ‡ . . . ‡ 1xn .  Âû÷èñëåíèå ôóíêöèè ñ âîññòàíîâëåíèåì îçíà÷àåò ðàáîòó ìàøèíû Òüþðèíãà ñ ñîõðàíåíèåì èñõîäíûõ äàííûõ. Ïðèâåäåííîå îïðåäåëåíèå ïîçâîëÿåò ïîëó÷àòü íà ëåíòå ñíà÷àëà ðåçóëüòàò, à çàòåì èñõîäíûå äàííûå. Òåîðåìà 4.5. Âñÿêàÿ ïðàâèëüíî âû÷èñëèìàÿ ôóíêöèÿ ïðàâèëüíî âû÷èñëèìà ñ âîññòàíîâëåíèåì. Òåîðåìà 4.6. Ñóïåðïîçèöèÿ âû÷èñëèìûõ ôóíêöèé  âû÷èñëèìàÿ ôóíêöèÿ. ÌËÒÀ. Ëåêöèÿ 3 2020 31 / 34 Ðàçâåòâëåíèå Îïðåäåëåíèå Ôóíêöèÿ f ˆx1 , x2 , . . . , xn  ïîëó÷åíà èç ïðåäèêàòà Pˆx1 , x2 , . . . , xn , ôóíêöèé g1 ˆx1 , x2 , . . . , xn  è g2 ˆx1 , x2 , . . . , xn  îïåðàòîðîì ðàçâåòâëåíèÿ, åñëè f ˆx1 , x2 , . . . , xn  œ g1 ˆx1 , x2 , . . . , xn , åñëè SPˆx1 , x2 , . . . , xn S g2 ˆx1 , x2 , . . . , xn , åñëè SPˆx1 , x2 , . . . , xn S 1, 0. Îïðåäåëåíèå Ïðåäèêàò Pˆx1 , x2 , . . . , xn  íàçûâàåòñÿ ïðàâèëüíî âû÷èñëèìûì, åñëè åãî õàðàêòåðèñòè÷åñêàÿ ôóíêöèÿ ïðàâèëüíî âû÷èñëèìà. Òåîðåìà 4.7. Ðàçâåòâëåíèå ê ïðàâèëüíî âû÷èñëèìûì ôóíêöèÿì ïî ïðàâèëüíî âû÷èñëèìîìó ïðåäèêàòó ÿâëÿåòñÿ ïðàâèëüíî âû÷èñëèìûì. ÌËÒÀ. Ëåêöèÿ 3 2020 32 / 34 Ïîâòîðåíèå Îïðåäåëåíèå Ðàññìîòðèì ôóíêöèþ gˆx, êîòîðàÿ ëþáîìó çíà÷åíèþ x ñòàâèò â ñîîòâåòñòâèå ðåçóëüòàò âûïîëíåíèÿ ñëåäóþùåé ïîñëåäîâàòåëüíîñòè äåéñòâèé: "ïîêà Pˆx âû÷èñëÿòü x f ˆx." Òàêàÿ ôóíêöèÿ gˆx íàçûâàåòñÿ ïîâòîðåíèåì f ˆx ïî ïðåäèêàòó Pˆx. Òåîðåìà 4.8. Ïîâòîðåíèå ïðàâèëüíî âû÷èñëèìîé ôóíêöèè ïî ïðàâèëüíî âû÷èñëèìîìó ïðåäèêàòó ïðàâèëüíî âû÷èñëèìî. Ñëåäñòâèå Ôóíêöèÿ, çàäàííàÿ îïåðàòîðîì ïðèìèòèâíîé ðåêóðñèè íàä âû÷èñëèìûìè ôóíêöèÿìè, âû÷èñëèìà. ÌËÒÀ. Ëåêöèÿ 3 2020 33 / 34 Òåçèñ Òüþðèíãà Òåçèñ Òüþðèíãà Âñÿêèé àëãîðèòì ìîæåò áûòü ðåàëèçîâàí ìàøèíîé Òüþðèíãà. ÌËÒÀ. Ëåêöèÿ 3 2020 34 / 34