Emptiness and infiniteness decidable for recursive languages?

1.2k Views Asked by At

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?

2

There are 2 best solutions below

2
On BEST ANSWER

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.

0
On

Maybe a different argument, which implies undecidablity of of both of your problems, emptiness and finiteness, for recursive languages.

We will argue that both problems are already undecidable for context-sensitive languages. As a context-sensitive grammar always expands strings in a derivation, languages decribed by them are recursive, as for a given input word $w$ we only have to inspect all derivations up to the length of $w$.

Now, we will show that if we can decide both problems for the context-sensitive languages, we could also decide them for the recursively enumerable ones. Let $L$ be a recursively enumerable language given by a deterministic Turing machine, which, if it accepts an input, leaves it one the tape and enters a special halting state from which no further movements are allowed. Now, the transitions of the machine could be interpreted as context-sensitive rewriting rules, if everytime we delete a symbol, we do not actually delete it, but use a special symbol to indicate this, and write the new symbol aside of it. In the operational mode, we just ignore this symbol, but beside from this operate the grammar like the Turing machine.

The context-sensitive grammar works on configurations, i.e, tape content with a single symbol indicating the current state and head position in it, but enrichted with the additional symbol. The terminal symbols are this additonal symbol, the tape symbols and the unique halting state. Then, the machine accepts an empty (or finite) language if and only if the grammars generates an empty (or finite) language.

Note that for finiteness, the property that the original machine is deterministic and that once it enters the halting state, it could not operate further, is important. By this, "useless" operations like deleting a symbol and then writing it back, which would the grammar allow to derive infinite long strings with the 'deletion symbol', are not possible.