Next: TM-Induced Distributions and Convergence Up: Measures and Probability Distributions Previous: A Novel Universal Cumulatively

## Approximable and Cumulatively Enumerable Distributions

To deal with infinite , we will now extend the treatment of semimeasures on to nontraditional probability distributions on .

Definition 4.6 (Probabilities)   A probability distribution on satisfies

Definition 4.7 (Semidistributions)   A semidistribution on satisfies

Definition 4.8 (Dominant Distributions)   A distribution dominates another distribution if there is a constant such that for all :
 (21)

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

Unfortunately it turns out that the analogue of the universal CEM Theorem 4.1 for EOMs with random input does not hold for GTMs:

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 approximable universes on 2 August 2000 in Munich). It is an extension of a modified1 proof [30, p. 249 ff] that there is no universal recursive semimeasure.

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

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

Definition 4.10 (Cumulatively Enumerable Distributions - CEDs)   A distribution on is a CED if is c.e. for all , where
 (22)

Next: TM-Induced Distributions and Convergence Up: Measures and Probability Distributions Previous: A Novel Universal Cumulatively
Juergen Schmidhuber 2003-02-13