Plausibility of Cumulatively Enumerable Priors

The semimeasure $\mu^M$ used in the traditional theory of inductive inference is dominated by the nonenumerable yet approximable $\mu^E$ (Def. 4.17) assigning approximable probabilities to initial segments of strings computable on EOMs.

As Chaitin points out [#!Chaitin:87!#], enumerable objects such as the halting probabilities of TMs are already expressive enough to express anything provable by finite proofs, given a set of mathematical axioms. In particular, knowledge of $\Omega^T_{n}$, the first n bits of the halting probability of TM T, conveys all information necessary to decide by a halting program whether any given statement of an axiomatic system describable by fewer than n-O(1) bits is provable or not within the system.

$\Omega^T_{n}$ is effectively random in the sense of Martin-Löf [#!Martin-Loef:66!#]. Therefore it is generally undistinguishable from noise by a recursive function of n, and thus very compact in a certain sense -- in fact, all effectively random reals are Omegas, as recently shown by Slaman [#!Slaman:99!#] building on work by Solovay [#!Solovay:75!#]; see also [#!Calude:00!#,#!Solovay:00!#]. One could still say, however, that $\Omega$ decompresses mathematical truth at least enough to make it retrievable by a halting program. Assuming that this type of mathematical truth contains everything relevant for a theory of all reasonable universes, and assuming that the describable yet even ``more random'' patterns of Theorem 3.3 are not necessary for such a theory, we may indeed limit ourselves to the enumerable universes.

If Conjecture 5.2 were true, then we would have P^E(x) = O(2^-KE(x)) (compare Equation (1)), or P^E(xy) = O(2^-KE(xy)) (compare (15)). That is, the most likely continuation y would essentially be the one corresponding to the shortest algorithm, and no cumulatively enumerable distribution could assign higher probability than O(2^-KE(xy)) to xy. Maximizing P^E(xy) would be equivalent to minimizing K^E(xy).

Since the upper bound given by Theorem 5.3 is not quite as sharp due to the additional, at most logarithmic term, we cannot make quite as strong a statement. Still, Theorem 5.3 does tell us that P^E(xy) goes to zero with growing K^E(xy) almost exponentially fast, and Theorem 5.6 says that $\mu^E(xy_k)$ (k fix) goes to zero with growing Km^E(xy_k) almost exponentially fast.

Hence, the relatively mild assumption that the probability distribution from which our universe is drawn is cumulatively enumerable provides a theoretical justification of the prediction that the most likely continuations of our universes are computable by short EOM algorithms. However, given P^E, Occam's razor (e.g., [#!Blumer:87!#]) is only partially justified because the sum of the probabilities of the most complex xy does not vanish:

$$lim_{n \rightarrow \infty} \sum_{xy \in B^{\sharp}: K^E(xy)>n}P^E(xy) > 0.$$

To see this, compare Def. 4.12 and the subsequent paragraph on program continua. There would be a nonvanishing chance for an observer to end up in one of the maximally complex universes compatible with his existence, although only universes with finite descriptions have nonvanishing individual probability.

We will conclude this subsection by addressing the issue of falsifiability. If P^E or $\mu^E$ were responsible for the pseudorandom aspects of our universe (compare Example 2.1), then this might indeed be effectively undetectable in principle, because some approximable and enumerable patterns cannot be proven to be nonrandom in recursively bounded time. Therefore the results above may be of interest mainly from a philosophical point of view, not from a practical one: yes, universes computable by short EOM algorithms are much more likely indeed, but even if we inhabit one then we may not be able to find its short algorithm.

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI