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.
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:
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.