Can languages with infinite strings be recursively enumerable?

Problem Detail: 

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but it does not have to halt on different inputs.

But suppose I have a language consisting of uncountable size with words of infinite length. Will Turing machine halt with a word of infinite length?

Consider a language constisting of all binary strings (I can produce such a set by diagonalization - Cantors rule, for example). Is this language recursively enumarable? If so, can you tell me why? I have not found any definition of this that would explain the behavior of TM with such inputs...

Asked By : Smajl

Answered By : babou

I agree with FrankW's answer regarding semi-decidability, though his answer is based mostly on an example. But I am not sure he answers your question, or that he answers with sufficient precision.

The problem is that your question is ambiguous. You use, and even emphasize in boldface, the expression recursively enumerable, but you give the definition that seems more intended for semi-decidability. I realize that it is weell known and easy to show that these two concepts are equivalent when considering languages that are sets of finite strings, and we do not usually distinguish them.

However these concepts were originally defined only for finite strings, or natural numbers, which amount more or less to the same. Basic computability theory assumes finiteness (the use of Gödel numbers requires finiteness of description, for example). I know there is work on automata for infinite strings, though I am not familiar with it.

If you consider languages with infinite words, concepts such as recursively enumerable or semi-decidable are no longer equivalent. The former means that there is a Turing Machine (TM) that can enumerate all the words of the language. The latter (also called recognizable) means that there is a TM that will halt in an accepting state when given a word of the language, and will reject or loop otherwise.

The concepts can extend to languages with infinite strings. However, as shown by FrankW's answer, a semi-decision procedure requires that words in the language be recongnizable by considering only a finite prefix. In other words, such a language $L$ with infinite words is semi-decidable iff it is of the form $L=M\cup N\Sigma^\infty$ where $\Sigma$ is the alphabet, $\Sigma^\infty$ is the set of infinite strings over $\Sigma$, and both $M$ and $N$ are semi-decidable sets of finite strings. The set of all infinite binary strings conforms this definition. As remarked by Shaull's comment, it is recognized by any TM that simply accepts without looking at the string. There are some subtler details about being sure of the alphabet, but that is minor.

You also have to define precisely what it means to enumerate an infinite set of infinite strings, but that can be done.

In the finite case, a recursively enumerable language is semi-decidable. The semi-decision procedure is simple, given a word $w$, you enumerate the words in the language and compare them to $w$. If there is equality, the word $w$ is accepted, else you keep enumerating.

In the case of infinite words this no longer works, very simply because checking equality of two infinite words takes infinite time. Of course, any infinite word that we may want to consider has to be computable. Hence it can be finitely represented by a TM, or a Gödel number. But this is no help. I think the TM enumerating the infinite strings in the language can be transformed into a TM that enumerate finite descriptions (Gödel numbers) of TM that just produce each one of these strings. Similarly, the infinite word $w$ that we try ro recognize can be finitely represented by a description of a TM that produces it. So now everything is finite, and we should be OK, except for the fact that checking whether two TM produce the same (finite or infinite) string is undecidable.

Basically, the problem is that infinity makes you lose the equality test, so that recursive enumerability no longer implies semi-decidability. However, semi-decidability still implies recursive enumerability, pretty much as in the finite case, but I would not care to give here a detailed construction for it.

While the structure of semi-decidable languages of infinite strings is limited to $L=M\cup N\Sigma^\infty$, as shown above, recursively enumerable languages of infinite strings can be much richer and complex.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29930