[This post contributes nothing new.]
Consider the sequence of bits observed by a camera situated within the physical universe (which we can imagine as a CA for concreteness). If we draw a program uniformly at random (i.e., fixing a universal prefix free encoding) and condition on agreement with this prefix, what does the posterior (over programs) look like?
If the CA is deterministic and regular, then the observations have a (relatively) short description, given by writing down the initial conditions and rules and specifying how to extract the observation sequence from the world history (e.g., read off values from this cell, or watch for a particular pattern which appears near this coordinate, perhaps tracking physical continuity, or etc.) If the sequence is sufficiently unsurprising (for example, nearly constant) then it will have a very short description; otherwise, it will be specified by describing the entire universe and locating the observer within it.
If the CA is randomized, there is no short description. Pointing to an observation within the universe is intractable, as it involves specifying an amount of randomness which grows with the age and extent of the universe. Similarly, having pointed to the observation, specifying the continuing evolution of the universe requires too much randomness to be useful. So what should we believe about the shortest description of observations in a random universe?
Averaging over all sequences of observations within the universe, the best predictor is the one who is a given the description of the universe and a specification of how to locate observations within that universe, and which uses its initial observations to condition the resulting distribution (where the distribution depends on the averaging used to determine optimality). Therefore there is a short description which specifies the correct probability distribution over next observations. The fact that much randomness is used in the actual description is relevant only insofar as we may suspect that the observations alone are not adequate to determine the universe–it is now more likely that a sequence won’t contain enough surprises to rule out simpler models.
Returning to our universe, consider a human’s sequence of observations. Even fixing the laws of physics, all you can conclude from your observations is that you belong to the reference class of observers who have shared your experiences (and your cognitive architecture etc.)