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 ?

##
Advertising

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