(a) (4 points) Describe what it means for a language to be computable (decidable), computably enumerable...

  

Transcribed Image Text:

(a) (4 points) Describe what it means for a language to be computable (decidable), computably enumerable (c.e.) but not computable, and co-c.e. but not com- putable. (b) (6 points, 2 points each) For each of the following languages, determine which, if any, of the above categories the language belongs to: i. ATM ii. SUBSET-SUM iii. XTM (Recall: XTM = {(M): M does not accept (M)}. (a) (4 points) Describe what it means for a language to be computable (decidable), computably enumerable (c.e.) but not computable, and co-c.e. but not com- putable. (b) (6 points, 2 points each) For each of the following languages, determine which, if any, of the above categories the language belongs to: i. ATM ii. SUBSET-SUM iii. XTM (Recall: XTM = {(M): M does not accept (M)}.