CS 575, Spring '16, Homework 4

1. Describe how you would prove that a language L was undecidable.

2. Give another method of proving that a language L was undecidable.

3. Consider the language $L\; =\; \{T\_n:\; T\_n(23)\; \uparrow \}$
a. Is L decidable? Prove your answer.
a. Is L semi-decidable? Prove your answer.

4. As a warm-up for the midterm, consider the language $L\; =\; \{T\_x:\; T\_x(x)\; \downarrow \; in\; \le \; |x|\; steps\}$
Is this language in P, NP, Decidable, or Semi-decidable? Prove your answer.

5. Consider the language $L\; =\; \{\phi \; in\; 3CNF\; form:\; \phi \; has\; a\; satisfying\; assignment\; that\; assigns\; exactly\; two\; true\; literals\; per\; clause\}$
Is this language in P, NP, Decidable, or Semi-decidable? Prove your answer.