From: Smigrodzki, Rafal (SmigrodzkiR@msx.upmc.edu)
Date: Tue Apr 16 2002 - 21:31:53 MDT
A truly magical prospect. I wonder what would be the physical manifestation
of a solution to an unsolvable problem - would it open the way to actions
which at present seem to be forbidden by the known laws of physics? (this is
just a totally uninformed deliberation on my part).
Rafal
-----Original Message-----
From: scerir [mailto:scerir@libero.it]
Sent: Sunday, April 14, 2002 9:55 AM
To: extropians@extropy.org
Subject: 'tunneling' the Turing barrier
<<< Is there any hope for quantum computing to challenge
the Turing barrier, i.e. to solve an undecidable problem,
to compute an uncomputable function?
According to Feynman [1] the answer is negative.
This [-see below-] paper reopens the case:
We will discuss solutions to a few simple problems
which suggest that quantum computing is theoretically
capable of computing uncomputable functions.
The main features of our quantum 'device' are:
a special type of continuity, the choice of test-vectors
from a special class of trajectories of two Markov processes
working in two different scales of time and realized
as elements of an infinitely-dimensional Hilbert space
(infinite superposition), the ability to work with 'truly random'
test-vectors in an evolution described by an exponentially
growing semigroup and the possibility to obtain the result
from a single measurement.
In deciding the halting /non-halting status of a non-halting machine,
our 'device' is capable to 'announce'(with a positive probability)
the non-halting status in a ?nite amount of time, well before the
'real' machine reaches it (in an in ?nite amount of time).
Hence, the challenge was to design a procedure
that detects and measures this tiny, but non-zero probability.
In what follows a quantum solution is a solution designed
to work on a quantum computer.
The discussion is mathematical and no engineering claims will be made;
in particular, when speaking about various quantum devices which
will be constructed, we will use quotes to emphasize
the mathematical nature of our constructs. >>>
Note that these authors also think that
'The results discussed in this paper <...> go beyond
the pure mathematical aspects; they might impose
the re-examination of the mind-machine issue.' [2]
'Coins,Quantum Measurements, and Turing's Barrier'
C.S.Calude, B.Pavlov
University of Auckland, New Zealand
Find this paper (rather technical at:
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl
[1] =
- R.P.Feynman. 'Simulating p 'hysics with computers',
International Journal of Theoretical Physics, 21 (1982),467-488.
- J.G.Hey (ed.). 'Feynman and Computation. Exploring the Limits
of Computers', Perseus Books, Reading, Mass.,1999.
[2] =
see, i.e. http://www.phil.canterbury.ac.nz/jack_copeland/publist.html
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 09:13:33 MST