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

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.

• – John L. Jan 14 '19 at 16:57

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.

• I still have some confusion about this. Suppose A_DFA = {<B, w> | B is a DFA that accepts input string w }. so we know this language is decidable. therefore there is a decider for that R. I can say in the proof that Create a DFA D : 1. D accepts every thing if M accepts w. 2. D accepts nothing if M does not accepts w. then give <D, w> to R. output the result. is this a conflict of the fact that A_DFA is decidable? – Mohammad Mahdi Jan 14 '19 at 14:49
• You won’t be able to construct $D$. Try it. – Yuval Filmus Jan 14 '19 at 14:51
• A DFA that accepts everything is simple. just a state q0 which is also a final state and for each input character goes to itself. A DFA that accepts nothing is also a single state q0 and with every character goes to itself but is not a final state. – Mohammad Mahdi Jan 14 '19 at 14:56
• Yes, we cannot construct such D. – Mohammad Mahdi Jan 14 '19 at 18:10