Я понимаю, что HP - неразрешимая проблема из-за аргумента диагонализации.
В моей книге (kozen) первый пример сокращения проблемы остановки - это машина, которая может решить, является ли пустой символстрока ε принята.
из моей книги:
Предположим, мы могли бы решить, e.данная машина a.ccepts E. Затем мы можем решить проблему остановки следующим образом.Скажем, нам дана машина Тьюринга M и строка x, и мы хотим определить, останавливается ли M на X. Построить из M и x новую машину M ', которая выполняет следующие действия при вводе y:
- (i) стирает свой вход y;
- (ii) записывает x на свою ленту (M 'имеет x встроенный в своем конечном элементе управления);
- (iii) запускает M на входе x (M 'также имеет описание M, встроенного в его конечное управление);
- (iv) принимает, если M останавливается на X.
Здесь уже много вопросовпришло мне в голову.M 'не основан (насколько это говорит текст) на фактической машине, которая решает, принято или нет ε.
Почему мы стираем ввод y?Является ли x в M 'произвольным?И самое большое замешательство возникает из-за моего вопроса: почему я не могу доказать любую проблему решения таким образом: сделать машину M ', которая стирает свой ввод, записывает x на ленту, запускает M на входе x и принимает, если M останавливается на x?
Я пытаюсь понять связь между решающим фактором для машины, принимающей ε, и ТМ, данной в книге, но, похоже, я не могу этого понять, как и мои сокурсники.