Re: on formally describable universes and measures

From: <juergen.domain.name.hidden>
Date: Tue, 19 Dec 2000 15:18:14 +0100

Thanks for the additional comments.

> You haven't addressed the issue of why it makes sense that S assigns about
> 2^(-2n) to random strings instead of 2^-n. If a prior does assign about
> 2^-n to random strings, then it does not predict that a pseudorandom
> number generator is driving the apparent randomness that we observe.
> This is because although each individual non-pseudorandom universe has very
> small probability, there are a lot more of them, and these two factors
> cancel out.

I see what you mean - that's in section 7.2 on enumerable universes,
which says: "Occam's razor is not fully justified because the sum of the
probabilities of the most complex x does not vanish. There would be a
nonvanishing chance for an observer to end up in one of the maximally
complex universes compatible with his existence, although only universes
with finite descriptions have nonvanishing individual probability."
Of course, all we can say here is that mu(x) cannot be much larger than
2^-KmG(x) (Theorem 5.5); muE(x) cannot be much larger than 2^-KmE(x)
(Theorem 5.6).

> To see this, consider a program prefix X that implements the
> laws of our universe and reads the rest of the input tape to obtain any
> bits needed to drive random occurances, and compare it with a program
> prefix Y that implements the laws of our universe but treats the rest of
> the tape as a pseudorandom number generator program to obtain these
> "random" bits. It's reasonable to assume that X is a little shorter than
> Y. Under the speed prior S, the set of programs that begin with X
> contributes less to the measure than the set of programs that begin with
> Y. But the reverse is true under any of the other priors mentioned in your
> paper.
> Let me reemphasize that each new bit of information should cost a factor
> of 2, not 4. The latter leads to the counterintuitive conclusion that any
> apparent randomness in the universe is actually the output of a
> pseudorandom number generator, which implies for example that it's
> theoretically possible to compute the entire history of the universe from
> the information obtained from a single tea leave.


The tea leave stuff does not necessarily follow. But apart from this, you
are actually touching the root of the reasoning behind the speed prior. I
am cutting and pasting a bit from section 7.4: Any source of randomness
leaves us with an unsatisfactory explanation of the universe, since random
strings do not have a compact explanation, by definition. The obvious
way around this is the ``ensemble approach'' where we run all possible
TM input programs and sum over the lengths of those that compute strings
starting with $x$. Once we deal with explicit computations, however, we
are forced to accept their fundamental time constraints. Many of the
shortest programs of certain enumerable or describable strings compute
their outputs more slowly than any recursive upper bound could indicate.

The speed prior is based on the most efficient way of computing
all individually computable universes (note that the infinite random
universes you mentioned are not computable at all, neither individually
nor collectively by the ensemble approach) plus an additional natural
resource-oriented postulate: the cumulative prior probability of all
$x$ incomputable within time $t$ by this optimal algorithm should be
$1/t$. In particular, anything that consumes uncountable resources
even when we use the fastest way of computing everything has measure
zero. Note that the pure description size-based priors ignore time to
the extent that their computation does require uncountable resources,
a notion rejected by the speed prior S.

Everything else (your comments on the discounting of random strings)
is just a consequence.

Juergen Schmidhuber
Received on Tue Dec 19 2000 - 06:20:07 PST