1. Let P = { | M is a TM that has a state that it never enters on input I }.

1. Let P-t("M", 1 M is a TM that has a state that it never enters on input I } (a) Suppose I prove A B By Dec, I mean Computable/Decidable. By Rec, I mean Recognizable but not Co-Recognizable. By Co-Rec, I mean Co-Recognizable but not Recognizable. By Neither, I mean neither Recognizable nor Co-Recognizable. Circle ALL that are possible. If A is decidable then B is: If A is not co-recognizable then B is: If B is recognizable then A is: If B is not decidable then A is: If B is Rec and Co-Rec then B is: Dec Rec Co-Rec Neither Dec Rec Co-Rec Neither Dec Rec Co-Rec Neither Dec Rec Co-Rec Neither Dec Rec Co-Rec Neither (b) Is the problem P recognizable/acceptable? Either prove it is or argue that it is not Is the problem P co-recognizable/acceptable? Either prove it is or argue that it is not. 7 sentences (c) Either prove Halting Scompute P or argue that it is impossible. Hint: In one case, try having a new character cloop and the transition function rules (qi, Cloop)-(a+1, Cloop, stay) Hint: In other case, give the chain of consequences that would follow leading to a contradiction (We only want No-No, Yes-Yes reductions.) (d) Again either prove Halting-compute P or argue impossible. (e) State Rice's Theorem. Can you directly use it to prove P orP is undecidable? (f) A Yes/No computational problem P (language) can be viewed as the set of yes instances. Define what it means for P to be enumerable. Compare and contrast this concept with the "list" definition of P being countable? Is the problem P countable? Is itenumerable? Give a one sentence argue. Is the problem -P countable? Is itenumerable