Approximable and Cumulatively Enumerable Distributions
Next: TM-Induced Distributions and Convergence Up: Measures and Probability Distributions Previous: Universal Cumulatively Enumerable Measure

## Approximable and Cumulatively Enumerable Distributions

To deal with infinite x, we will now extend the treatment of semimeasures on B* in the previous subsection by discussing probability distributions on .

Definition 4.6 (Probabilities)   A probability distribution P on satisfies

Definition 4.7 (Semidistributions)   A semidistribution P on satisfies

Definition 4.8 (Dominant Distributions)   A distribution P0 dominates another distribution P if there is a constant cP > 0 such that for all :

 (23)

Definition 4.9 (Universal Distributions)   Let be a set of probability distributions on . A distribution is universal if for all : P0 dominates P.

Theorem 4.2   There is no universal approximable semidistribution.

Proof. The following proof is due to M. Hutter (personal communications by email following a discussion of enumerable and approximable universes on 2 August 2000 in Munich). It is an extension of a modified1 proof [#!LiVitanyi:97!#, p. 249 ff] that there is no universal recursive semimeasure.

It suffices to focus on . Identify strings with integers, and assume P(x) is a universal approximable semidistribution. We construct an approximable semidistribution Q(x) that is not dominated by P(x), thus contradicting the assumption. Let be a sequence of recursive functions converging to P(x). We recursively define a sequence converging to Q(x). The basic idea is: each contribution to Q is the sum of n consecutive P probabilities (n increasing). Define Q0(x):=0; . Let n be such that . Define jtn (ktn) as the element with smallest Pt (largest Qt-1) probability in this interval, i.e., . If is less than twice and is more than half of Qt-1(ktn), set Qt(x)=Qt-1(x). Otherwise set for x=jtn and Qt(x)=0 for . Qt(x) is obviously total recursive and non-negative. Since , we have

Summing over n we observe that if Pt is a semidistribution, so is Qt. From some t0 on, Pt(x) changes by less than a factor of 2 since Pt(x) converges to . Hence Qt(x) remains unchanged for and converges to . But , violating our universality assumption .

Definition 4.10 (Cumulatively Enumerable Distributions - CEDs)   A distribution P on is a CED if CP(x) is enumerable for all , where

 (24)

Next: TM-Induced Distributions and Convergence Up: Measures and Probability Distributions Previous: Universal Cumulatively Enumerable Measure
Juergen Schmidhuber
2001-01-09

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