Turing Compliant?

[Bryan VanDeVen]

Gordon McMillan wrote:
> 
> Jim Hefferon wrote:
> 
> [snip]
> 
> > Somebody else in this thread mentioned quantum computation.  I've
> > tried to read up on it, but I'm afraid I didn't get it.  Is it the
> > case that anything quantum computable is Turing computable, that is,
> > quantum computability may go faster but doesn't add anything
> > actually new?

No.  Quantum computing basically gives you the "nondeterministic"
element that would allow problems that are NP to actually be solved in
polynomial time. (By my understanding) Quantum parallelism would overome
the exponential nature of these hard problems. There is an intersting
article about quantum computing and some of the practical obstacles
facing its realization in the June 1999 issue of APS Physics Today. 

> Well there's biological computation, in which each fork() grows it's
> own "CPU", thus making some formerly non-computable problems
> computable.

I have heard of some experiments with biological computing - most taking
advantange of the much higher information density that can be achieved
using DNA, for instance, but I am very skeptical of the claim that this
adds something fundamentally new.  Any pointers to a proof? 


-- 
Bryan Van de Ven
Applied Research Labs
University of Texas, Austin