Re: The Singularity

Michael Nielsen (mnielsen@loquat.phys.unm.edu)
Wed, 22 Jul 1998 19:06:55 -0600 (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