6. Проблема соответствий Поста. Алгоритмическая неразрешимость проблемы соответствий Поста. Многоголовочные конечные автоматы (1162497), страница 2
Текст из файла (страница 2)
. . $ αN−1 $ αN a,⇑2 ⇑1ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ2. Çàòåì àâòîìàò DM , ñèíõðîííî ïåðåìåùàÿ îáåñ÷èòûâàþùèå ãîëîâêè, ñðàâíèâàåò ïîáóêâåííîñëîâà α0 è α1 è ïðîâåðÿåò, ÷òî α1 ýòîêîíôèãóðàöèÿ ÌÒ M , îáðàçóþùàÿñÿ çà îäèíòàêò åå ðàáîòû èç êîíôèãóðàöèè α0 :$ α0 $ α1 $ . . . $ αi−1 $ αi $ . . . $ αN−1 $ αN a,⇑ 2 ⇑1ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ3. Ýòî ñèíõðîííîå ïåðåìåùåíèå ñ÷èòûâàþùèõãîëîâîê è ïîáóêâåííîå ñðàâíåíèå ïîñëåäîâàòåëüíîèäóùèõ ôðàãìåíòîâ αi−1 è αi äëÿ ïîäòâåðæäåíèÿòîãî, ÷òî αi ïîëó÷åíà èç αi−1 çà îäèí òàêòðàáîòû MT M , ïðîâîäèòñÿ äëÿ âñåõ i, i ≥ 1 .$ α0 $ α1 $ . . . $ αi−1 $ αi $ . .
. $ αN−1 $ αN a,⇑2⇑1ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ4. Íî êàê òîëüêî ñ÷èòûâàþùàÿ ãîëîâêà ⇑1 ïðèïðîâåðêå î÷åðåäíîé ïàðû ôðàãìåíòîâ αN−1 è αNîáíàðóæèâàåò, ÷òî ôðàãìåíò αN = uq0v ýòîçàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ MT M$ α0 $ α1 $ . . . $ αi−1 $ αi $ . . . $ αN−1 $ αN a,⇑2⇑1¾âèæóq0 ¿äâóõãîëîâî÷íûé àâòîìàò DM ïåðåõîäèò â ðåæèìóñïåøíîãî çàâåðøåíèÿ âû÷èñëåíèÿ.ÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛ5. Äëÿ óñïåøíîãî çàâåðøåíèÿ âû÷èñëåíèÿàâòîìàò DM ïðîâåðÿåò, ÷òî ñ÷èòûâàþùàÿãîëîâêà ⇑1 äîñòèãàåò ïî ïðî÷òåíèè ôðàãìåíòà αNãðàíè÷íîãî ìàðêåðà a$ α0 $ α1 $ . .
. $ αi−1 $ αi $ . . . $ αN−1 $ αN a,⇑2⇑1à çàòåì ïåðåìåùàåò ê ýòîìó ìàðêåðóñ÷èòûâàþùóþ ãîëîâêó ⇑2 è ïåðåõîäèò âôèíàëüíîå ñîñòîÿíèå.QEDÌÍÎÃÎÃÎËÎÂÎ×ÍÛÅ ÊÎÍÅ×ÍÛÅÀÂÒÎÌÀÒÛÈç äîêàçàííîãî Óòâåðæäåíèÿ 6.5 è òåîðåìû îáàëãîðèòìè÷åñêîé íåðàçðåøèìîñòè ïðîáëåìûîñòàíîâà äëÿ ìàøèí Òüþðèíãà ñëåäóåò Òåîðåìà6.4 îá àëãîðèòìè÷åñêîé íåðàçðåøèìîñòèïðîáëåìû ïóñòîòû äëÿ äâóõãîëîâî÷íûõäåòåðìèíèðîâàííûõ êîíå÷íûõ àâòîìàòîâ.ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈß 1912 ã. íîðâåæñêèé ìàòåìàòèê Àêñåëü Òóýïðåäëîæèë îäíó èç ñàìûõ ïðîñòûõ ìîäåëåéâû÷èñëåíèé. Âïîñëåäñòâèå À.À. Ìàðêîâïðåäëîæèë íàçûâàòü ñèñòåìû âû÷èñëåíèé òàêîãîâèäà àññîöèàòèâíûìè èñ÷èñëåíèÿìè,ïîñêîëüêó îíè îòíîñÿòñÿ ê àëãåáðàè÷åñêèìñèñòåìàì ñ îäíîé îïåðàöèåé, ïîä÷èíÿþùåéñÿåäèíñòâåííîìó çàêîíó çàêîíó àññîöèàòèâíîñòè.Ôàêòè÷åñêè, àññîöèàòèâíîå èñ÷èñëåíèå ýòîíàáîð ïðàâèë ïåðåïèñûâàíèÿ ñëîâ ïóòåì çàìåíûîäíèõ ïîäñëîâ äðóãèìè.
Íî äàæå äëÿ òàêîéïðîñòîé ìîäåëè âû÷èñëåíèé íåêîòîðûå çàäà÷èîêàçûâàþòñÿ àëãîðèòìè÷åñêè íåðàçðåøèìûìè.ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÏóñòü çàäàí êîíå÷íûé àëôàâèòΣ = {a1 , a2 , . . . , an } è êîíå÷íîå ìíîæåñòâîóïîðÿäî÷åííûõ ïàð ñëîâ â ýòîì àëôàâèòåK = {(u1 , v1 ), (u2 , v2 ), . . . , (uk , vk )} .Îïðåäåëèì ïðàâèëî âûâîäà ñëîâ ñëåäóþùèìîáðàçîì: ñëîâî wb íåïîñðåäñòâåííî âûâîäèìî èçKb ),ñëîâà w â ñèñòåìå K (îáîçíà÷àåòñÿ w −→wåñëè ñóùåñòâóåò òàêîå i, 1 ≤ i ≤ k, , äëÿ êîòîðîãîb = w 0 vi w 00 .w = w 0 ui w 00 è wÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÑëîâî wm ñ÷èòàåòñÿ âûâîäèìûì èç ñëîâà w0 âñèñòåìå K , åñëè ñóùåñòâóåò êîíå÷íàÿïîñëåäîâàòåëüíîñòü íåïîñðåäñòâåííî âûâîäèìûõäðóã èç äðóãà ñëîâKKKKKw0 −→ w1 −→ w2 −→ · · · −→ wm−1 −→ wm .Îòíîøåíèå âûâîäèìîñòè â ñèñòåìå K áóäåìKîáîçíà÷àòü w0 −→∗ wm .Ñèñòåìà óïîðÿäî÷åííûõ ïàð ñëîâ K ñ ââåäåííûìKîòíîøåíèåì íåïîñðåäñòâåííîé âûâîäèìîñò−→íàçûâàåòñÿ ïîëóñèñòåìîé Òóý .ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÏðèìåð.KÏóñòü K = {(abb, bab), (aba, b)} .
ÒîãäàKKKaabbaa −→ ababaa −→ abba −→ baba −→ bbÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÏîëóñèñòåìû Òóý ïîñëóæèëè ïåðâîîñíîâîé äëÿìíîãèõ äðóãèõ ìàòåìàòè÷åñêèõ ìîäåëåé ìàøèíÒüþðèíãà, íîðìàëüíûõ àëãîðèòôìîâ Ìàðêîâà,ôîðìàëüíûõ ãðàììàòèê è ïð.Äëÿ ïîëóñèñòåì Òóý èíòåðåñ ïðåäñòàâëÿåòñëåäóþùàÿ çàäà÷à ïðîáëåìà âûâîäèìîñòè :äëÿ çàäàííîé ïîëóñèñòåìû Òóý K è ïàðû ñëîâ w 0è w 00 âûÿñíèòü, âûâîäèìî ëè ñëîâî w 00 èç w 0ñëîâà â K .ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÏðîáëåìà âûâîäèìîñòè äëÿïîëóñèñòåì Òóý àëãîðèòìè÷åñêè íåðàçðåøèìà.Äîêàçàòåëüñòâî ýòîé òåîðåìû îñíîâûâàåòñÿ íàñëåäóþùåì óòâåðæäåíèè.Óòâåðæäåíèå 6.7.
Äëÿ ëþáîé ìàøèíûÒüþðèíãà M ìîæíî ýôôåêòèâíî ïîñòðîèòüòàêóþ ïîëóñèñòåìó Òóý KM è òàêóþ ïàðó ñëîâw 0 , w 00 , ÷òî ñëîâî w 00 âûâîäèìî èç ñëîâà w 0 â Kâ òîì è òîëüêî òîì ñëó÷àå, êîãäà ÌÒ Mîñòàíàâëèâàåòñÿ íà ïóñòîé ëåíòå.Òåîðåìà 6.6.ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÏóñòü ÌÒ M èìååòìíîæåñòâî ñîñòîÿíèé Q = {q0, q1, . . . , qm } èëåíòî÷íûé àëôàâèò {0, 1} . Ïîëóñèñòåìà Òóý KMâêëþ÷àåò ñëåäóþùèå ïàðû ñëîâ â àëôàâèòå{0, 1, #, q0 , q1 , . .
. , qm } :äëÿ êàæäîé êîìàíäû hq, a : q0, b, Li òðè ïàðû(0qa, q 0 0b) , (1qa, q 0 1b) è (#qa, #q 0 0b) ;äëÿ êàæäîé êîìàíäû hq, a : q0, b, Ri òðè ïàðû(qa0, bq 0 0) , (qa1, bq 0 1) è (qa#, bq 0 0#) ;÷åòûðå ïàðû (q00, q0) , (q01, q0) , (0q0, q0) è(1q0 , q0 ) . êà÷åñòâå w 0, w 00 âîçüìåì ñëîâà #q10# è #q0# .Äîêàçàòåëüñòâî.IIIÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÊàê âèäíî èç îïðåäåëåíèÿ ïîëóñèñòåìû KM , äëÿêàæäîé íåçàêëþ÷èòåëüíîé êîíôèãóðàöèè α MTM èç ñëîâà #α# íåïîñðåäñòâåííî âûâîäèìîñëîâî w òîãäà è òîëüêî òîãäà, êîãäà MT Mïðåîáðàçóåò çà îäèí òàêò ðàáîòû êîíôèãóðàöèþ αâ êîíôèãóðàöèþ β è ïðè ýòîì w = #β# .Ïîýòîìó â ïîëóñèñòåìå Òóý KM èç ñëîâàw 0 = #q1 0# âûâîäèìî ñëîâî, ñîäåðæàùååñèìâîë q0 òîãäà è òîëüêî òîãäà, êîãäà MT Mèìååò óñïåøíîå âû÷èñëåíèå èç íà÷àëüíîéêîíôèãóðàöèè α0 = q10 .ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÍåòðóäíî âèäåòü òàêæå, ÷òî äëÿ êàæäîéçàêëþ÷èòåëüíîé êîíôèãóðàöèè β = uq0v èç ñëîâà#uq0 v # â ïîëóñèñòåìå Òóý KM âûâîäèìîw 00 = #q0 # .Òàêèì îáðàçîì, ïîëóñèñòåìå Òóý KM èç ñëîâàw 0 = #q1 0# âûâîäèìî ñëîâî w 00 = #q0 # òîãäàè òîëüêî òîãäà, êîãäà ÌÒ MT M îñòàíàâëèâàåòñÿíà ïóñòîé ëåíòå.QEDÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÎïðåäåëåíèå íåïîñðåäñòâåííîé âûâîäèìîñòè ñëîâìîæíî óñèëèòü: ñëîâî wb íåïîñðåäñòâåííîâûâîäèìî èç ñëîâà w â ñèñòåìå K (îáîçíà÷àåòñÿKb ), åñëè ñóùåñòâóåò òàêîå i, 1 ≤ i ≤ k, ,w =⇒ wäëÿ êîòîðîãî ëèáî w = w 0ui w 00 è wb = w 0vi w 00 ,ëèáî w = w 0vi w 00 è wb = w 0ui w 00 .Òàêèì îáðàçîì, ïàðû (ui , vi ) ýòî òîæäåñòâàKb ýòî öåïî÷êàui = vi , à âûâîä w =⇒∗ wòîæäåñòâåííûõ ïðåîáðàçîâàíèé ñëîâ.Ñèñòåìà óïîðÿäî÷åííûõ ïàð ñëîâ K ñ ââåäåííûìKîòíîøåíèåì íåïîñðåäñòâåííîé âûâîäèìîñòè =⇒íàçûâàåòñÿ ñèñòåìîé Òóý .ÀÑÑÎÖÈÀÒÈÂÍÛÅ ÈÑ×ÈÑËÅÍÈßÄîêàçàòü, ÷òî ñóùåñòâóåò òàêàÿïîëóñèñòåìà Òóý K , äëÿ êîòîðîé àëãîðèòìè÷åñêèíåðàçðåøèìà ñëåäóþùàÿ çàäà÷à: äëÿ çàäàííîéïàðû ñëîâ w 0 è w 00 âûÿñíèòü, âûâîäèìî ëè ñëîâîw 00 èç w 0 ñëîâà â K . 1967 ã.
Þ.Â. Ìàòèÿñåâè÷ ïîñòðîèë òàêóþñèñòåìó, ñîäåðæàùóþ âñåãî ëèøü òðè ïàðû ñëîâ.Çàäà÷à 4. [Òðóäíàÿ] Äîêàçàòü, ÷òîàëãîðèòìè÷åñêè íåðàçðåøèìà ñëåäóþùàÿ çàäà÷à:äëÿ çàäàííîé ñèñòåìû Òóý K è ïàðû ñëîâ w 0 èw 00 âûÿñíèòü, âûâîäèìî ëè ñëîâî w 00 èç w 0 ñëîâàâ K.Çàäà÷à 3.ÀËÃÎÐÈÒÌÈ×ÅÑÊÈ ÍÅÐÀÇÐÅØÈÌÛÅÇÀÄÀ×ÈÑóùåñòâóþò è äðóãèå àëãîðèòìè÷åñêèíåðàçðåøèìûå ìàòåìàòè÷åñêèå çàäà÷è.Ðàññìîòðèì íàèáîëåå èçâåñòíûå èç íèõ.ÄÈÎÔÀÍÒÎÂÛ ÓÐÀÂÍÅÍÈßÓðàâíåíèå P(x1, x2, .
. . , xn ) = 0 , ãäåP(x1 , x2 , . . . , xn ) ìíîãî÷ëåí ñ öåëî÷èñëåííûìèêîýôôèöèåíòàìè, íàçûâàþò äèîôàíòîâûìóðàâíåíèåì . Íàçâàíû â ÷åñòü äðåâíåãðå÷åñêîãîìàòåìàòèêà Äèîôàíòà (¾îòåö àëãåáðû¿).Ïðèìåðîì äèîôàíòîâà óðàâíåíèÿ ÿâëÿåòñÿ ëþáîåèç óðàâíåíèé âèäà x n + y n = z n .ÄÈÎÔÀÍÒÎÂÛ ÓÐÀÂÍÅÍÈßÌíîãèå ñòîëåòèÿ ìàòåìàòèêè èñêàëè ñïîñîáïîëó÷åíèÿ öåëî÷èñëåííûõ ðåøåíèé äèîôàíòîâûõóðàâíåíèé. Íàïðèìåð, äëÿ äèîôàíòîâûõóðàâíåíèé ñ îäíîé ïåðåìåííîé òàêîé ñïîñîáïðåäîñòàâëÿåò òåîðåìà Áåçó. 1900 ã.
Äàâèä Ãèëüáåðò ñôîðìóëèðîâàë çàäà÷ó(10-ÿ ïðîáëåìà Ãèëüáåðòà)Ïóñòü çàäàíî äèîôàíòîâî óðàâíåíèå ñ ïðîèçâîëüíûìè íåèçâåñòíûìè è öåëûìè ðàöèîíàëüíûìè÷èñëîâûìè êîýôôèöèåíòàìè. Óêàçàòü ñïîñîá, ïðèïîìîùè êîòîðîãî âîçìîæíî ïîñëå êîíå÷íîãî÷èñëà îïåðàöèé óñòàíîâèòü, ðàçðåøèìî ëè ýòîóðàâíåíèå â öåëûõ ðàöèîíàëüíûõ ÷èñëàõ.ÄÈÎÔÀÍÒÎÂÛ ÓÐÀÂÍÅÍÈß 1953-1970 ãã. Ì. Äåâèñ, Þ. Ðîáèíñîí, Õ. Ïàòíåìè Þ.Â. Ìàòèÿñåâè÷ äîêàçàëè àëãîðèòìè÷åñêóþíåðàçðåøèìîñòü ýòîé ïðîáëåìû.
Îêîí÷àòåëüíàÿôîðìóëèðîâêà ïîëó÷åííîãî ðåçóëüòàòà òàêîâà.Òåîðåìà. Äëÿ ëþáîãî ðåêóðñèâíî ïåðå÷èñëèìîãîìíîæåñòâà öåëûõ ÷èñåë R ñóùåñòâóåò òàêîéìíîãî÷ëåí P(x1, . . . , xn , z) , ÷òî äëÿ ëþáîãî öåëîãî÷èñëà k ñïðàâåäëèâî ñëåäóþùåå ñîîòíîøåíèåk ∈R⇔äèîôàíòîâî óðàâíåíèå P(x1, . . . , xn , k) = 0 èìååòöåëî÷èñëåííîå ðåøåíèå.ÌÀÒÐÈ×ÍÀß ÀËÃÅÁÐÀÏðåäïîëîæèì, ÷òî èìååòñÿ íåêîòîðîå êîíå÷íîåìíîæåñòâî öåëî÷èñëåííûõ ìàòðèö M1, M2, . . . , Mkðàçìåðà n × n .Çàäàäèìñÿ âîïðîñîì (ïðîáëåìà åäèíè÷íîéìàòðèöû ): ìîæíî ëè, ïåðåìíîæàÿ ìàòðèöû ýòîãîìíîæåñòâà, ïîëó÷èòü åäèíè÷íóþ ìàòðèöó I , ò.å.ñôîðìèðîâàòü òàêóþ êîíå÷íóþïîñëåäîâàòåëüíîñòü èíäåêñîâ i1, i2, . . .
, iN , ÷òîáûâûïîëíÿëîñü ðàâåíñòâîMi1 × Mi2 × · · · × MiN = I ?ÌÀÒÐÈ×ÍÀß ÀËÃÅÁÐÀÏðîáëåìà åäèíè÷íîé ìàòðèöûàëãîðèòìè÷åñêè íåðàçðåøèìà äëÿ öåëî÷èñëåííûõìàòðèö ðàçìåðà n × n ïðè ëþáûõ n, n ≥ 4 , èðàçðåøèìà äëÿ n = 2 .Îòêðûòàÿ ïðîáëåìà. Ñóùåñòâóåò ëè àëãîðèòìðåøåíèÿ ïðîáëåìà åäèíè÷íîé ìàòðèöû äëÿìàòðèö ðàçìåðà 3 × 3 ?Òåîðåìà.ÏÐÎÁËÅÌÀ ÌÎÇÀÈÊÈÌîçàèêà (äîìèíî): ýòî êîíå÷íîå ìíîæåñòâî(îáðàçöîâ) êâàäðàòíûõ ïëèòîê, êðàÿ êîòîðûõìîãóò èìåòü ðàçíîîáðàçíóþ ðàñêðàñêó.Äâå ïëèòêè, ïðèëåãàþùèå äðóã ê äðóãó êðàÿìè,ñ÷èòàþòñÿ ñîâìåñòíûìè , åñëè èõ ñìåæíûå êðàÿîäèíàêîâî îêðàøåíû.Ïðè ýòîì âðàùàòü ïëèòêè çàïðåùàåòñÿ.ÏÐÎÁËÅÌÀ ÌÎÇÀÈÊÈÇàäàäèìñÿ âîïðîñîì (ïðîáëåìà ìîçàèêè ): ìîæíîëè ïîêðûòü ïëèòêàìè çàäàííîé ìîçàèêè âñþáåñêîíå÷íóþ ïëîñêîñòü òàê, ÷òîáû ëþáàÿ ïàðàñîñåäíèõ ïëèòîê áûëà ñîâìåñòíîé?ÏÐÎÁËÅÌÀ ÌÎÇÀÈÊÈÏðîáëåìà ìîçàèêè àëãîðèòìè÷åñêèíåðàçðåøèìà.Îòêðûòàÿ ïðîáëåìà.
Ñóùåñòâóåò ëè àëãîðèòìðåøåíèÿ ïðîáëåìà åäèíè÷íîé ìàòðèöû äëÿìàòðèö ðàçìåðà 3 × 3 ?Òåîðåìà.ÌÀØÈÍÛ ÌÈÍÑÊÎÃÎÍàñêîëüêî ïðîñòîé ìîæåò áûòü ìîäåëüâû÷èñëåíèé, äàþùàÿ âîçìîæíîñòü ðåàëèçîâàòüëþáîé àëãîðèòì (âû÷èñëèòü ëþáóþ ðåêóðñèâíóþôóíêöèþ)?Êàæåòñÿ, ÷òî òðóäíî ïðåäñòàâèòü ñåáåóíèâåðñàëüíîå âû÷èñëèòåëüíîå óñòðîéñòâî, áîëååïðîñòîå, ÷åì ìàøèíû Òüþðèíãà.Îäíàêî åñòü è áîëåå ïðîñòûå óíèâåðñàëüíûåìîäåëè âû÷èñëåíèé!ÌÀØÈÍÛ ÌÈÍÑÊÎÃÎÌàøèíà Ìèíñêîãî ýòî ïðîãðàììà, ñîñòîÿùàÿèç ïîìå÷åííûõ îïåðàòîðîâ òîëüêî äâóõ âèäîâ:L0 : X++; goto L00 ;L0 : if X>0 then X−− ; goto L00 else goto L000 .Ïåðåìåííûå ïðèíèìàþò òîëüêî öåëûåíåîòðèöàòåëüíûå çíà÷åíèÿ.Ìàøèíó Ìèíñêîãî ìîæíî ïðåäñòàâèòü â âèäåàâòîìàòà, ñíàáæåííîãî íàáîðîì ñ÷åò÷èêîâ.
Íàêàæäîì òàêòå ðàáîòû ïîêàçàíèÿ êàêîãî-íèáóäüñ÷åò÷èêà ëèáî óâåëè÷èâàþòñÿ, ëèáî (ïîñëåïðîâåðêè åãî íåïóñòîòû) óìåíüøàþòñÿ.IIÄëÿ ëþáîé ÷àñòè÷íî-ðåêóðñèâíîéôóíêöèè ñóùåñòâóåò ìàøèíà Ìèíñêîãî ñ äâóìÿñ÷åò÷èêàìè, âû÷èñëÿþùàÿ ýòó ôóíêöèþ.Ñëåäñòâèå. Ïðîáëåìà îñòàíîâà äëÿ ìàøèíûÌèíñêîãî ñ äâóìÿ ñ÷åò÷èêàìè àëãîðèòìè÷åñêèíåðàçðåøèìà.Çàäà÷à 5. Äîêàæèòå âû÷èñëèòåëüíóþóíèâåðñàëüíîñòü ìàøèí Ìèíñêîãî ñ òðåìÿñ÷åò÷èêàìè.Çàäà÷à 6. Ïîñòðîéòå àëãîðèòì ðåøåíèÿïðîáëåìû îñòàíîâà äëÿ ìàøèí Ìèíñêîãî ñ îäíèìñ÷åò÷èêîì.Òåîðåìà.ÊÎÍÅÖ ËÅÊÖÈÈ 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
