Log In
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?

  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. 
in Theory of Computation
edited by

4 Answers

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

  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
can we not assume Y as a particular RE language ??
Yes, you can take any Y that is r.e but not recursive, to prove any statement False.

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

How B is recursively enumerable?

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

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

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

 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.


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.

How can this be true?

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


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.

@Praveen Saini


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?
6 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)

@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

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

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

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

wonderfully explained
5 votes
Answer is (c)
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

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


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 ?




Related questions

27 votes
4 answers
Which of the following decision problems are undecidable? Given NFAs $N_1$ and $N_2$ , is $L(N_1) \cap L(N_2) = \Phi$ Given a CFG $G = (N,\Sigma,P,S)$ and a string $x \in \Sigma^{*}$, does $x \in L(G)$} ? Given CFGs $G_1$ and $G_2$, is $L (G_1) = L(G_2)$? Given a TM $M$, is $L(M)=\Phi$ ? I and IV only II and III only III and IV only II and IV only
asked Feb 12, 2016 in Theory of Computation Sandeep Singh 4.7k views
27 votes
4 answers
Consider that $B$ wants to send a message $m$ that is digitally signed to $A$. Let the pair of private and public keys for $A$ and $B$ be denoted by ${K_{x}}^-$ and ${K_{x}}^+$ for $x=A, B$, respectively. Let $K_{x}(m)$ represent the operation of encrypting $m$ with a key $K_{x}$ and $H(m)$ ... $\left\{m, {K_{A}}^-(H(m))\right\}$ $\left\{m, {K_{A}}^+(m)\right\}$
asked Feb 12, 2016 in Computer Networks Sandeep Singh 5.3k views
24 votes
3 answers
Consider a computer system with $40$-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per process and each page table entry requires $48$ bits, then the size of the per-process page table is __________ megabytes.
asked Feb 12, 2016 in Operating System Sandeep Singh 6.5k views
20 votes
3 answers
The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are: $\Theta (n \log n)$, $\Theta (n \log n)$ and $\Theta(n^2)$ $\Theta (n^2)$, $\Theta (n^2)$ and $\Theta(n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n \log n)$ $\Theta (n^2)$, $\Theta (n \log n)$ and $\Theta (n^2)$
asked Feb 12, 2016 in Algorithms Sandeep Singh 3.9k views