0
$\begingroup$

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.

My attempt :

Given, $X$ is REC, and $Y$ is RE only. Since REC is closed under complementation property. So, complement of REC is also REC. RE is not closed under complementation property, so complement of RE may not be RE.

Therefore,

$$Y\leq W$$

So, $W$ can be RE.

$$Z\leq X$$

So, $Z$ is REC. Hence, option $(1)$ is true. But, somewhere answer is given option $(3)$.

Can you explain in formal way, please?

$\endgroup$
1
+50
$\begingroup$

At first I didn't notice the \bar{}s over $X$ and $W$. I changed them to \overline, which is easier to see.

In the case of $X$ it doesn't matter: as $X$ is recursive, $\overline{X}$ is recursive too, so $Z\le_m \overline{X}$ is recursive.

In the case of $W$, it matters a lot. Here's why 3. is true: If $W$ were r.e., we would have $\overline{Y}\le_m W \le_m K$, where K is the halting problem. Thus $\overline{Y}\le_m K$ would be r.e. But then $Y$ would be recursive, which it isn't.

$\endgroup$
  • $\begingroup$ I got it, Thanks for nice explanation. $\endgroup$ – Mithlesh Upadhyay Feb 25 '16 at 14:42
  • $\begingroup$ You're welcome, & thank you. $\endgroup$ – BrianO Feb 25 '16 at 14:42
  • $\begingroup$ Assume complement property for CFLs. Since, we have proved that CFLs are not closed under property complementation. That means, if L is CFL but not regular, then the complement of L may not be CFL. That was my question :) $\endgroup$ – Mithlesh Upadhyay Feb 25 '16 at 14:46
  • $\begingroup$ I got here, if L and its complement L1, then (i) if L is REC then L1 also REC (ii) if L is RE but not REC then L1 is not RE (iii) if L is not RE then L1 is also not RE. Am I right? $\endgroup$ – Mithlesh Upadhyay Feb 25 '16 at 14:50
  • $\begingroup$ Ohh, I wouldn't have guessed that was your question :) But is it true? (by "may not be", do you mean "must not be" or "might not be"?) I don't of such a theorem, saying that if $L$ and $\overline{L}$ are both CFL then $L$ is regular. There may be a known or easy-enough counterexample. $\endgroup$ – BrianO Feb 25 '16 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.