4. The Halting Problem is Undecidable

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 docs 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 TNI M fears the most. For example. F(MSherlock Homes)-Moriarty" and Msuper Man) - "Kryptonite" i. Suppose FM) is distinct for each TNI M. i.e. VM. M. M?M, 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, i.e.?M. M. M?M, and F(M)-F(M") Suppose we want Phard to be a language, i.c. its output is in {Yes, No). What docs wrong in your previous proof