Re: Predictions & duplications

From: <hal.domain.name.hidden>
Date: Mon, 15 Oct 2001 16:13:36 -0700

Saibal wrote:
> Hal Finney wrote:
> > Juergen Schmidhuber writes:
> > > But there is no uniform prior over all programs!
> > > Just like there is no uniform prior over the integers.
> > > To see this, just try to write one down.
> >
> > I think there is. Given a program of length l, the prior probability
> > is 2^(-l). (That is 2 to the power of negative l.) The length of a
> > program is defined by interpreting it using self-delimiting rules as
> > is customary in the AIT analysis of Greg Chaitin.
>
> This doesn't seem to be very uniform to me. Maybe you mean that with the
> above prior the probability for a bit, drawn randomly from the set of all
> programs, to be 1 is 1/2 ?

I should have used the proper name for this, the universal prior.

However it is derived in the limit (of string length -> infinity)
by giving the same probability to all strings, and then adopting the
convention that we ignore the material past the end of a self-delimiting
program.

As we go to the limit, if we are looking at n bit strings, then a self
delimiting program of length l will have 2^(n-l) instances among the
2^n possible strings, hence will have measure 2^(-l), which is the
universal prior. So the universal prior on self-delimiting programs
is the same as the uniform prior on all program strings, as we take the
limit in program string length going to infinity.

Hal
Received on Mon Oct 15 2001 - 16:25:22 PDT