Формально об алгоритмах. Вычислительные модели/Задачи/ex-obfuscation-undecidable/Решение Дербышев

Материал из DISCOPAL
Перейти к: навигация, поиск

Дана любая МТ Т.

Введем новую машину Т', стирающую входное слово и начинающую потом работать как Т на пустом слове, но вместо остановки переходящее в состояние СТОП.

Нашей проблемой (входные данные: Т', СТОП) можно решить задачу останова Т на пустом слове, поэтому она не разрешима.


StasFomin (обсуждение) 14:25, 13 декабря 2016 (UTC): Задача уже была решена за неделю до вашего решения.