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

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

Date: Mon, 15 Oct 2001 16:13:36 -0700

Saibal wrote:

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

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