https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9C%D0%A2_%D0%BD%D0%B5_%D0%BC%D0%B5%D0%BD%D1%8F%D0%B5%D1%82_%D0%B2%D1%85%D0%BE%D0%B4%2F%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A1%D0%B5%D0%B8%D0%BB%D0%BE%D0%B2 2026-04-20T07:18:08Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9C%D0%A2_%D0%BD%D0%B5_%D0%BC%D0%B5%D0%BD%D1%8F%D0%B5%D1%82_%D0%B2%D1%85%D0%BE%D0%B4/%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A1%D0%B5%D0%B8%D0%BB%D0%BE%D0%B2&diff=6115&oldid=prev 2017-05-13T13:24:28Z

<p>Новая страница: «Ответ: да. докажем лемму: если МТ, двигаясь по бесконечной вправо (или влево) ленте, запол…»</p> <p><b>Новая страница</b></p><div>Ответ: да.<br /> <br /> докажем лемму: если МТ, двигаясь по бесконечной вправо (или влево) ленте, заполненной пустыми символами, не изменяла символы на ленте и сдвинулась по крайней мере на |Q|+1 ячеек вправо (влево), то эта машина никогда не останавливается и не изменяет ни одного символа на ленте.<br /> Это следует из того, что в состояниях МТ, когда машина указывала на различные ячейки из этих |Q| + 1, было (по принципу Дирихле) как минимум две одинаковые конфигурации (символ, на который указывает головка МТ и состояние МТ). Значит, МТ зациклится.<br /> <br /> Решение исходной задачи: модернизируем универсальную МТ так, что она моделирует работу М в пределах зоны |x| + 2|Q| + 2 (ко входному слову слева и справа приписываются по |Q|+1 пустому символу), при этом на отдельной ленте составляет список последовательных конфигураций М. <br /> Как только изменяется какой-либо символ, МТ выдает ответ &quot;нет&quot;<br /> Если некоторая конфигурация повторилась, и символы не менялись: М зациклится, ответ &quot;да&quot;.<br /> Если МТ остановилась, и символы не менялись: ответ &quot;да&quot;.<br /> Если МТ вышла за границы зоны, и символы не менялись: ответ &quot;да&quot;.<br /> <br /> из конечности числа конфигураций становится ясно, что всегда реализуется один из вариантов.</div>

Темирлан