2
$\begingroup$

Given a language $L$, I sometimes try to find a subset of $L' \subseteq L$ which I can prove is undecidable. I conclude that if a subset of $L$ is undecidable, then $L$ must be undecidable as well. Is this correct for arbitrary languages $L$ and $L' \subseteq L$?

What if someone said: $L'$ could be empty (we don't know due to the undecidability of $L'$), and we cannot conclude anything about $L$ from $L' = \varnothing$, therefore the proof is insufficient. Is this a valid point?


For example, in order to prove that the language $$L = \left\{ w : M_w \text{ halts on a a finite set of inputs} \right\}$$ is undecidable ($M_w$ is a turing machine constructed from $w$), I use the fact that $L \text{ is undecidable} \iff L^c \text{ is undecidable}$. $L^c$ can be described as $$L^c = \left\{ w : M_w \text{ halts on an infinite set of inputs} \right\}$$ and $$L' = \left\{ w : M_w \text{ halts on all inputs } \Sigma^* \right\}$$ can be considered a subset of $L^c$. Using reduction, I can then prove that $L'$ is undecidable. If my assumption about subsets is correct, then $L^c$ must be undecidable as well, and therefore $L$ is undecidable.

(I know that the undecidability of the above language can be proven simpler, but I need an example for the use of subsets.)

$\endgroup$
3
$\begingroup$

No, your conclusion is not correct. The fact that $L'\subseteq L$ is undecidable do not imply anything about $L$. Indeed, consider $L=\Sigma^*$ for some finite alphabet $\Sigma$. Then, $L$ is decidable.

Now consider $L'\subset L$ such that $w\in L'$ iff $w$ is the description of a halting Turing machine written with characters from $\Sigma$. Then, $L'$ is, of course, undecidable.

$\endgroup$
  • $\begingroup$ Your example is surprisingly simple, thank you. $\endgroup$ – just.kidding Feb 27 '17 at 18:02
2
$\begingroup$

$L'$ can not be empty and undecidable at the same time.

However, the objection stands: given $L' \subseteq L$, knowing that $L'$ is (un-)decidable does not imply anything about $L$.

Indeed, if the complement of $L'$ is infinite, there are uncountably many languages larger than $L'$, so most of those are undecidable (and not even RE).

There are also languages larger than $L'$ which are cofinite, i.e. the complement of a finite set. Those are decidable.

In general, trying to reason about the decidability of sublanguages or superlanguages is not useful. You have to write a reduction function (and prove it such) to achieve (un-)decidability results. If inclusion were enough, probably no one would bother with reduction :-)

$\endgroup$

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.