состояние хотя бы для одного входного слова <tt>x</tt>?
состояние хотя бы для одного входного слова <tt>x</tt>?
−
[[Category:На проверку]]
+
[[Category:Решенные задачи]]
<!--Вообще-то, решения уже есть-->
<!--Вообще-то, решения уже есть-->
−
−
<latex>
−
Решение (Бунаков Василий, 974гр.)
−
\smallskip
−
−
Докажем от противного. Допустим, проблема разрешима, т.е. существует машина Тьюринга M, которая для заданной машины Тьюринга T и ее состояния q, выдает ответ <<Да>>, если состояние достижимо и <<Нет>> в противном случае.
−
Покажем, что тогда разрешима и проблема проверки $L(T)=\emptyset$: по данной машине Тьюринга Т узнать, определяет ли она пустой язык. Действительно, пусть дана МТ T с финальным состоянием $q_{final}$. Подадим на вход машине M $\langle T,q_{final} \rangle$: если ответ <<Да>>, то $q_{final}$ --- достижимое состояние и $L(T)\neq \emptyset$,
−
иначе --- $L(T)= \emptyset$.
−
\smallskip
−
−
Докажем от противного, что проблема $L(T)=\emptyset$ неразрешима.
−
Пусть M - машина Тьюринга, которая для заданной МТ Т выдает ответ <<Да>>, если $L(T)=\emptyset$ и <<Нет>> в противном случае. Тогда разрешима и проблема остановки (для данной МТ Т и слова x определить, останавливается ли T на x): построим по машине Т и входному слову $x$ машину $\hat T$
−
которая на любом входе симулирует работу $T$ на $x$. Тогда $L(\hat T)=\emptyset$ тогда и только тогда, когда Т не останавливается на x.
−
Противоречие.
−
−
−
<\latex>
Версия 01:11, 26 декабря 2014
Докажите, что неразрешима «Проблема недостижимого кода»
- нет алгоритма, который для заданной машины Тьюринга T
и ее состояния выясняет: попадет ли машина в это
состояние хотя бы для одного входного слова x?