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:

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.


Add photos to your e-mail with MSN 8. Get 3 months FREE*.

Reply via email to