$30.00
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 L1 is decidable and L2 is Turing recognizable, then
L1 ∩ L2 is decidable. 10
3. True or False? (Prove that your answer is correct). If L1 and L2 are in NP, then L1 ∩ L2 is in NP. 15
4. Describe the language of the following TM over the alphabet {0, 1, 2}: There are three states qstart,
qaccept, and qreject. Three arrows from qstart to itself with labels 1 → 0, R and 0 → 1, L, and 2 → 2, L.
There is also one arrow from qstart to qaccept with label t → t, R.
10
5. Rigorously establish the decidability or undecidability of the following language:
L = {hM1, M2i | M1, M2 are TM’s and L(M1) ⊆ L(M2)}.
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 hx
2
1 + x
2
2 − 5i ∈ L as it
evaluates to 0 if we set x1 = 1 and x2 = 2. On the other hand hx
2
1 − 5i is not in L. Prove that L can
be decided by an oracle Turing Machine that has access to an oracle for
HaltTM = {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}}.
(a) Is L Turing recognizable? (Prove your answer)
(b) Is the complement of L Turing recognizable?(Prove your answer)
Course: COMP 330 SEC 001 Theory of Computation Page number: 2 / 2
WhatsApp us