МТ не меняет вход/решение Сеилов

Материал из DISCOPAL
Перейти к: навигация, поиск

Ответ: да.

докажем лемму: если МТ, двигаясь по бесконечной вправо (или влево) ленте, заполненной пустыми символами, не изменяла символы на ленте и сдвинулась по крайней мере на |Q|+1 ячеек вправо (влево), то эта машина никогда не останавливается и не изменяет ни одного символа на ленте. Это следует из того, что в состояниях МТ, когда машина указывала на различные ячейки из этих |Q| + 1, было (по принципу Дирихле) как минимум две одинаковые конфигурации (символ, на который указывает головка МТ и состояние МТ). Значит, МТ зациклится.

Решение исходной задачи: модернизируем универсальную МТ так, что она моделирует работу М в пределах зоны |x| + 2|Q| + 2 (ко входному слову слева и справа приписываются по |Q|+1 пустому символу), при этом на отдельной ленте составляет список последовательных конфигураций М. Как только изменяется какой-либо символ, МТ выдает ответ "нет" Если некоторая конфигурация повторилась, и символы не менялись: М зациклится, ответ "да". Если МТ остановилась, и символы не менялись: ответ "да". Если МТ вышла за границы зоны, и символы не менялись: ответ "да".

из конечности числа конфигураций становится ясно, что всегда реализуется один из вариантов.