Course: COMP 330 SEC 001 Theory of Computation

Theory of Computation

COMP 330 SEC 001

10 1. True or False? (Prove that your answer is correct). If L is a regular language and A ⊆ L, then A is

decidable.     10

2. True or False? (Prove that your answer is correct). If L₁ is decidable and L₂ is Turing recognizable, then

L₁ ∩ L₂ is decidable.

10

3. True or False? (Prove that your answer is correct). If L₁ and L₂ are in NP, then L₁ ∩ L₂ is in NP.

15

4. Describe the language of the following TM over the alphabet {0,1,2}: There are three states q_start, q_accept, and q_reject. Three arrows from q_start to itself with labels 1 → 0,R and 0 → 1,L, and 2 → 2,L. There is also one arrow from q_start to q_accept with label t → t,R.

10 5. Rigorously establish the decidability or undecidability of the following language:

L = {hM₁,M₂i | M₁,M₂ are TM’s and L(M₁) ⊆ L(M₂)}.

15

6. Let us call a deterministic Turing Machine M super-fast if there exists a constant c (here c can depend on M but it does not depend on the input) such that the following holds: On every input w, the TM M halts after at most c steps. Rigorously establish the decidability or undecidability of the following languages:

L = {hMi | M is a super-fast TM}.

10

7. Let L be the set of all hpi such that p is a multivariate polynomial with integer coefficients that evaluates to zero for some assignment of positive integers to its variables. For example  as it evaluates to 0 if we set x₁ = 1 and x₂ = 2. On the other hand  is not in L. Prove that L can be decided by an oracle Turing Machine that has access to an oracle for

Halt_TM = {hM,wi | M is a TM that halts on input w}.

20 8. Consider the following language:

L = {hM,wi|M is a TM and L(M) = {w}}.

1. 1. Is L Turing recognizable? (Prove your answer)
   2. Is the complement of L Turing recognizable?(Prove your answer)

Course: COMP 330 SEC 001 Theory of Computation       Page number: 2 / 2