1
$\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$
  • $\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$ – Yuval Filmus Jan 9 '17 at 15:50
  • $\begingroup$ @YuvalFilmus This is helpful. Thank you sir. $\endgroup$ – Zhao Chen Jan 9 '17 at 16:21
1
$\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$
  • $\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 Jan 10 '17 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.