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, does this change with whether you can solve the Halting problem? (c) Supposc you think it undignified to feed a TM M a description "M" of itself. Instcad, of mak- ing M's nenesis be 1M-"M", lets instead defineM = F(M) where F(M) is the descrip- tion of what the TM M fcars the most. For cxample, F(MSherlock Homes)"Moriarty" and lan) = "Kryptonite" i. Suppose F(M) is distinct for each TM M, ie. 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, ie.M. M. M M, 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) Supposc you think it undignified to feed a TM M a description "M" of itself. Instcad, of mak- ing M's nenesis be 1M-"M", lets instead defineM = F(M) where F(M) is the descrip- tion of what the TM M fcars the most. For cxample, F(MSherlock Homes)"Moriarty" and lan) = "Kryptonite" i. Suppose F(M) is distinct for each TM M, ie. 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, ie.M. M. M M, 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