patternMinor
Understanding the reduction of REGULARTM from ATM
Viewed 0 times
understandingthereductionatmfromregulartm
Problem
REGULARTM is defined as below:
I am trying to understand the proof of REGULARTM being undecidable from Sipser's book "Introduction to the Theory of Computation". The book says:
The problem that I am facing is in the 2nd substep of the 1st step which says:
What if M does not halt on w? Then the decider S that we are building would not halt.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#74608, answer score: 2
Revisions (0)
No revisions yet.