Next: Probability vs Descriptive Complexity Up: Measures and Probability Distributions Previous: Universal TM-Induced Measures

## Universal CEM vs EOM with Random Input

Corollary 4.3 and Lemma 4.2 below imply that and are essentially the same thing: randomly selecting the inputs of a universal EOM yields output prefixes whose probabilities are determined by the universal CEM.

Corollary 4.3   Let denote the universal CEM of Theorem 4.1. For ,

Lemma 4.2   For ,

Proof. In the enumeration of EOMs in the proof of Theorem 4.1, let be an EOM representing . We build an EOM such that . The rest follows from the Invariance Theorem (compare Proposition 3.1).

applies to all in dovetail fashion, and simultaneously simply reads randomly selected input bits forever. At a given time, let string variable denote 's input string read so far. Starting at the right end of the unit interval , as the are being updated by the algorithm of Theorem 4.1, keeps updating a chain of finitely many, variable, disjoint, consecutive, adjacent, half-open intervals of size in alphabetic order on , such that is to the right of if . After every variable update and each increase of , replaces its output by the of the with . Since neither nor the in the algorithm of Theorem 4.1 can decrease (that is, all interval boundaries can only shift left), 's output cannot either, and therefore is indeed EOM-computable. Obviously the following holds:

and

Summary. The traditional universal c.e. measure [40,45,29,16,17,41,14,30] derives from universal MTMs with random input. What is the nature of our novel generalization here? We simply replace the MTMs by EOMs. As shown above, this leads to universal cumulatively enumerable measures. In general these are not c.e. any more, but they are just as computable'' in the limit as the c.e. ones -- we gain power and generality without leaving the constructive realm and without giving up the concept of universality. The even more dominant approximable measures, however, lack universality.

Next: Probability vs Descriptive Complexity Up: Measures and Probability Distributions Previous: Universal TM-Induced Measures
Juergen Schmidhuber 2003-02-13