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
