The Gateway to Computer Science Excellence

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

+70 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)

+12

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,503 answers

195,502 comments

100,866 users