1
$\begingroup$

Given that $L_1$ is decidable language. That means it has a TM ($M_1$) decider. Now we consider a language, $L_p$;

$$L_p = \left \{ \langle M \rangle \mid L(M) \text{ is reducible to } L(M_1) \right \}$$

$L_p$ consists of all the encodings of the Turing machines whose language is reducible to $L_1$.

What can we say about $L_p$, Or, $L_p$ is decidable or undecidable ?

I understand if we assume to have a decider for $L_p$ and using this as component if we can construct a TM which decides a problem $P$. If $P$ is already known as undecidable then we can conclude that out assumed decider for $L_p$ does not exist.

How to come up with this reduction idea for $L_p$ ?

$\endgroup$
  • 4
    $\begingroup$ You tagged the question rice-theorem; why didn't you apply it? $\endgroup$ – Raphael Oct 3 '16 at 10:04
  • $\begingroup$ I assume that $M_1$ is a Turing machine such that $L(M_1) = L_1$. This not clear from your question. $\endgroup$ – Hans Hüttel Oct 3 '16 at 13:02
3
$\begingroup$

Let $L_1$ be a decidable language. Consider the class of Turing-recognizable languages

$$\mathcal{S} = \{ L \mid L \mbox{ reduces to } L_1 \}$$

This class is non-trivial in the sense of Rice's theorem, as no recognizable but undecidable language can be an element of $\mathcal{S}$, and since we obviously have that $L_1 \in \mathcal{S}$.

You can now apply Rice's theorem to get that $L_p$ is undecidable.

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