4.9k views

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.

edited | 4.9k views

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

by Veteran (57k points)
edited
+1
can we not assume Y as a particular RE language ??
0
Yes, you can take any Y that is r.e but not recursive, to prove any statement False.
+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
+1

@amsar $A \leq B$  it means that solution of problem B can be used to solve problem A.

+2
Yes, but i think, if A is undecidable then B is undecidable , so, it can be non RE also ( not only RE)
+1
I think if A is r.e then B is r.e and above in hierarchy.
+13

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
WHAT IS THE MEANING OF "CANNOT BE HARDER THA"
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.

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

@Praveen Saini

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

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)

by Active (4.1k points)
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
+16

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:)

0
Sanket Sir , thanks :)
0
one of the most clear solution. Thanx a lot
0

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

0
wonderfully explained
by (233 points)
+1
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??

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

by Active (4.1k points)