I am confused about Turing Machines that are able to decide languages that contain infinite words.

  1. Are languages with an infinite amount of only finite strings always decidable?

  2. How can a Turing Machine halt on an infinite input string?

  3. Can Turing Machines loop on finite strings?

  4. What is the difference between an infinite input string that a Turing Machines can halt on and an infinite input string that a Turing Machine cannot halt on (decidable vs recognizable)?

It's a lot of questions but they are related, please help me.

  • 1
    $\begingroup$ I have never heard of Turing machines operating on infinite words. Can you supply a reference? $\endgroup$ Aug 10 '19 at 7:24
  • $\begingroup$ The example question I got was: Give a high level description of a Turing Machine that decides the language L = {w | count(a) == 2 * count(b)}. A regular expression may be infinite as well, for example a*. Given that it is a regular expression it is also a decidable language, however I don't quite understand how a Turing Machine can actually decide on such a language. $\endgroup$
    – BHK
    Aug 10 '19 at 8:56
  • $\begingroup$ Your language consists of finite words. The regular expression $a^*$ denotes a language of finite words. $\endgroup$ Aug 10 '19 at 9:05
  • $\begingroup$ @YuvalFilmus yes, but it could also contain a word consisting of infinite a's $\endgroup$
    – BHK
    Aug 10 '19 at 10:37
  • 2
    $\begingroup$ No it couldn’t. By definition, a language only contains finite words. $\endgroup$ Aug 10 '19 at 15:31

There's is a significant difference between "arbitrarily long" and "infinite".

As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \notin \mathbb{N}$.)

Similarly, the Kleene star operator $A^*$ represents the concatenation of an arbitrarily large number of elements from $A$, but not an infinite number of elements of $A$.

There is an interesting part of formal language theory which deals with sets of infinitely-long strings (ω-strings), but such strings cannot be produced by any regular expression. (You can use ω-regular expressions, which include the infinite repetition operator $A^\omega$.) But you might want to master the material you're currently studying before venturing onto Buchi automata, interesting though they may be.

To answer your questions:

  1. No, there are undecidable languages consisting only of finite strings. Indeed, since such languages are undecidable, it is not necessarily even decidable whether they are finite sets. A classic example of an undecidable language is the set of (descriptions of) Turing machines which halt on every input. Note that every Turing machine (like every integer) has a finitely-long description, so the language is a set (an infinite set, in this case) of finite strings.

  2. A Turing machine is under no obligation to read its entire input. Consider the language of ω-strings which start with an $a$. This is clearly a set of infinitely-long strings, but only a single character needs to be examined to determine whether a string belongs to the language.

  3. Sure, why not. For example, the Turing machine trying to determine whether its input describes a Turing machine which halts on every input could simulate the described machine using every possible input, but that is going to go on forever even if the language describe a Turing machine which always halts.

  4. See, for example, deterministic Buchi automata. Basically, an ω-language $L$ can be deterministic if there is a language $L' \subset Pref(L)$ of finite prefixes which can deterministically predict inclusion in $L$.


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.