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 nemesis be IM-"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(MSuper Man)-"Kryptonite". i. Suppose F(M) is distinct for each TM M, ie. VM, M', MM, F(M)F(M'). Using this new nemesis input, give the proof that there is a problem Phord 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, i.e.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 nemesis be IM-"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(MSuper Man)-"Kryptonite". i. Suppose F(M) is distinct for each TM M, ie. VM, M', MM, F(M)F(M'). Using this new nemesis input, give the proof that there is a problem Phord 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, i.e.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