GATE CSE 2016 Set 1 | Question: 44

Question

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$  and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard many-one reduction). Which one of the following statements is TRUE?

• A. $W$ can be recursively enumerable and $Z$ is recursive.
• B. $W$ can be recursive and $Z$ is recursively enumerable.
• C. $W$ is not recursively enumerable and $Z$ is recursive.
• D. $W$ is not recursively enumerable and $Z$ is not recursive. 

Comments

option C ??

---

Thanks....

---

The complement of R.E need not be R.E, doesn’t that be that there could be cases where complementof R.E. is R.E., making A as the answer

Answer 1

$X$ is recursive language, so $\overline{X}$ is also recursive.

$Y$ is recursively enumerable,but not recursive so $\overline{Y}$ is not recursively enumerable language.

$A \leq B$, ($A$ is reducible to $B$) , i. e, solving $A$ cannot be "harder" than solving $B$.

1. If $A$ is reducible to $B$, and $B$ is decidable, then $A$ is decidable.
            i) if $A$ is reducible to $B$, and $B$ is recursive, then $A$ is recursive.
2. If $A$ is undecidable and reducible to $B$, then $B$ is undecidable.
           i) if $B$ is recursively enumerable, and $A$ is reducible to $B$, then $A$ is recursively enumerable.
           ii) if $A$ is not recursively enumerable, and reducible to $B$, then $B$ is not recursively enumerable.

Now Back to question.

$\overline{Y}$ is not recursively enumerable, and reducible to $W$, then $W$ is not recursively enumerable (using 2(ii)).

$Z$ is reducible to $\overline{X}$ and $\overline{X}$ is recursive, then $Z$ is recursive (using 1(i)). 

Option C is correct.

Comments

@rohith1001

Read this comment by arjun sir

https://gateoverflow.in/39721/gate2016-1-44?show=40518#c40518

---

Thanks @chirudeepnamini. I got to know my mistake.

Given: A is recursively enumerable and not recursive.

A is recursively enumerable means there exists a TM that halts on all strings in A but also there are some strings(which are not in A) for which the TM enters infinite loop. If such A is reducible to B. Then B is definitely not recursive (because if at all B is recursive then I can reduce A to B always and hence make A also recursive). But we have 2 possibilities here. (1) B can be REL - halts on all valid inputs but enters infinite loop on some invalid inputs (2) B can be Not-REL - doesn't halt on some valid inputs and also doesn't halt on some invalid inputs. Due to the above possibility (2) my statement is wrong. :)

 

However we can make a statement like this. 

If A is recursively enumerable and there exists some B which is reducible to A then B is also recursively enumerable.

---

If it was not mentioned in the question that Y is not recursive, then A would be the answer right?

Answer 2

recursive language is closed under complementation so x^c   is recursive and hence z is recursive

if a language L and L^c  both are recursive enumerable then language L is recursive

so for a Y to be recursive enumerable and not recursive .....Y^c  must not be recursive enumerable and hence W is not recursive enumerable

option c)

Comments

one of the most clear solution. Thanx a lot

---

 Sanket_ One of the best answers on this site. Simply wow!

---

wonderfully explained

Answer 3

$Note\ points\ for:\ A\ is\ reducible\ to\ B:\ A\rightarrow B$

$1)\ A\ is\ UD\rightarrow B\ is\ UD$

$2)\ B\ is\ D\rightarrow A\ is\ D$

$3)\ B\ is\ recursive\rightarrow A\ is\ recursive$

$4)\ B\ is\ RE\rightarrow A\ is\ RE$

$5)\ A\ is\ D\rightarrow B\ may\ or\ may\ not\ D$

$6)\ B\ is\ UD\rightarrow A\ may\ or\ may\ not\ UD$

$7)\ A\ is\ not\ recursive\rightarrow B\ also\ not\ recursive$

$8)\ A\ is\ not\ RE\rightarrow B\ also\ not\ RE$

---

$Y'\rightarrow W$

$Given\ Y\ is\ RE\ but\ not\ recursive\ .Hence\ Y'\ will\ be\ Non-RE$ 

$Look\ for\ point\ 8)$

---

$Z\rightarrow X'$

$Given\ X\ is\ Recursive .Hence\ X'\ will\ be\ Recursive$ 

$Look\ for\ point\ 3)$

---

$Ans:C$

Comments

what about B is not recursive → ??

B is not R.Enumerable → ??

A is Recursive – > ??

A is R.Enumerable → ??

---

@Praveen Sir, @Kushagra,  For the 4th point,

4) B is RE→A is RE,

Why it isn’t

 B is RE→A may be RE or may be Recursive ?

Can u pls elaborate it ?

 

Thanks

---

4th point is wrong

It will be B is RE → A may or may not be RE

Answer 4

Answer is (c)

Comments

If A is reducible to B and A is "Not RE", then it means A is Undecidable, so B is also Undecidable. But how can we say that B is surely "Not RE" as it could be "RE but not REC" also. So, why the correct answer to the gate question is C and not A??