5. (Unary acceptance) A Turing machine M accepts a unary string if there exists a string x E {1}* such that M accepts on input x. Consider the problem of determining whether (the encoding of) a TM M accepts a unary string. (a) Formulate this problem as a language U A. Caution: The only input to this computational problem is (M) for a TM M. (b) Consider the following first attempt at designing a TM N recognizing the language U A. Algorithm: N((M)) Input : Encoding of a basic TM M over input alphabet {0, 1} 1. Let xn = 1. For each n= = 0, 1, 2, 3, ...: 2. Run M on input In. If it accepts, accept. Otherwise, continue. Explain why N fails to recognize U A. (c) Design and analyze a Turing machine that does recognize the language U A. Hint: Solved exercise 4.5 in Sipser illustrates the dovetailing" trick that will be useful here. (d) Prove that the language UA is undecidable. Hint: Give a reduction from the undecidable language Atm. That is, you should assume for the sake of contradiction that U A is decidable. Then under this assumption, construct a TM deciding ATM, prove that this decider is correct, and as a result conclude that your assumption that U A is decidable must have been false. 5. (Unary acceptance) A Turing machine M accepts a unary string if there exists a string x E {1}* such that M accepts on input x. Consider the problem of determining whether (the encoding of) a TM M accepts a unary string. (a) Formulate this problem as a language U A. Caution: The only input to this computational problem is (M) for a TM M. (b) Consider the following first attempt at designing a TM N recognizing the language U A. Algorithm: N((M)) Input : Encoding of a basic TM M over input alphabet {0, 1} 1. Let xn = 1. For each n= = 0, 1, 2, 3, ...: 2. Run M on input In. If it accepts, accept. Otherwise, continue. Explain why N fails to recognize U A. (c) Design and analyze a Turing machine that does recognize the language U A. Hint: Solved exercise 4.5 in Sipser illustrates the dovetailing" trick that will be useful here. (d) Prove that the language UA is undecidable. Hint: Give a reduction from the undecidable language Atm. That is, you should assume for the sake of contradiction that U A is decidable. Then under this assumption, construct a TM deciding ATM, prove that this decider is correct, and as a result conclude that your assumption that U A is decidable must have been false