# Decidability of the language of all TMs whose languages reduce to a fixed decidable language

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$ ?

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

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.