Theorem 5.3 from Sipser's TOC book is about decidability of Regular_TM = {M | M is a Turing Machines (TMs) and L(M) is regular languages}. For the sake of reaching a contradiction, TM R is assumed to be a decider for Regular_TM and then R is used to decide Acceptance problem as shown in the blow 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."
I have two questions. The first is x in M_2 fixed? if not, where does it come from ?
The 2nd question. Why do we care about x in M2. If R is truly a decider, why do we care about check if x is in 0^n1^n. So does a TM S' below works?
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."