- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Jesse Mazer <lasermazer.domain.name.hidden>

Date: Mon, 30 Dec 2002 14:57:05 -0500

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

Date: Mon, 30 Dec 2002 14:57:05 -0500

Ben Goertzel wrote:

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

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*