From: Michael Nielsen (mnielsen@loquat.phys.unm.edu)
Date: Wed Jul 22 1998 - 19:06:55 MDT
yOn Wed, 22 Jul 1998, Robin Hanson wrote:
> Eugene asks Damien:
> > > magical SI through AI seems a bit incoherent; you exploit the
> > > Church-Turing thesis, then assume the result does something beyond
> > > Turing-completeness...
> >
> >I can't follow your reasoning here. Would you care to explain?
>
> Damien has an essay on the topic at:
> http://www.ugcs.caltech.edu/~phoenix/vinge/antising.html
Damien's essay makes much of the fact that all universal Turing machines
are equivalent, in the sense of the class of functions they may be used
to compute.
A simple objection to this argument is that different types of computer
may require very different physical resources to compute some class of
functions.
For example, a plausible though not watertight argument can be made that
quantum computers will be capable of solving problems involving quantum
simulation of a few humdred qubits that would require physical resources
exceeding those available in the observed Universe, if those resources
were exploited in a classical fashion. (Similar comments about factoring
and certain search problems can also be made).
For such classes of problems, I think it is fair to say that classical
computational devices, such as the brain, may be qualitatively weaker
than is allowed by physical Laws.
Damien concludes with:
"My very vague thesis: All undamaged human beings, and other sentiences,
share the same area of comprehensibility."
So my counterargument is that devices which exploit computational models
beyond the Turing model in terms of _efficiency_, such as quantum
computation is presumed to be, may be "incomprehensible" in the sense
that no classical computer, however large, constrained to run in our
Universe, could simulate the action of a modestly sized quantum
computer.
Michael Nielsen
http://wwwcas.phys.unm.edu/~mnielsen/index.html
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:49:23 MST