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.
applies to all in dovetail fashion,
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 ,
are being updated by the algorithm of
keeps updating a chain of finitely many, variable, disjoint,
consecutive, adjacent, half-open intervals
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.