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

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

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

## 1 Answer

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