Confusion about proof of undecidability of REGULAR TM in Sipser's book [duplicate]

Question

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows :

REGULAR_TM = { <M> | M is a Turing machine and L(M) is regular language }. Well, Sipser says that this is an undecidable language since we cannot have a decider to decide this language. Because if we could, we could create a TM that decides ATM which we know previously that is undecidable. so this could cause a contradiction. Here is the proof from this book :

Proof. We let R be a TM that decides REGULAR_TM and construct TM S to decide ATM. Then S works in the following manner.

S = "On input <M, w>, where M is a TM and w is a string:

1. Construct the following TM M2.

   M2 = "On input x:

     1. If x has the form 0^n 1^n, accept.
   
     2. If x does not have this form, run M on input w and accept if M accepts w."
   

2. Run R on input <M2>.

3. If R accepts, accept; if R rejects, reject."

Now my question is, is this kind of constrcuting a TM S correct? the part that is really confusing me is the part that says "run M on input w and accept if M accepts w". this is the whole question for Atm. If we could answer that question why we need a machine M2 to feed it into the R and output the result of R. We just "run M on w".

Also for some languages that [we know] are decidable we can have the same argument and conclude that it is not decidable.

----- EDIT -----

Ok. let me explain my confusion a little bit different. consider language A_DFA :

A_DFA = { <B, w> | B is a DFA that accepts w }

We know it is decidable (Proof in the textbook). so we reduce ATM to A_DFA.

PROOF. let R be Turing machine that decides A_DFA. we construct TM S to decide ATM. then S works in the following manner :

S = "On input <M, w> where M is a TM and w is a string:

1. Construct the following DFA D:

   DFA D has only one state q0 which is also the start state. all arrows come back to q0 itself. if M accepts w add q0 to F. (F is the set of final states.)

2. Run R on <D, w>

3. accept if R accepts; reject if R rejects.

---

It is interesting that I kind of understood the problem of my own work when I was writing the proof of reduction of ATM to A_DFA. I write it so that if it is true others can learn if it is wrong others will correct it!

I think that because M2 in the first proof is a Turing machine we CAN say that if "M accepts w". (we somehow embedded the work of "if M accepts w" into M2 without actually running M on w). but in my own proof of ATM -> A_DFA the problem is that we cannot construct DFA D without actually running M on w. so we cannot construct D. That's the reason why the first proof is true and my proof is wrong.

Answer 1

A universal Turing machine accepts a machine $M$ and an input $x$, and simulates the run of $M$ on $x$.

• If $M$ halts on $x$, the universal Turing machine will also halt, and will output the state of $M$ at the end of computation.

• If $M$ doesn't halt on $x$, the universal Turing machine will also not halt.

This is what the machine $M_2$ does on step 2. It simulates $M$ on $w$, and may or may not halt. What a universal Turing machine cannot accomplish is solve the halting problem, that is, given $M$ and $x$, do some computation which always terminates, and answer whether $M$ halts on $x$ or not. Instead, it simulates $M$ on $x$, and halts iff $M$ halts on $x$.

We shouldn't be able to tell whether an arbitrary machine $M$ halts on an arbitrary $w$ or not. The reduction translates this question into the question whether $L(M_2)$ is regular. Since the former question is undecidable, so is the latter one.