Deciding if a recursively enumerable language is finite

1.9k Views Asked by At

A language $L \subseteq X^{\ast}$ is recursively enumerable if there exists a Turing machine enumerating the strings in $L$, here after a word from $L$ is written we do not know if it will be the last one, and the machine runs forever without printing anything new (or just repeats words already written). Equivalently a lanuage is recursively enumerable if there exists a Turing machine which accepts inputs, and halts if the input word is in $L$, and has an unspecified behaviour otherwise. Or similar if there exists a partial computable function $f : L \to \{1\}$.

Given a recursively enumerable language, is there an effective way to decide if the language is finite?

I guess not, but how to prove this?

2

There are 2 best solutions below

2
On BEST ANSWER

To try to determine whether a language is finite, we have to have some information about the language. So, to make the problem precise, it's necessary to specify how that information will be provided. Perhaps the most typical way to pose this sort of question is the following:

Given a program $e$ for a Turing machine, is the language accepted by machine $e$ finite?

So we are asking whether that problem can be solved by a computable function:

Is there a computable function $f$ such that, given a program $e$ for a Turing machine, $f(e) = 1$ if the language accepted by machine $e$ finite, and $f(e) = 0$ otherwise?

The answer to that is "no". There is a general result, Rice's theorem, which applies. It shows that, when we ask questions like this one about the language accepted by a Turing machine (i.e. not questions about the machine itself), no nontrivial property of languages can be decided by a computable function that takes as input the machine $e$.

The general proof method is by reducing the halting problem to the question above. If we want to tell whether a particular Turing machine $e$ halts when started on an empty tape, we can make another Turing machine $e'$ which accepts a finite language if and only if $e$ halts. The function taking $e$ to $e'$ is computable. So if $f$ above was computable, we could solve the halting problem by taking input $e$ and asking whether $f(e') = 1$. That would let us solve the halting problem with a computable function, which is impossible. We conclude that $f$ is not computable, because the map taking $e$ to $e'$ is.

3
On

You can feed all words of the language to the second version Turing machine and it will halt for each word. If the whole run is finished in finite time, the given language was finite.

The question is how to do this practically. We can not start a TM with some maybe infinite language as input. We rather need to remove an element from the set and repeat until the set is exhausted. This needs removal and test for emptiness. Or remembering the enumerated words and a means of comparison.

In the other view one could let the enumerating TM list all words of the language and compare with the given language. If all words of the given language are listed within finite time, the given language is finite.

Again, how to do this in practice?