3

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?

Community
  • 1
Michael Cloud
  • 141
  • 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 08 '14 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? – Michael Cloud Dec 08 '14 at 19:46
  • There is the concept of an infinite time Turing Machine: http://arxiv.org/pdf/math/9808093.pdf . And more here: http://mathoverflow.net/questions/121152/can-a-hamkins-infinite-time-turing-machine-with-infinite-super-turing-jumps-fro . Not at all my area of expertise, but I hope this helps some! :-) – ml0105 Dec 10 '14 at 01:54

3 Answers3

2

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

Denis
  • 6,945
  • 1
  • 21
  • 22
1

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.

The standard definition of a TM tape is unbounded, but finite. This means we can extend the output tape as much as needed but it is understood the tape is always finite. Assume a TM can write to every position of a countably infinite tape. For simplicity assume this TM starts with a blank tape and writes a '1' to each position in sequential order.

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.

There are definitions of Turing like machines that can perform an infinite number of operations. Turing invented oracle machines. This type of computation is often called hypercomputation. Many such machines use limits and have special rules on how the TM behaves at limit points. Any such theory has to assume the TM performs an infinite number of operations in a single step. No sequential machine that performs a finite number of operations at a time can ever process an infinite string.

Russell Easterly
  • 1,261
0

If infinite inputs are allowed but the Turing machines are finite, the question depends on the function. The exponential function can be computed given infinite time, but there are uncountably many real valued functions and only countably many machines, so some functions cannot be computed.

Matt Samuel
  • 58,164