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

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

L₁∩ L₂is decidable.

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

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_startto itself with labels 1 → 0,R and 0 → 1,L, and 2 → 2,L. There is also one arrow from q_startto q_acceptwith 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₂)}.

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}.

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. 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

Already member? Sign In

Purchased 3 times

Completion Status 100%