Below is a proof (from the text and lecture) that ETM is undecidable. = { 1-M is a TM and L(M)=0) Proof: For any let Mi be the TM which takes as input string r Ifw then Mi rejects Ifw then Mh runs like M on input w and accepts if M does. Now we construct TM V to decide ATM. Let R be a hypothetical TM which decides ETM. V has input and does the following Usesto output Runs Ron If R accepts, it rejects; if R rejects, it accepts. If R decided the emptiness of L(Mi). then V decides ATM. Therefore R can't exist and ETM is undecidable (a) If M accepts w what is the language of M1? (b) Given input , does V ever simulate M running on w? ircle one a) Yes b) No c) Can't tell Explain your answer (c) What happens if M doesn't halt on w? (circle all correct answers) a) Mi doesn't halt on some input b) R doesn't halt on some input c) V doesn't halt on some input d) Mi rejects