# 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. Aug 22, 2016 at 20:21
• @Shaull Can you please share the source where language of a TM definition Aug 22, 2016 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? Aug 22, 2016 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. Aug 22, 2016 at 21:45
• Your proof is not very convincing. Saying we usually talk about searching a "finite pattern" doesn't constitute a formal argument. Aug 22, 2016 at 23:59

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