A question on decidability I have a homework question that is as follows:
L(P) is a language of ASCII input strings for which a given program, P, returns &quot;yes&quot;. Is the set of all input strings P decidable, such that P is a decision program and L(P) is decidable?
My intuition leads me to believe that the set is, in fact, decidable but I am having a tough time proving my answer.
Would appreciate any help on this. Thanks
Let $L=\{\langle M \rangle \mid M \text{ is a TM such }L(M)\in R\}$, where $\langle M\rangle$ is the encoding of a TM $M$, and $R$ is the set of all decidable languages. This is the language in question.
Notice that $R\neq \emptyset$ and also since there are languages not in $R$ (like the halting problem), then $R\neq RE$. Simply put, $R$ is not trivial (obviously).
Apply Rice's theorem on the property $"R"$, to directly get that $L$ is not decidable.