CS701 Midterm Current Paper 12 Dec 2017
cs701 My today Paper at 90:30 dated: 11/12/2017
2 Q 5 Marks 2 Q 10 Marks
1. What is Hilbert tenth problem, who solve it. How much time takeing to solve this problem (5).
2. Consider following instance of PCP. Is it possible to find a match? If yes then give the dominos arrangements. If NO then prove {[100/1], [1/ 00], [0/100]} (5)
3. Show that the collection of Turning-recognizable language is closed under start operation. (10)
4. Consider the sentence y x [R1 (x, x, y)]. Let’s assign PLUS to R1 where PLUS (a, b, c) is TRUE whenever a + b = c. If universe is N(Natural Numbers), is this sentence TRUE? Justify your answer. (10)
Emoticon