Задача по Машинам Тьюринга.

[DdK]

Существует ли aлгоритм, который по описанию машины Тьюринга М проверяет истинность условия "нaйдется тaкoе
слово х, что М останавливается на этом слове x"?

Собственно не понятно то, как свести её к проблеме остановки МТ,который выглядит так:

Цитата:

Неразрешимо свойство «Машина Тьюринга останавливается, будучи запущенной на данных X»

[lofar]

Можно взять машину $T_X$, которая по любому входу порождает выход $X$. Для любой машины $M$ вопрос остановки на входе $X$ эквивалентен вопросу останови композиции машин $M\circ T_X$ на некотором входе.

[Профессор Снэйп]

Э-э-э... Тут надо, наоборот, проблему остановки сводить к нашей проблеме. Мы ведь хотим неразрешимость показать, не так ли?

Проблема остановки в чём заключается? Для каждой пары $\langle M, x \rangle$ требуется определить, остановится ли машина $M$ на входе $x$.

Для каждой пары $\langle M, x \rangle$ строим машину $N(M,x)$, которая, получив на вход произвольное $y$, запускает машину $M$ со входом $x$, напрочь игнорируя это самое $y$. Функция $\langle M,x \rangle \mapsto N(M,x)$ осуществляет нужное сведение.

-- Пт дек 31, 2010 04:42:07 --

Собственно, $N(M,x) = M \circ T_x$ в терминологии lofar.