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

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

Date: Wed, 27 Dec 2000 16:50:42 +0100

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.

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.

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

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