38 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?

- $W$ can be recursively enumerable and $Z$ is recursive.
- $W$ can be recursive and $Z$ is recursively enumerable.
- $W$ is not recursively enumerable and $Z$ is recursive.
- $W$ is not recursively enumerable and $Z$ is not recursive.

79 votes

Best answer

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

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

1

if A is recursive enumerable, and reducible to B, then B is recursive enumerable.

How B is recursively enumerable?

0

treat problem A i.e RE as undecidable problem , so if a problem is undecidable and reducible to another problem say B then that B should also be undecidable, we can not decide or solve using using problem which is already unsolveble, now B can RE or not RE both are undecidable

2

Yes, but i think, if A is undecidable then B is undecidable , so, it can be non RE also ( not only RE)

14

i) if A is recursive enumerable, and reducible to B, then B is recursive enumerable.

This should be

i) if B is recursive enumerable, and A reducible to B, then A is recursive enumerable.

0

Is this a rule or is there a more generalized rule?

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

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

0

How can this be true?

if B is recursively enumerable, and A is reducible to B, then A is recursively enumerable.

1

I guess it should be

if A is recursive enumerable, and reducible to B, then B is recursive enumerable.

Ex: If the halting problem can be reduced to a problem "X" then "X" is also undecidable. However the converse is not true.

Please correct this.

0

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.

6 votes

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)

0

@Sanket , Sir , I'm unable to understand. I only know RE languages are not closed under complement. So if L is RE then L' maybe RE or may not be RE .... this closure property is valid for a language which is RE as well as REC or RE but not REC... Please clear my doubt

19

if complement of RE language is also RE then the language becomes REC

i.e. if L=RE and $\overline{L}$=RE then L=REC

complement of RE is "Not RE or Non RE" provided **language is not Recursive**

i.e.if L=RE and L is not REC then $\overline{L}$= Not RE

here It is given that Y is RE and not REC so $\overline{Y}$ is NOT RE language.

so if $\overline{Y}$ reduces to W it means W is also "Not RE".

complement of Recursive language is also Recursive so $\overline{X}$ is also recursive

and if a language Z reduces to $\overline{X}$ which is a recursive language then Z is also recursive language.

Hope this helps:)

5 votes

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