0
$\begingroup$

I'm still insecure in the section decidability (no proof needed, I want to divine it):

X is decidable and Y is undecidable. Is the intersection of X and Y decidable or undecidable?

X is decidable and Y is a partial quantity of X. Is Y decidable, too or not?

Thanks!

$\endgroup$
  • $\begingroup$ What do you think? What have you tried? We're not here to do your exercises for you, so please show us the effort you've made on your own (and you should be making a substantial effort before asking) and what you've tried and where you got stuck. $\endgroup$ – D.W. Jun 16 '14 at 22:47
  • 1
    $\begingroup$ related/duplicate: cs.stackexchange.com/q/2982/157 cs.stackexchange.com/q/17966/157 and others. $\endgroup$ – Ran G. Jun 17 '14 at 1:22
  • $\begingroup$ Like I mentioned, I don't need any proof or solutions, only the fact. Thanks! $\endgroup$ – user22709 Jun 17 '14 at 8:20
  • 1
    $\begingroup$ @user22709 Simple yes/no answers are not well suited to this site. Our goal is to build a high-quality repository of questions and answers that will be useful to more people than just the asker of the question. While it's great that you want to figure out the proofs yourself, it's hard to see a yes/no answer being useful to anyone other than you. $\endgroup$ – David Richerby Jun 17 '14 at 8:56
2
$\begingroup$

For your first question, the answer is that $X\cap Y$ will not necessarily be decidable. Let $Y$ be an undecidable language over an alphabet $\Sigma$ and let $X=\Sigma^*$. Then obviously $X$ will be decidable and $X\cap Y=Y$ will be undecidable. On the other hand, the intersection may be decidable, as we could show by letting $X=\emptyset$.

For your second question, I assume that by "$Y$ is a partial quantity of $X$" you mean that $Y$ is a subset of $X$ (i.e., $Y\subseteq X$). Then we can do a similar construction, letting $X=\Sigma^*$, and $Y$ be undecidable, so again, $Y$ may or may not be decidable.

It's worth mentioning that this latter result frequently trips up students. Very few properties of languages are closed under subset/superset: there's no guarantee that a subset of a regular language will be regular, for example.

$\endgroup$

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