From: Michael Nielsen (mnielsen@theory.caltech.edu)
Date: Fri Mar 19 1999 - 15:09:59 MST
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
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:03:21 MST