Просмотр исходного текста страницы Формально об алгоритмах. Вычислительные модели/Задачи/ex-obfuscation-undecidable

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


<!--Вообще-то, решения уже есть-->

[[Категория:Нерешенные задачи]]