Computable Universal Prior

Ronny Fernandez

Suppose instead of using 2^-K(H) we just use 2^-length(H), does this do something obviously stupid?

Here's what I'm proposing:

Take a programing language with two characters. Assign each program a prior of 2^-length(program). If the program outputs some string, then P(string | program) = 1, else it equals 0. I figure there must be some reason people don't do this already, or else there's a bunch of people doing it. I'd be real happy to find out about either.

Clearly, it isn't a probability distribution, but we can still use it, no?

Suppose instead of using 2^-K(H) we just use 2^-length(H), does this do something obviously stupid?

Here's what I'm proposing:

Clearly, it isn't a probability distribution, but we can still use it, no?

If you want a computable universal prior, forget about turing machines, because the halting problem will always get you in the end.

One option is to just say that the probability of observing a sequence of bits is equal to 2^-L. This is the maximum entropy prior, which is perfectly easy to compute. It's also useless, because it doesn't have any starting information. It's a prior without any "prior." The Solomonoff prior (which you outlined) is useful at predicting computable sequences, but at the cost of making many overconfident mistakes when the sequence is not computable / infinitely K-complex.

If you want a computable prior that's still useful, one approach might be to think of sequence-generating methods that 1) appear in the real world and 2) don't have the halting problem (maybe look into finite state machines, eh?), and then make a prior that is useful for predicting those sequences, at the cost of making overconfident mistakes when the sequence is of infinite "complexity" in that class.