title: Turing Machine for regular languages
body: <p>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:</p>
  
  <p><code>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."</code></p>
  
  <p>I have two questions. The first is x in M_2 fixed? if not, where does it come from ? </p>
  
  <p>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? </p>
  
  <p><code>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."</code> </p>