# Can a Turing Machine process an infinite string?

I read in a text book once that a finite state acceptor machine cannot be an acceptor for an infinite language.

My question is does this apply to Turing Machines? The implication, it seems to me, would be that no Turing Machine can ever solve something like exp(x) for all x in R, since the specification of a general x requires an infinite string.

Is this correct? And can anyone site a specific theorem?

The problem is that the text I remember was stating something somewhat narrow (acceptor machines), and not in the form of a theorem with proof, just an off hand assertion...

This question is clearly related to a previously posted question: infinitely long input for a turing machine

But I think is somewhat different. Certainly that answer doesn't address the issue. Having multiple tapes is just an artifice, anything you can do with two tapes you can do with one, just interleave them. This question is really about the number of states.

So let me restate the question a bit more narrowly: given a function f(x) from R to R (such as in particular exp(x), can a finite state Turing Machine provide the output for any input x in R, allowing infinite time?

• What does “a finite state acceptor machine cannot be an acceptor for an infinite language” mean exactly? As stated, it is obviously false, as the language ${\mathtt a }^*$ is infinite and is accepted by a one-state machine. Something must be missing.
– MJD
Dec 8, 2014 at 14:41
• I'll admit, I don't know. I read it in passing in a text I don't have anymore. I can change the question to the following: can a finite state Turing Machine compute the exact output of exp(x), or equivalently any power series on the reals, or does it have to stop at some finite approximation? Obviously we need to allow infinite time, but is that enough? Does the issue of finite state enter in? Dec 8, 2014 at 19:46
• There is the concept of an infinite time Turing Machine: arxiv.org/pdf/math/9808093.pdf . And more here: mathoverflow.net/questions/121152/… . Not at all my area of expertise, but I hope this helps some! :-) Dec 10, 2014 at 1:54

It makes sense to say that a Turing machine computes a function $\mathbb R\to\mathbb R$, like $\exp$.

This means that the machine will never stop, and on infinite input $x$ will write as output the decimals of $\exp(x)$ (in binary or any other base).

For instance the machine computing the identity function on $\mathbb R$ can just copy the input, but it will never stop. It is not hard to devise Turing machine that compute $x\mapsto 2x$ as well.

Whether a function is computable depends on your definition of computable. For example, the function exp(x) is normally considered computable because there is a TM that given some representation of a real number $x$ can output the representation of exp(x) to any desired finite number of positions. The answer to the question in the title is no. No normal TM can process an infinite string.
Define a family of sets, $A$, where each $a_i$ is the set of the blank positions on the tape after each step $i$. If the TM writes to every position on the infinite tape then some $a_z$ must be the empty set. This would mean $z$ is the largest natural number. There is no largest natural number proving the TM will never write to every position of an infinite tape. There will always be an infinite number of blank spaces on the infinite tape. Notice we made no assumptions about how fast the TM is or how long we waited. We only had to assume the TM could write to every position of an infinite tape sequentially.