I recently came across this language:

$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$

It was asked in the question to find out whether language L is decidable or undecidable.

As far as I could reason out, language L is the set of all recursive enumerable languages or set of all turing machines.

But I can't figure out whether this language is decidable or not.

Can anyone please help me out??

Thanks in advance!!

  • $\begingroup$ Well, if, as you say, $L$ is simply the language of all TM encodings, then what do you need to check in order to decide it? $\endgroup$ – dkaeae Dec 4 '18 at 9:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.