GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 64

Question

Which of the following languages are Turing-recognizable?

A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$.
B. $\{\langle M\rangle \mid M$ is a nondeterministic Turing machine and $M$ accepts 010$\}$.
C. $\{\langle M\rangle \mid M$ is a Turing machine and $M$ does not accept 101$\}$.
D. $\left\{\langle M\rangle \mid M\right.$ is a Turing machine and $\left.L(M)=\Sigma^*\right\}$.

Answer 1

GO BY OPTION ELIMINATING :

D SHOULDNT BE THERE AS TURING RECOGNIZABLE WHICH IS RE LANGUAGE HAVE UNIVERSALITY PROBLEM OF UNDECIDABLE AND OPTION C WHICH IS NON MONOTONIC PROPERTY

Comments

We can apply Rice theorem upon the languages of Turing Machines i.e. L(M) and not directly on Turing Machine M as far as I know.

Monotonic is a property of a language.

Correct me if I am wrong.

---

But in option D it is a monotone property i.e if a language accepts all strings then its superset also accepts all strings, so it should be RE and hence turing recognizable.