GATE CSE 2015 Set 2 | Recursively Enumerable Language and Turing Machine Question 11 | Theory of Computation

GATE CSE 2015 Set 2

MCQ (Single Correct Answer)

-0.3

Consider the following statements.

$$\,\,\,$$ $${\rm I}.\,\,\,\,\,\,\,\,\,$$ The complement of every Turing decidable language is Turing decidable
$$\,$$ $${\rm II}.\,\,\,\,\,\,\,\,\,$$ There exists some language which is in $$NP$$ but is not Turing decidable
$${\rm III}.\,\,\,\,\,\,\,\,\,$$ If $$L$$ is a language in $$NP,$$ $$L$$ is Turing decidable

Which of the above statements is/are true?

Only $${\rm I}$$$${\rm I}$$

Only $${\rm III}$$

Only $${\rm I}$$ and $${\rm II}$$

Only $${\rm I}$$ and $${\rm III}$$

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 2013

MCQ (Single Correct Answer)

-0.3

Which of the following statements is/are FALSE?
$$1.$$ For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine
$$2.$$ Turing recognizable languages are closed under union and complementation
$$3.$$ Turing decidable languages are closed under intersection and complementation
$$4.$$ Turing recognizable languages are closed under union and intersection

$$1$$ and $$4$$ only

$$1$$ and $$3$$ only

$$2$$ only

$$3$$ only

GATE CSE 2008

MCQ (Single Correct Answer)

-0.3

Which of the following is true for the language $$\left\{ {{a^p}} \right.\left| P \right.$$ prime $$\left. \, \right\}$$?

It is not accepted by a Turing machine

It is regular but not context-free

It is context-free but not regular

It is neither regular nor context-free, but accepted by a Turing machine