This post has been de-listed
It is no longer included in search results and normal feeds (front page, hot posts, subreddit posts, etc). It remains visible only via the author's post history.
The following content is quoted from Micheal Sipser's introduction to theory of computation. The bold text is where I am facing problem.
Theorem : ETM is undecidable; ETM ={⟨M⟩|M is a TM and L(M)=∅}.
PROOF IDEA: We follow the pattern adopted in Theorem 5.1. We assume that ETM is decidable and then show that ATM is decidable—a contradiction. Let R be a TM that decides ETM. We use R to construct TM S that decides ATM. How will S work when it receives input ⟨M, w⟩?
One idea is for S to run R on input ⟨M ⟩ and see whether it accepts. If it does, we know that L(M) is empty and therefore that M does not accept w. But if R rejects ⟨M ⟩, all we know is that L(M ) is not empty and therefore that M accepts some string—but we still do not know whether M accepts the particular string w. So we need to use a different idea.
Instead of running R on ⟨M ⟩, we run R on a modification of ⟨M ⟩. We modify⟨M⟩ to guarantee that M rejects all strings except w, but on input w it works as usual. Then we use R to determine whether the modified machine recognizes the empty language. The only string the machine can now accept is w, so its language will be nonempty iff it accepts w. If R accepts when it is fed a description of the modified machine, we know that the modified machine doesn’t accept anything and that M doesn’t accept w.
- So first question is if R is fed the description of modified machine should not it accept w because we modified it to accept w but it says it does not accept anything and it does not accept w. and it is not mentioned what is done empty string from the description I can only understand that the modified machine accepts only w and not the empty string. I need clarification of this.
PROOF
Let’s write the modified machine described in the proof idea using our standard notation. We call it M1.
M1 = “On input x:
- If x ̸= w, reject.
- If x=w, run M on input w and accept if M does.”
This machine has the string w as part of its description. It conducts the test of whether x = w in the obvious way, by scanning the input and comparing it character by character with w to determine whether they are the same.
Putting all this together, we assume that TM R decides ETM and construct TMS that decides ATM as follows.
S = “On input ⟨M,w⟩, an encoding of a TM M and a string w:
- Use the description of M and w to construct the TM M1 just
described. - Run R on input ⟨M1 ⟩.
- If R accepts, reject ; if R rejects, accept .
Note that S must actually be able to compute a description of M1 from a description of M and w. It is able to do so because it only needs to add extra states to M that perform the x = w test.
If R were a decider for ETM, S would be a decider for ATM. A decider for ATM cannot exist, so we know that ETM must be undecidable.
- Now the second question is from point 3 in the description S. But lets move to 2nd point first we are running R(decider for ETM) on M1 which means it will reject if x /= w and accept otherwise. Now to point 3 if R accepts we reject in S(decider for ATM) because it first is performing a check on x=w it passes that but we know ATM is undecidable so it must reject same for when it accepts.
Please let me know if there are missing points in my understanding of it and correct where I am wrong being a theory person I would like how you tackle this problem.
Post Details
- Posted
- 5 years ago
- Reddit URL
- View post on reddit.com
- External URL
- reddit.com/r/compsci/com...