L = { < M > | M is a turing machine and enter image description here }

Obviously, the language which L(M) is polynomially reducible to, is context free and hence recursive, so it is a decidable language .

Now, L(M) is reducible to decidable language.

I think this language is not decidable, as this language is non-trivial in the sense of rice theorem, as no recognizable language can be a part of L(M) and even this context free language belongs to L(M).

Is my understanding right ?

  • 3
    $\begingroup$ By the way, these "am I correct?" questions are not a good fit for StackExchange. There is no answer to that except "yes", which is not very informative. $\endgroup$
    – chi
    Oct 4 '16 at 17:20

Yes, your understanding is right.

The first part (about context-free languages which are decidable) is unneeded. To apply Rice, you only have to show that the property at hand only depends on $L(M)$ (which it does, trivially) and prove that the set is nontrivial. So the whole exercise bogs down to: exhibit $M$ satisfying the reduction property, and $M′$ not satisfying it.

To prove/disprove reduction you may have to use the fact that the language $0^p1^{2p}$ is decidable, as you argued.

  • $\begingroup$ Can you please elaborate the first line more ? I am having a bit misunderstanding with that . $\endgroup$
    – Garrick
    Oct 4 '16 at 17:25

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.