1. Below is a proof (from the text and lecture) that ErM is undecidable. ETM { M | M is a TM and L(M) = Proof: For any let M1 be the TM which takes as input string x: . If x Ifx-w then M1 runs like M on input w and accepts if M does. w then Mi rejects. Now we construct TM V to decide ATM. Let R be a hypothetical TM which decides ETM-V has input M, w and does the following: . Uses If R accepts, it rejects; if R rejects, it accepts If R decided the emptiness of L(Mi), then V decides ATM. Therefore A can't exist and HTM 1s undecidable. (a) If M accepts w what is the language of M1? (b) Given input M, w , does V ever simulate M running on w? circle 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) 1. Below is a proof (from the text and lecture) that ErM is undecidable. ETM { M | M is a TM and L(M) = Proof: For any let M1 be the TM which takes as input string x: . If x Ifx-w then M1 runs like M on input w and accepts if M does. w then Mi rejects. Now we construct TM V to decide ATM. Let R be a hypothetical TM which decides ETM-V has input M, w and does the following: . Uses If R accepts, it rejects; if R rejects, it accepts If R decided the emptiness of L(Mi), then V decides ATM. Therefore A can't exist and HTM 1s undecidable. (a) If M accepts w what is the language of M1? (b) Given input M, w , does V ever simulate M running on w? circle 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)