2. Prove that ALLTM is undecidable by modifying the proof on the pre- ious page and filling in the blanks ALLTM-{ M | M is a TM which accepts every input string} Proof: For anyM. w let M be the TM which takes as input string r: (a) Iw then 11 (b) If x-w then Mi Now we construct TM V to decide ATM. Let R be a hypothetical TM which decides ALLTM-V has input M, w and does the following: (a) Uses to output . (b) Runs R on to output . (b) Runs R on