4. (Reduction Mad-Libs) A language B is excited if every string in B takes the form ww for some w = {0,1}*. For example, {00, 1111, 1010} is excited, but {00, 10} is not excited. The language EXTM = {(M) |L(M) is excited} corresponds to the following computational problem: Given the encoding of a TM M, does M recognize an excited language? This exercise will walk you through a proof, by reduction, that EXTM is undecidable. Assume, for the sake of contradiction, that EXTM is decidable by a TM R. That is, there is a TM R that accepts (M) whenever L(M) is excited, and rejects (M) whenever L(M) is not excited. We will use R to construct a new TM S that decides the (undecidable) language ATM. Algorithm: S((M, w)) Input : Encoding of a basic TM M over input alphabet {0,1}, string w {0, 1}* 1. Construct the following TM N: N = "On input a string x {0,1}*: If x = 01, accept. Else, run M on input w. If it accepts, accept. Otherwise, reject." 2. Run R on input (N). If it accepts, (i) Otherwise, (ii) (a) Consider the machine N constructed inside algorithm S. If M accepts on input w, what is the language L(N)? Is L(N) excited in this case? (b) If M does not accept on input w, what is the language L(N)? Is L(N) excited in this case? (c) Fill in the blanks labeled (i) and (ii) with accept or reject decisions to guarantee the following conditions: If M accepts input w, then S accepts input (M, w), and if M does not accept input w, then S rejects input (M,w). Use parts (a) and (b) to explain why these conditions hold for your choices of how to fill in the blanks. 2 (Your job is done now, but you may want to keep reading to see how the proof concludes.) By part (c), the TM M exactly decides the language ATM. But this language is undecidable, which is a contradiction. Hence our assumption that EXTM was decidable is false, so we conclude that EXTM is an undecidable language. 4. (Reduction Mad-Libs) A language B is excited if every string in B takes the form ww for some w = {0,1}*. For example, {00, 1111, 1010} is excited, but {00, 10} is not excited. The language EXTM = {(M) |L(M) is excited} corresponds to the following computational problem: Given the encoding of a TM M, does M recognize an excited language? This exercise will walk you through a proof, by reduction, that EXTM is undecidable. Assume, for the sake of contradiction, that EXTM is decidable by a TM R. That is, there is a TM R that accepts (M) whenever L(M) is excited, and rejects (M) whenever L(M) is not excited. We will use R to construct a new TM S that decides the (undecidable) language ATM. Algorithm: S((M, w)) Input : Encoding of a basic TM M over input alphabet {0,1}, string w {0, 1}* 1. Construct the following TM N: N = "On input a string x {0,1}*: If x = 01, accept. Else, run M on input w. If it accepts, accept. Otherwise, reject." 2. Run R on input (N). If it accepts, (i) Otherwise, (ii) (a) Consider the machine N constructed inside algorithm S. If M accepts on input w, what is the language L(N)? Is L(N) excited in this case? (b) If M does not accept on input w, what is the language L(N)? Is L(N) excited in this case? (c) Fill in the blanks labeled (i) and (ii) with accept or reject decisions to guarantee the following conditions: If M accepts input w, then S accepts input (M, w), and if M does not accept input w, then S rejects input (M,w). Use parts (a) and (b) to explain why these conditions hold for your choices of how to fill in the blanks. 2 (Your job is done now, but you may want to keep reading to see how the proof concludes.) By part (c), the TM M exactly decides the language ATM. But this language is undecidable, which is a contradiction. Hence our assumption that EXTM was decidable is false, so we conclude that EXTM is an undecidable language