2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Any hints what "effective" and "decides" mean here, or how the r.e. language is provided to the TM? $\endgroup$
    – mvw
    Nov 23, 2016 at 13:36

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The question has two points that puzzle me. The first one is what is meant by "effective" (is this more than just in finite steps and with finite memory?) and what is meant by "decides" - does the recognition involve only the true case, meaning the TM halts for a finite r.e. language but has unspecified behaviour otherwise. Your argument seems to hinge on the requirement that the false case can be recognized as well. $\endgroup$
    – mvw
    Nov 23, 2016 at 13:34
  • $\begingroup$ "effective" is just a synonym for "computable". "Decide" in the context of computability theory means to give a correct yes or no answer to every instance of a problem. These are standard terms, so it is not surprising use them in the question without definition. $\endgroup$
    – Carl Mummert
    Nov 23, 2016 at 14:15
-1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ In general we will not be able to tell when the machine has listed all the words of the language... $\endgroup$
    – Carl Mummert
    Nov 23, 2016 at 13:09
  • $\begingroup$ And in your first paragraph you assume decidability, but I assumed just recursive enumerability, which means that the TMR might run forever on some inputs, so the algorithm you proposed there might not work on recursive enumerable sets. $\endgroup$
    – StefanH
    Nov 23, 2016 at 14:20
  • $\begingroup$ I changed the wording. The point is that the Turing machine will always halt by its definition, it gets only words from its $L$. $\endgroup$
    – mvw
    Nov 23, 2016 at 14:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .