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?
Best Answer
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.
This Wikipedia page goes more into the details: http://en.wikipedia.org/wiki/Computable_real_function