GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 28

Question

Which of the following languages is/are not recursively enumerable? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices)

• A. $L = \{\langle M \rangle\mid L(M) = \Sigma^*\}$
• B. $L = \{\langle M \rangle\mid L(M) \text{ is finite}\}$
• C. $L = \{\langle M \rangle\mid L(M) \text{ is infinite}\}$
• D. $L = \{\langle M \rangle\mid L(M) = \emptyset\}$

Answer 1

All the four languages are not recursive as they all are non-trivial properties of language of Turing machines (Rice's theorem part $1.$)

For B and D, we can easily apply Rice's theorem part $2$ and prove them as not recursively enumerable. For B, $L_{yes}$ can be taken as $\{\}$ and $L_{no}$ can be any infinite set making $L_{yes}$ a strict subset of $L_{no}$ (non monotonicity). For D, $L_{yes} = \{\}$ and $L_{no}$ can be any other set making $L_{yes}$ a strict subset of $L_{no}$.

For C we cannot apply Rice's theorem but through reduction we can see this is also not recursively enumerable. Reference: https://gateoverflow.in/78/l-m-is-infinite

For A also we cannot apply Rice's theorem part $2$ but via reduction this can be shown as not recursively enumerable. Reference: https://gateoverflow.in/79/l-m-%CF%83

So, correct answer A;B;C;D

Answer 2

This is how I approach this question:

B : L(M) is finite

Now, let’s check NON-MONOTONIC Property

→  P(something ‘x’) = True and P(something ‘y’) = False, then x is strict subset of y.

Now as it is given that M is TM which means we can apply the RICE theorem happily.

Now here ‘x’ = $\phi$ and ‘y’ = a* as both are RE.

Hence we can say that this will follow NON-MONOTONIC property which implies UNRECOGNIZABLE(NOT RE).

---

D : L(M) is $\phi$

Now, let’s check NON-MONOTONIC Property

→  P(something ‘x’) = True and P(something ‘y’) = False, then x is strict subset of y.

Now as it is given that M is TM which means we can apply the RICE theorem happily.

Now here ‘x’ = $\phi$ and ‘y’ = a* as both are RE.

Hence we can say that this will follow NON-MONOTONIC property which implies UNRECOGNIZABLE(NOT RE).

---

But the actual game starts at Option A, C 🔥

A, C : You can check that, they are MONOTONIC right!!, which means we can’t do anything with the rice theorem now.

Now, We apply GO-METHOD + DOVETAILING.

 “As L is infinite, even with dovetailing one can’t recognize members in finite time.”

Which makes these options NOT-RE.

Comments

@Deepak Poonia sir please re-check it.

---

Correct it is.

Verification of Non-Monotonic Property is done as following:

Property $P$ for Set of RE languages is called Non-Monotonic:

$if$ there exists two RE languages $L_1,L_2$ such that $L_1 \subset L_2 $ and $P(L_1) = True, P(L_2) = False$