Description

CSE340: Theory of Computation (Homework Assignment 4)
Total Number of Pages: 1 Total Points 55

Question 1. Which of the following languages are decidable/undecidable? Prove your answer by either giving an algorithm or a proof of undecidability.
(a) (5 points) L1 = {hM,Ni | M,N are two TMs and M takes fewer steps than N on input }
(b) (5 points) L2 = {hMi | M takes at most 2340 steps on some input}
(c) (5 points) L3 = {hMi | there are infinitely many TMs equivalent to M}
(d) (5 points) L4 = {hM,Ni | L(M) ∩ L(N) is infinite}
Question 2. (8 points) In class we showed that REGTM is not Turing recognizable. Prove that REGTM is also not co-Turing recognizable.
Question 3. One of the following two languages is Turing recognizable and the other is not. State which is which and give proofs for your answer.
(a) (6 points) A = {hMi | |L(M)| ≥ 340}
(b) (6 points) B = {hMi | |L(M)| ≤ 340}
Question 4. Prove that the following problems are NP-complete.
(a) (7 points) LPATH = {hG,s,t,ki | G has a simple path of length at least k from s to t}
Page 1 of 1