retagged by
12,269 views
47 votes
47 votes

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?

  1. $W$ can be recursively enumerable and $Z$ is recursive.
  2. $W$ can be recursive and $Z$ is recursively enumerable.
  3. $W$ is not recursively enumerable and $Z$ is recursive.
  4. $W$ is not recursively enumerable and $Z$ is not recursive. 
retagged by

5 Answers

Best answer
95 votes
95 votes

$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.

edited by
9 votes
9 votes

recursive language is closed under complementation so xc   is recursive and hence z is recursive

if a language L and Lc  both are recursive enumerable then language L is recursive

so for a Y to be recursive enumerable and not recursive .....Ymust not be recursive enumerable and hence W is not recursive enumerable

option c)

7 votes
7 votes

$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$

5 votes
5 votes
Answer is (c)
Answer:

Related questions