GATE CSE 2016 Set 1 | Recursively Enumerable Language and Turing Machine Question 7 | Theory of Computation

GATE CSE 2016 Set 1

MCQ (Single Correct Answer)

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

$$W$$ can be recursively enumerable and $$Z$$ is recursive.

$$W$$ can be recursive and $$Z$$ is recursively enumerable.

$$W$$ is not recursively enumerable and $$Z$$ is recursive.

$$W$$ is not recursively enumerable and $$Z$$ is not recursive.

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

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

$${L_1}$$ is recursive and $${L_2},$$$${L_3}$$ are not recursive

$${L_2}$$ is recursive and $${L_1},$$$${L_3}$$ are not recursive

$${L_1},$$$${L_2}$$ are recursive and $${L_3}$$ is not recursive

$${L_{1,}}$$$${L_{2,}}$$$${L_{3}}$$ are recursive

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-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

decidable and recursively enumerable

un-decidable but recursively enumerable

un-decidable and not recursively enumerable

decidable but not recursively enumerable

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.6

Let $$L$$ be a language and $$\overline L $$ be its complement. Which one of the following is NOT a viable possibility?

Neither $$L$$ nor $$\overline L $$ is recursively enumerable (r.e).

One of $$L$$ and $$\overline L $$ is r.e. but not recursive; the other is not r.e.

Both $$L$$ and $$\overline L $$ are r.e. but not recursive.

Both $$L$$ and $$\overline L $$ are recursive.