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

Question

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

• A. $L = \{\langle M \rangle\mid L(M) = \emptyset\}$
• B. $L = \{\langle M \rangle\mid L(M) = \Sigma^*\}$
• C. $L = \{\langle M \rangle\mid |L(M)| = 2(\text{ number of strings in L(M) is 2)}\}$
• D. $L = \{\langle M,w \rangle\mid w \in L(M)\}$

Answer 1

A is not even recursively enumerable as per Rice's theorem part 2. $L_{yes} = \{\}$ and $L_{no}$ can be any other set making $L_{yes}$ a strict subset of $L_{no}$ and thus $L$ is a non-monotonic property of language of Turing machines making it not even recursively enumerable (not even semi-decidable).

For B  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

C is also not recursively enumerable. We can take $L_{yes} = \{0, 1\}$ and $L_{no} = \{0,1, 00\}$ making $L_{yes}$ a strict subset of $L_{no}$ and thus $L$ is a non-monotonic property of language of Turing machines making it not even recursively enumerable (not even semi-decidable).

D is the acceptance problem for Turing machines. This is semi-decidable (L is recursively enumerable) as we can simulate $w$ on $M$ and if $M$ accepts $w$ we output "yes" making the problem semi-decidable. If $M$ goes to an infinite loop on $w$, we cannot output anything and that's why the problem is not decidable (L is not recursive).

Thus, only D is recursively enumerable.

Comments

C option is also RE but NOT REC.

 

edit: yes it is not re.

Answer 2

Options A and B are NOT-RE, 

I have mentioned the reason in this question → https://gateoverflow.in/346934

Now let’s talk about Options C and D.

The question is asking for RE but not REC, which means we must HALT for members, but we are not sure for non-members.

Now in Option C, the size of L(M) is 2, which means with dovetailing we can say whether it’s RE but not REC or not.

By running our TM for all strings as followed using the dovetailing method and stop at that point where we have 2 strings accepted.

Hence its REC.. which is not what asked in question.

but, in Option D → we can say for members 100%. but for non member even with dovetailing, we can’t say anything.

 

Edit : Option C's explanation is slightly wrong. Read my comment below for the correct one.

Comments

@Udhay_Brahmi Language in option C is not RE.

---

Got it, I ignored this point. 

What I was doing is to prove that the “length of language is 2”, if yes → HALTS, if no → ?(no idea). Hence RE but not REC.

But the twist is in the yes part.

 To say that it halts for the “yes part”, we have to check for all strings over sigma* & see whether it is not-halting for all other strings or not(which is not what done by RE).

Hence, Option C is not RE.

→ (I am not going to make changes in my original answer, because I think its good to know why above way of thinking is not accurate.)

Request : please remove the downvote.😢

---

@samarpita let me know if this comment makes any sense or not,

---

@Udhay_Brahmi Already a very good explanation is given by @gatecse for option C.

if it’s non-monotonic property of re languages then why to use devotailing method? Devotailing method is used when it is monotonic property of re languages.