Re: on formally describable universes and measures

From: Wei Dai <weidai.domain.name.hidden>
Date: Thu, 21 Dec 2000 02:23:43 -0800

On Wed, Dec 20, 2000 at 04:32:47PM +0100, juergen.domain.name.hidden wrote:
> It's all in Section 6. Please read 6.1 to get the basic idea, read 6.2
> to understand why Levin Search and FAST are optimal. FAST computes the
> n-th bit of each universe x as quickly as the fastest algorithm for x
> (save for a constant factor). Your alternative does not.

I don't see how that can be true. If x is a random string, FAST will
compute it in 2^l(x) steps, whereas the fastest algorithm will compute it
in l(x) steps. If you have a more precise definition, please point me to
it because I couldn't find it in any of those sections.

> Just like the "infinitely accelerating computer" discussed here earlier.
> But you might have noticed that the paper does not assume the existence
> of TMs more powerful than general TMs (quantum physics does not require
> those). Duplicating forever leads to uncountable sets, which we reject
> for lack of evidence they are necessary to explain the world - they make
> the explanation much more complicated than necessary.

Unlike the infinitely accelerating computer, the duplicating computer
cannot solve the halting problem. It's no more powerful than general TMs,
only faster (and only faster for problems that can be solved in parallel).

If you don't like the duplicating computer, you would have to choose
between a classical TM and a quantum TM. The latter may be able to solve
some problems (for example factoring) exponentially faster. Choosing a
classical TM would lead to the conclusion that building a practical
quantum computer is impossible in our universe, so the choice has real
consequences, yet I don't see how you can make it on a priori grounds.
Received on Thu Dec 21 2000 - 02:26:05 PST