GATE CSE 2014 Set 2 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2014 Set 2

MCQ (Single Correct Answer)

-0.3

Let $$A\,\,{ \le _m}\,\,B$$ denotes that language $$A$$ is mapping reducible (also known as many-to-one reducible) to language $$B.$$ Which one of the following is FALSE?

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursive then $$A$$ is recursive.

If $$A\,\,{ \le _m}\,\,B$$ and $$A$$ is undecidable then $$B$$ is un-decidable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is recursively enumerable then $$A$$ is recursively enumerable.

If $$A\,\,{ \le _m}\,\,B$$ and $$B$$ is not recursively enumerable then $$A$$ is not recursively enumerable.

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 Papers

2024