How to determine if a language is recursive or recursively enumerable?
I have to determine whether a language (for example L={a^n b^m c^s | 0<=n<=m<=s}) is regular, context-free, recursive, recursively enumerable or none of them.
I know how to determine if a language is regular (find a DFA or regular expression that works) or context-free (find a PDA or context-free grammar that works); I know that a recursive language has a Turing machine that always halts and that a recursively enumerable language has a Turing machine that may not halt.
So the question is: is there a fast criteria to determine whether the language is recursive or recursively enumerable or neither? For example, I don't have to build a PDA to understand that a language is context-free, I can't see it by the fact that it requires one stack; is there a similar fast approach to the problem (that hopefully saves the trouble to build a Turing machine)?
Answer
There's no structural way to check if a language is recursive versus recursively enumerable. There's actually a really cool proof that says that for any automaton capable of recognizing the recursive languages, there's at least one RE language not in R that the automaton also accepts; it's a variant of the diagonalization argument you use to show the existence of undecidable problems.
The main way in which you prove a language is in RE but not R is to prove the language is in RE (perhaps by defining a TM for it), then to reduce a known problem in RE but not R to that problem. For example, if you can show that any instance of the halting problem can be solved by transforming it into an instance of your problem, you know that it can't have a recursive solution, and if you follow this up with a TM for the language you know that the language is in RE. Together, you have a language in RE but not R.