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.


1 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.

  • $\begingroup$ 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? $\endgroup$ Jan 14, 2019 at 14:49
  • $\begingroup$ You won’t be able to construct $D$. Try it. $\endgroup$ Jan 14, 2019 at 14:51
  • $\begingroup$ 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. $\endgroup$ Jan 14, 2019 at 14:56
  • $\begingroup$ Yes, we cannot construct such D. $\endgroup$ Jan 14, 2019 at 18:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.