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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: добавление Категория:Теоретические задачи)
 
(не показано 11 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
состояние хотя бы для одного входного слова <tt>x</tt>?
 
состояние хотя бы для одного входного слова <tt>x</tt>?
  
−
[[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>
+

Текущая версия на 06:50, 4 мая 2023

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

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