4. The Halting Problem is Undecidable (a) Use first order logic to state that problem P is computable. Might the TM mentioned in this sentence fail to halt on some input? (b) Suppose I give you as an oracle a Universal Turing Machine. With this extra help, does this change with whether you can solve the Halting problem? (c) Suppose you think it undignified to feed a TM M a description "M" of itself. Instead, of mak- ing M's nernesis be 111-"M", lets instead define IM = F(M) where F(M) is the descrip- tion of what the TM M fears the most. For example, F(MSherlock Homes)-Moriarty" and F(Ms super Man) - "Kryptonite" i. Suppose F(M) is distinct for each TM M, ie. YM. M. MM, F(M)F(M"). Using this new nemesis input, give the proof that there is a problem Phard that is uncomputable. This is done by giving the first order logic statement and then playing the game (Six quick sentences, i.e. I removed all the chat from the posted proof.) If you have memorized the proof in the slides and you put it here unchanged you will get 60% ii. (Bonus Question so no marks for a blank): Suppose F(M) is not distinct for each TM M. ie.M. M', MM, and F(M) F(M"). Suppose we want Phard to be a language, i.e. its output is in {Yes, No]. What does wrong in your previous proof! 4. The Halting Problem is Undecidable (a) Use first order logic to state that problem P is computable. Might the TM mentioned in this sentence fail to halt on some input? (b) Suppose I give you as an oracle a Universal Turing Machine. With this extra help, does this change with whether you can solve the Halting problem? (c) Suppose you think it undignified to feed a TM M a description "M" of itself. Instead, of mak- ing M's nernesis be 111-"M", lets instead define IM = F(M) where F(M) is the descrip- tion of what the TM M fears the most. For example, F(MSherlock Homes)-Moriarty" and F(Ms super Man) - "Kryptonite" i. Suppose F(M) is distinct for each TM M, ie. YM. M. MM, F(M)F(M"). Using this new nemesis input, give the proof that there is a problem Phard that is uncomputable. This is done by giving the first order logic statement and then playing the game (Six quick sentences, i.e. I removed all the chat from the posted proof.) If you have memorized the proof in the slides and you put it here unchanged you will get 60% ii. (Bonus Question so no marks for a blank): Suppose F(M) is not distinct for each TM M. ie.M. M', MM, and F(M) F(M"). Suppose we want Phard to be a language, i.e. its output is in {Yes, No]. What does wrong in your previous proof