# What is an example of a Turing-recognizable infinite word, which is not Turing-decidable?

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)?

• I have never heard of Turing machines operating on infinite words. Can you supply a reference? Aug 10, 2019 at 7:24
• 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.
– BHK
Aug 10, 2019 at 8:56
• Your language consists of finite words. The regular expression $a^*$ denotes a language of finite words. Aug 10, 2019 at 9:05
• @YuvalFilmus yes, but it could also contain a word consisting of infinite a's
– BHK
Aug 10, 2019 at 10:37
• No it couldn’t. By definition, a language only contains finite words. Aug 10, 2019 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.

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