Машина Тьюринга для обычных языков
Теорема 5.3 из книги TOC Сипсера о разрешимости Regular_TM = {M | M - машины Тьюринга (TM), а L(M) - обычные языки}. Для достижения противоречия предполагается, что TM R является решающим для Regular_TM, а затем R используется для решения проблемы принятия, как показано в ударе TM S:
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x:
(a) If x of the form 0^n1^n, accept.
(b) else, run M on w and if M accepts w, then accept."
2. Run R on (M2).
3. If R accepts, accept; if R rejects, reject."
У меня два вопроса. Первый x в M_2 исправлен? если нет, то откуда?
2-й вопрос. Почему мы заботимся о х в М2. Если R действительно является решающим, зачем нам проверять, находится ли x в 0^n1^n. Так работает ли ТМ S'ниже?
S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x: //ignore x
(a) run M on w and if M accepts w, then accept else reject."
2. Run R on (M2).
3. If R accepts, accept; if R rejects, reject."