Изменения
Нет описания правки
Имея этот набор правил можем составить упомянутый выше критерий: программа корректно завершиться на данном на ленте входном слове <tex> u </tex>, если в построенной полусистеме <tex> \langle q_1u \rangle \vDash ^* q_n </tex>. Таким образом из разрешимости этой задачи следовала бы разрешимость задачи останова. Соответсвенно задача о выводе в полусистеме Туэ алгоритмически неразрешима.
}}
== См. также ==
* [[m-сводимость]]
* [[Примеры неразрешимых задач: проблема соответствий Поста | Проблема соответствий Поста]]
* [[Примеры неразрешимых задач: задача о замощении | Задача о замощении]]
* [[Неразрешимость исчисления предикатов первого порядка]]
==Примечания==
