The problem of determining whether a recursively enumerable language is empty or infinite cannot be solved. The proof goes by reduction to the problem of decidability, which is known to be unfeasible for recursively enumerable languages.

However, the recursive languages are decidable. What about the problem of emptiness and infiniteness of a recursive language?


Right off the bat we have a problem: how exactly are you listing the recursive languages? We can easily list the recursively enumerable languages (by listing Turing machines), but telling whether a given recursively enumerable language is actually recursive is undecidable. That is, the set $$Tot=\{e: \Phi_e\mbox{ is total}\}$$ of indices of recursive languages is not recursive. Indeed, $Tot$ is exactly as complicated as $\{e: \{x: \Phi_e(x)\downarrow=1\}\mbox{ is infinite}\}$, the set of infinite recursively enumerable languages, and strictly more complicated than the set $\{e: \{x: \Phi_e(x)\downarrow=1\}\mbox{ is empty}\}$ of empty recursively enumerable languages.

EDIT: To clarify, this isn't informal - there is a rigorous notion of relative complexity of undecidable problems, called Turing reducibility. Showing e.g. that $Tot$ is strictly more complicated in this sense than the set of all indices of empty recursively enumerable languages is a good exercise.

So the problem of telling whether a recursive language is infinite, or empty, is overwhelmed by the problem of telling whether a language is in fact recursive!

That said, we could look at a subclass of the recursive languages - say, the primitive recursive languages. We do have an effective listing $\psi_i$ of the primitive recursive functions in one variable, and we can identify such a function with the language $\{n: \psi_i(n)=1\}$. We can now ask: how complicated are the sets of (indices for) primitive recursive languages which are empty, or are infinite?

It turns out that each such set is indeed undecidable. For instance, there is a recursive $f$ such that for a given Turing machine $\Phi_e$ and natural number $n$, $\psi_{f(e, n)}(k)=1$ iff $\Phi_e(n)$ halts and equals $1$ in $k$ steps. Thus, we can reduce the Halting Problem to the set of indices of nonempty, and the infinite, primitive recursive languages.

| cite | improve this answer | |
  • $\begingroup$ Thanks for a very informative answer! I get it until the point where you use $\downarrow = 1$ notation I am unfamiliar with, what does it stand for? (halts and equals 1 ?) $\endgroup$ – NumberFour Feb 6 '16 at 19:24
  • $\begingroup$ @NumberFour Yep, halts and equals 1. $\endgroup$ – Noah Schweber Feb 6 '16 at 19:29

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.