The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+29 votes
4.3k 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. 
asked in Theory of Computation by Loyal (7.1k points)
edited by | 4.3k views

3 Answers

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

  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.

answered by Veteran (55.8k points)
edited by
+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.
+9

 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. 

+5 votes
Answer is (c)
answered 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??
+4 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)

answered by Active (4k 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
+15

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,587 questions
54,197 answers
187,535 comments
71,151 users