CS-701 Theory of Computation Mcqs Q & A Video Online Test Foram
Q1: Show that ATM is not mapping reducible to ETM. 10 marks
Spring 2016 – Mid

Q2: Let LALL = {M is a TM with input alphabet ∑ and L(M)∑*}, prove that LALL is not Turing recognizable. 10 marks
Spring 2016 – Mid

Q3: In the Silly Post Correspondence Problem (SPCP), in each pair the top string has the same length as the bottom string. Show that the SPCP is decidable, 10 marks
Spring 2016 – Mid

Q4: Lets recall that a language A is Truing recognizable if there is a TM M such that L(M)=A. 5 marks
Spring 2016 – Mid

Q5: Let X be the set{1,2,3,4,5} and Y be the set (6,7,8,9,10}. We describe the functions f:(X-->Y) and g:(X-->Y) in the following table.
 N 1 2 3 4 5 F(n) 6 7 6 7 6
 N 1 2 3 4 5 G(n) 10 9 8 7 6
(a) Is f one-to-one?          (b) Is f onto?       (c) Is f a correspondence?
(d). Is g one-to-one?        (e). Is g onto?     (f) Is g a correspondence?
Spring 2016 – Mid

Q6: Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable, using a proof by diagonalization. 10 marks
Spring 2016 – Mid
Q7: Show that the set of possible statements in TH(N,+,X) is turing recognizable. 10 marks
Spring 2016 – Mid
Q8: if ∀Y∃X[R1(x,x,y)], if we assign plus to (a,c,c) whenever a+b=c. if R is (universe) real number then whether the sentence is TRUE, justify you answer. 10 marks
Spring 2016 – Mid
Q9: Show that the set of all off all odd integers has one-to-one correspondence with the set of all even integers. 5 marks
Spring 2016 – Mid
Q10: Show that all positive numbers has one-to-one correspondence to real number. 5 marks
Spring 2016 – Mid
Q11: if A belong to a language that contains infinity pairs, prove that its uncountable. 5 marks
Spring 2016 – Mid
Q12: Consider following instance of PCP. Is it possible to find a match? If YES then give the dominos arrangements, If NO then prove. 5 marks
1/0, 101/1, 1/001
Spring 2016 – Mid
Q13: Show that 234 and 399 are relatively prime or not. 5 marks
Spring 2016 – Mid
Q14: Show that some TRUE statements in TH(N,+,X) are not proveable. 10 marks
Spring 2016 – Mid
Q15: Is PCP decidable over unary alphabet? 5 marks
Spring 2016 – Mid
Q16: Show that A≤TB and B≤TC then A≤TC. 10 marks
Spring 2016 – Mid
Q17: Prove that Turing recogniable languages are closed under concatenation. 10 marks
Fall 2015 – Mid
 Course Instructor Dr. Sarmad Abbasi Ph.D Computer ScienceRutgers University, USA Javascript is disable - Webestools - Vote Service (notation module) Books Book Title: Introduction to the Theory of Computation by Michael Sipser Solution ( Introduction to the Theory of Computation )