2
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Shaull Aug 22 '16 at 20:21
  • $\begingroup$ @Shaull Can you please share the source where language of a TM definition $\endgroup$ – Laschet Jain Aug 22 '16 at 20:48
  • 3
    $\begingroup$ "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? $\endgroup$ – David Richerby Aug 22 '16 at 21:44
  • 3
    $\begingroup$ @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. $\endgroup$ – David Richerby Aug 22 '16 at 21:45
  • $\begingroup$ Your proof is not very convincing. Saying we usually talk about searching a "finite pattern" doesn't constitute a formal argument. $\endgroup$ – Yuval Filmus Aug 22 '16 at 23:59
4
$\begingroup$

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

$\endgroup$

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.