REGULARTM is defined as below:

REGULARTM ={〈M〉| M is a TM and L(M)is a regular language}.

I am trying to understand the proof of REGULARTM being undecidable from Sipser's book "Introduction to the Theory of Computation". The book says:

We let R to be a TM that decides REGULARTM 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^n1^n,accept.
        2.If x does not have this form, run M on input w and accept if M.”
2.Run R on input〈M2〉.
3.If R accepts,accept; if R rejects,reject.”

The problem that I am facing is in the 2nd substep of the 1st step which says:

If x does not have this form, run M on input w and accept if M.

What if M does not halt on w? Then the decider S that we are building would not halt.


Let's look just at $M_2$ for the moment. If $M$ accepts $w$, then $M$ will accept strings of the form $0^n1^n$ in step (1) and everything else in step (2). In other words

If $M$ accepts $w$, then the language $L(M_2)=\Sigma^*$, which is of course regular.

Now if $M$ doesn't accept $w$, then $M_2$ will accept all and only strings of the form $0^n1^n$, so $L(M_2) = \{0^n1^n\mid n\ge 0\}$ and this language is certainly not regular.

The important thing here is that we don't have to run $M$ on $w$ to decide its behavior: the behavior is determined solely by whether $M$ accepts $w$ or not. Since $R$ was assumed to be a decider, it doesn't have to run $M$ to determine whether the language of $M_2$ is regular or not; because $R$ is a decider it is by definition assumed to be able to tell that.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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