Формально об алгоритмах. Вычислительные модели/Задачи/ex-obfuscation-undecidable — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
состояние хотя бы для одного входного слова <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>

Версия 15:53, 18 декабря 2014

Докажите, что неразрешима «Проблема недостижимого кода» - нет алгоритма, который для заданной машины Тьюринга T и ее состояния выясняет: попадет ли машина в это состояние хотя бы для одного входного слова x?

Источник — «https://discopal.ispras.ru/index.php?title=Формально_об_алгоритмах._Вычислительные_модели/Задачи/ex-obfuscation-undecidable&oldid=3251»