# A Turing Machine that exclusively accepts an infinite string

While reading some of proofs in Computability Theory, I came up with following conclusion:

We can design a Turing Machine which exclusively accepts finite strings (obvious).

Now while trying the same for infinite string, I came up with the following conclusion :

There exist no Turing Machine which exclusively accepts infinite strings.

Proof : Since acceptance in context to Turing Machine is defined in terms of finite amount of time, therefore every time we say that an infinite string $w$ is accepted by a Turing Machine, we usually talk about searching a "finite pattern" in $w$. So while designing a machine for $w$ there exist a $w'$ which is finite and contains the same "finite pattern" which we try to find in $w$.

Example of "finite pattern" : A string that contains a 0. (Assuming Binary Strings)

So my question is that is my proof right? and if yes, is there a better way to prove this?

• The language of a TM is defined as a subset of $\Sigma^*$, which contains only finite words by definition. If you want to consider infinite words, you need to define a proper semantics for TMs over infinite words. There are such models, but you're probably better off starting with automata over infinite words, such as Büchi automata. – Shaull Aug 22 '16 at 20:21
• @Shaull Can you please share the source where language of a TM definition – Laschet Jain Aug 22 '16 at 20:48
• "We can design a Turing Machine which exclusively accepts finite strings (obvious)." How is that obvious? What does it even mean for a Turing machine to accept an infinite string? – David Richerby Aug 22 '16 at 21:44
• @LashitJain The definition of the language accepted by a Turing machine is completely standard and appears in any relevant textbook and on hundreds of web pages. – David Richerby Aug 22 '16 at 21:45
• Your proof is not very convincing. Saying we usually talk about searching a "finite pattern" doesn't constitute a formal argument. – Yuval Filmus Aug 22 '16 at 23:59

## 1 Answer

In contrast to the commenters, it is perfectly possible to define a Turing machine formalism whose input can be infinite. Let $\Sigma$ be an alphabet, and let $\#$ be a symbol not in $\Sigma$. We say that a Turing machine $T$ accepts a finite word $w \in \Sigma^*$ if it halts in an accepting state when the tape is initialized by $w \#^\omega$ (i.e., $w$ followed by infinitely many copies of $\#$; I assume for simplicity that the tape is only one-way infinite). Similarly, $T$ accepts an infinite word $w \in \Sigma^\omega$ if it halts in an accepting state when the tape is initialized by $w$.

We say that a language $L \subseteq \Sigma^* \cup \Sigma^\omega$ is $\omega$-computable (non-standard terminology) if there exists a Turing machine which halts on all inputs, and accepts exactly the strings in $L$. We say that $L$ is $\omega$-r.e. if there exists a Turing machine that accepts the strings in $L$, and never halts on strings not in $L$.

Under this definition, the language $\Sigma^*$ consisting of all finite words is not $\omega$-computable (as we show below), but is $\omega$-r.e. (exercise). It then follows that $\Sigma^\omega$ is not $\omega$-r.e., and in particular not $\omega$-computable (though we can show the latter directly).

Suppose that $T$ is a machine which halts on all inputs and accepts $\Sigma^*$. In particular, it halts on $\sigma^\omega$, where $\sigma \in \Sigma$ is arbitrary. Suppose that it halts after $N$ steps, at the rejecting state $s$. Then $T$ also halts on $\sigma^N$ (exercise), at the same state $s$, thus rejecting the finite word $\sigma^N$.

The same proof also shows directly that no Turing machine accepts $\sigma^\omega$.