On 19 Mar 1999, Anders Sandberg wrote:
> Harnessing the Power of the Continuum: Asynchrony, Emergence, and
> Church's Thesis
> David F. Delchamps
> Nonlinear Science Today, 1995?
> http://www.springer-ny.com/nst/nstarticles.html
>
> A fun article exploring the consequences of having continous time. It
> turns out that this enables Turing machines to compute uncomputable
> numbers. The proof is rather simple: imagine two Turing machines, one
> with clock frequency 1 and the other with frequency tau, which is
> irrational. If the first is programmed to output n ones and then halt
> when given the input n, and the other is programmed to output n zeros
> and then halt. A third machine simply concatenates the outputs as they
> arrive, creating a composite stream of interleaved ones and zeros. It
> turns out that this little machine can compute uncomputable numbers
> simply by selecting the right tau. Neat. The rest of the paper is a
> bit more speculative, and I don't buy the author's idea that brains
> become powerful by being parallel and exploiting continous times (then
> our thinking would be highly sensitive to delays, which occur
> naturally in aging). But it is definitely a fun way of extending the
> TM.
The difficulty with this is the effects of noise -- any finite amount of noise will destroy the ability to compute "uncomputable" functions.
Another example is a hypothetical coin whose probability of coming up heads is Chaitin's omega, the number whose binary expansion simply enumerates the values of the hlating function. By repeatedly tossing such a coin we could determine the halting function. Nothing in the laws of nature precludes such a coin from existing. (It is easy to define quantum analogues of this, if you are worried about quantum effects). However, once again noise will prevent you from actually following the above procedure, even should such a coin magically come into your hands.
(On a related note, there are several interesting papers showing that analogue computational machines with exponential precision can solve NP-complete problems in polynomial time. Once again, noise destroys any hope of using such machines in any practical sense.)
Michael Nielsen