2
$\begingroup$

To my knowledge, lots of languages can be classified as undecidable after applying Rice's theorem, for example {"M" | L(M) is regular}.

But what I am not sure is, how to determine if a language is enumerable after applying Rice's theorem? I reckon we can examine that whether the M halt on some specific input, i.e. test if L(M) is an empty set. Am I right? Is there any principled way to determine a language's(composed of lots of Turing machines) enumerability?

$\endgroup$
2
  • $\begingroup$ You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable, then $L$ is not enumerable. To determine whether a language is enumerable, try to construct an enumerator for it. $\endgroup$ Commented Jan 9, 2017 at 15:50
  • $\begingroup$ @YuvalFilmus This is helpful. Thank you sir. $\endgroup$
    – Zhao Chen
    Commented Jan 9, 2017 at 16:21

2 Answers 2

2
$\begingroup$

You can use the fact that if $L$ is undecidable and $\overline{L}$ is enumerable then $L$ is not enumerable (since if both $L$ and $\overline{L}$ are enumerable, then $L$ is decidable). In order to determine whether an undecidable language is enumerable or not, you can try to construct an enumerator for the language or its complement.

$\endgroup$
1
$\begingroup$

In addition to Yuval's approach You can also read about monotonic and non-monotic properties of languages as well. This statement usually an extension to Rice theorem says :

“Every non-monotone semantic property

of Turing machines is unrecognizable”

$\endgroup$
1
  • $\begingroup$ Indeed, this is a part of the Rice-Shapiro theorem, which is quite powerful. It is commonly used to prove "non-RE" properties. $\endgroup$
    – chi
    Commented Jan 10, 2017 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.