1. Suppose that S is an infinite countable set, then prove that the power-set 25 of S is uncountable. (hint: use diagonalization) (5 pts) 2. Prove that the set of strings S={(a, b, c}* is countable.(hint: use diagonalization) (5 pts) 3. Prove that the halting problem is unsolvable (undecidable). (hint: use diagonalization) (5 pts) 4. State-entry problem: Given a turing machine, an input string and a state in that turing machine, tell whether the turing machine will enter to that state or not during the executing of the input string. Prove that the state-entry problem is unsolvable (undecidable). (hint: use reduction) (5 pts)