1
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Consider the following languages.

$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_1} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on some input $$\left. \, \right\},$$
$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_2} = \left\{ {\left\langle M \right\rangle |M} \right.$$ takes at least $$2016$$ steps on all inputs $$\left. \, \right\}$$ and
$$\,\,\,\,\,\,\,\,\,\,\,\,$$ $${L_3} = \left\{ {\left\langle M \right\rangle |M} \right.$$ accepts $$\left. \varepsilon \right\},$$

where for each Turing machine $${M,\left\langle M \right\rangle }$$ denotes a specific encoding of $$M.$$ Which one of the following is TRUE?
A
$${L_1}$$ is recursive and $${L_2},$$$${L_3}$$ are not recursive
B
$${L_2}$$ is recursive and $${L_1},$$$${L_3}$$ are not recursive
C
$${L_1},$$$${L_2}$$ are recursive and $${L_3}$$ is not recursive
D
$${L_{1,}}$$$${L_{2,}}$$$${L_{3}}$$ are recursive
2
GATE CSE 2016 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Let $$X$$ be a recursive language and $$Y$$ be a recursively enumerable but not recursive language. Let $$W$$ and $$Z$$ be two languages such that $$\overline Y$$ reduces to $$W,$$ and $$Z$$ reduces to $$\overline X$$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?
A
$$W$$ can be recursively enumerable and $$Z$$ is recursive.
B
$$W$$ can be recursive and $$Z$$ is recursively enumerable.
C
$$W$$ is not recursively enumerable and $$Z$$ is recursive.
D
$$W$$ is not recursively enumerable and $$Z$$ is not recursive.
3
GATE CSE 2014 Set 1
MCQ (Single Correct Answer)
+2
-0.6
Let $$L$$ be a language and $$\overline L$$ be its complement. Which one of the following is NOT a viable possibility?
A
Neither $$L$$ nor $$\overline L$$ is recursively enumerable (r.e).
B
One of $$L$$ and $$\overline L$$ is r.e. but not recursive; the other is not r.e.
C
Both $$L$$ and $$\overline L$$ are r.e. but not recursive.
D
Both $$L$$ and $$\overline L$$ are recursive.
4
GATE CSE 2014 Set 2
MCQ (Single Correct Answer)
+2
-0.6
Let $$< M >$$ be the encoding of a Turing machine as a string over $$\sum { = \left\{ {0,1} \right\}.}$$
Let $$L = \left\{ { < M > \left| M \right.} \right.$$ is a Turing machine that accepts a string of length $$\left. {2014} \right\}.$$ Then, $$L$$ is
A
decidable and recursively enumerable
B
un-decidable but recursively enumerable
C
un-decidable and not recursively enumerable
D
decidable but not recursively enumerable
GATE CSE Subjects
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12