0
$\begingroup$

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

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

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Schweber May 9 at 21:03
  • 1
    $\begingroup$ Thank you for explaining this clearly. I think it was the layout of the question that I was struggling to understand. $\endgroup$ – TheClash May 10 at 10:30
  • $\begingroup$ Seems like it. Next time, try to write down the formal definition of the language and work with it. It makes everything much simpler to think of! $\endgroup$ – nir shahar May 10 at 10:32

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.