0
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ The standard definition of TMs refers to words of finite length. If you want to move to words of infinite length, it is not clear what it means for a word to be accepted. In automata, for example, you can define acceptance conditions such as B\"uchi acceptance, but I don't think this is where your question is going. As for the language of all binary strings, specifically, it's recognizable (and decidable) by a machine that immediately accepts (assuming the alphabet is binary). $\endgroup$ – Shaull Sep 12 '14 at 8:21
  • $\begingroup$ So in conclusion it IS recursively enumarable language since it will be recognized and accepted no matter what time it will take. $\endgroup$ – Smajl Sep 12 '14 at 8:23
  • $\begingroup$ If you define properly what it means for a TM to work with infinite words, then this specific case will be RE, yes. $\endgroup$ – Shaull Sep 12 '14 at 9:07
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

As you state, the standard definition of TM acceptance requires that the TM halts after finite time.

It is still possible for a TM to accept languages that contain infinite words, if they can accept without reading the entire word. For example the language of all (finite and infinite) words that contain at least one $0$ is semi-decidable, since if there is a $0$, the TM will encounter it after a finite amount of time and can then accept the word.
The complement of this language however is not semi-decidable, since it is not possible to read an infinite input in finite time (and it is not possible, in the general case, to know that there is no $0$, without reading the whole input).

$\endgroup$
  • $\begingroup$ Thanks for the clarification. The task I had to do, was to find a language which is not recursively enumarable and its complement is also not recursively enumarable. I wanted to use this language as this example but I am not sure if can do that... $\endgroup$ – Smajl Sep 12 '14 at 11:18
  • $\begingroup$ Unless that task is from a course/book section, that explicitly deals with infinite words, I'm pretty sure you are supposed to find an example that only uses finite words. $\endgroup$ – FrankW Sep 12 '14 at 11:26

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.