Ben Goertzel wrote:
>
>Jesse & Stephen:
>
>About quantum computing getting around the limitations of Turing machines:
>you don't have to cite Feynman, this matter was settled fairly clearly in
>David Deutsch's classic work on quantum computation. He showed that the
>only quantum-computable functions are Turing-computable functions. Quantum
>computers may be able to compute some things *faster* than classical
>computers (in the average case), but this is a different story.
>
>In his book Shadows of the Mind, Penrose reacts to this result with
>disappointment, and with an expression of hope that "quantum gravity
>computers" will be able to compute non-Turing-computable functions. But so
>far neither he nor anyone else has offered much more than hope and
>speculation in this direction. My own opinion is that this is probably a
>pipe dream, and we must make do with Turing-computable functions, but I'm
>of
>course open to new ideas and new information...
I had a science-fictional idea about a way to build an oracle machine after
reading Hans Moravec's article on "Time Travel and Computing" here:
http://www.frc.ri.cmu.edu/users/hpm/project.archive/general.articles/1991/TempComp.html
As I understood it, the basic idea here was to use the fact that history
must work out consistently to get a machine that could solve problems much
faster than a Turing machine. For example, for any problem that requires
exponential time to reach a solution but for which possible solutions can be
checked in polynomial time, you could have the machine pick a possible
solution at random, then check to see if the solution actually works, then
if it *doesn't* work it sends back a sort of override command that changes
the original guess, which would create an inconsistency. The only consistent
history in this case would be one where the machine's first guess happened
to be correct, so if history is indeed constrained to be consistent, you are
guaranteed to get the correct answer on the first guess.
Moravec says that although this would allow you to solve certain problems
faster than a classical computer or a traditional quantum computer, it would
not actually allow you to solve any uncomputable problems. But suppose we
combine the idea of time-travel computers with the idea that intelligent
life will find a way to increase the total amount of computing power
available without bound as time goes to infinity (as in Freeman Dyson's
proposal) or as time approaches the moment of the big crunch (as in Frank
Tipler's proposal). Then it seems you could use such a machine to solve the
halting problem--the machine could originally guess randomly whether to
display the output "does not halt" or "halts after n steps" (where n is any
whole number), and then you could run the computation indefinitely, and if
it ever does halt and the number of steps is different from the original
guess (or if it passes the number of steps in the original guess without
halting), the machine is programmed to send back a message which overrides
the original guess, which would create a contradiction. Thus, for history to
work out consistently, the original guess must have been the correct one.
It seems to me that one could use this idea of time-travel-computers in a
universe where computing power increases without bound not just to create
first-level oracle machines which tell you if the nth Turing machine halts
or not, but also arbitrary higher-level oracle machines which tell you if
the nth m-level oracle machine halts or not, where m is any countable
ordinal (Penrose discusses the notion of higher-level oracle machines in
'Shadows of the Mind'). I'm not sure if there are any conceivable types of
"machines" consisting of a finite set of well-defined operations that could
not be simulated in such a universe.
Jesse
_________________________________________________________________
Add photos to your e-mail with MSN 8. Get 3 months FREE*.
http://join.msn.com/?page=features/featuredemail&xAPID=42&PS=47575&PI=7324&DI=7474&SU=
http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_addphotos_3mf
Received on Mon Dec 30 2002 - 15:00:32 PST