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

Материал из DISCOPAL
< МТ не меняет вход
Версия от 16:24, 13 мая 2017; Темирлан (обсуждение | вклад) (Новая страница: «Ответ: да. докажем лемму: если МТ, двигаясь по бесконечной вправо (или влево) ленте, запол…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Ответ: да.

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

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

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