# 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 "yes". 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

• Im struggling to understand the language you want to show decidability for. Can you formally define it (with mathematical symbols)? – nir shahar May 9 at 18:49
• Is it the set of all turing machine repersentations with decidable languages? – nir shahar May 9 at 18:50
• The language is the set of strings P where P is a python decision program, if that makes sense. – TheClash May 9 at 19:10

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.
• Note that Rice's theorem only provides a lower complexity bound. In fact $L$ is substantially more complicated than that: it's $\Sigma^0_3$-complete, so Turing-equivalent to ${\bf 0'''}$ (basically "the halting problem's halting problem's halting problem"). Proving this takes work though. – Noah Schweber May 9 at 21:03