Re: on formally describable universes and measures

From: <juergen.domain.name.hidden>
Date: Wed, 27 Dec 2000 16:50:42 +0100

>> 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.

Please see section 6. The finite (short) random strings are absorbed
by the O() notation. The infinite random strings (without finite
description), however, can neither individually nor collectively be
computed in countable time (section 6.3) and are not even formally
describable (Defs 2.2 and 2.5). Let p^x be the fastest finite program
for a (possibly infinite) string x. FAST computes x as quickly as p^x,
save for a constant factor (see Levin's results summarized in section
6.2). If this sounds surprising, check out algorithm SIMPLE in section
6.1, which also computes x as quickly as p^x, save for a constant factor.
(Actually I already used SIMPLE in the 1997 paper on the computable
universes, without thinking much about its fundamental advantages over
the very inefficient alphabetic listings of all bitstrings discussed here
earlier - compare algorithm ALPHABET, section 6.1). SIMPLE's constant
factor tends to be worse than FAST's though (section 6.2). A good
overview is in the 1997 edition of Li and Vitanyi's book on page 503 ff.

>> 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).

It is so much faster that it is more powerful - it can do uncountably
many things in countable time. My credo is: don't assume something
like that if you don't really need it to explain the observations.

>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.

None of the quantum effects we observe forces us to give up the simple
idea that our universe can be simulated on a classic TM, just like
there is no evidence that forces us to assume the existence of complex
and incomputable things such as uncountable sets.

Juergen Schmidhuber
Received on Wed Dec 27 2000 - 07:57:27 PST