Next: Approximable and Cumulatively Enumerable Up: Measures and Probability Distributions Previous: Dominant and Universal (Semi)Measures

## A Novel Universal Cumulatively Enumerable Measure (CEM)

The traditional universal enumerable measure [40,45,29,16,17,41,14,30] studied in the theory of optimal inductive inference [40,41,24,23] reflects properties of a universal MTM with random input. In what follows we will simply replace the MTM by a more expressive EOM and obtain a nonenumerable measure that (1) dominates the traditional measure, (2) is just as computable'' in the limit as the traditional one, (3) is universal in its class. It will turn out though that this approach does not generalize to the case of GTMs. Some new definitions are in order.

Definition 4.4 (Cumulative measure )   For semimeasure on define the cumulative measure :
 (17)

Note that we could replace '' by '' in the definition above. Recall that denotes the smallest with ( may be undefined). We have
 (18)

Definition 4.5 (CEMs)   Semimeasure is a CEM if is c.e. for all .

Then is the difference of two finite c.e. values, according to (18).

Theorem 4.1   There is a universal CEM.

Proof. We first show that one can enumerate the CEMs, then construct a universal CEM from the enumeration. Check out the differences to Levin's proofs that there is a universal discrete semimeasure and a universal c.e. semimeasure [45,28], and Li and Vitányi's presentation of the latter [30, p. 273 ff], attributed to J. Tyszkiewicz.

Without loss of generality, consider only EOMs without halt instruction and with fixed input encoding of according to Def. 2.8. Such EOMs are c.e., and correspond to an effective enumeration of all c.e. functions from to . Let denote the -th EOM in the list, and let denote its output after instructions when applied to . The following procedure filters out those that already represent CEMs, and transforms the others into representations of CEMs, such that we obtain a way of generating all and only CEMs.

FOR all DO in dovetail fashion:

START: let and and denote variable functions on . Set , and for all other . Define for undefined . Let denote a string variable.

FOR DO:

(1) Lexicographically order and rename all with :

.

(2) FOR down to 1 DO:

(2.1) Systematically search for the smallest such that AND if ; set .

(3) For all satisfying , set . For all with , set . For all with , set .

If indeed represents a CEM then each search process in (2.1) will terminate, and the will enumerate the from below, and the and will approximate the true and , respectively, not necessarily from below though. Otherwise there will be a nonterminating search at some point, leaving from the previous loop as a trivial CEM. Hence we can enumerate all CEMs, and only those. Now define (compare [28]):

and is a c.e. constant, e.g., or (note a slight difference to Levin's approach which just requests ). Then dominates every by Def. 16, and is a semimeasure according to Def. 4.1: ; ; and
 (19)

also is a CEM by Def. 4.5, because

 (20)

is c.e., since and are (dovetail over all ). That is, is approximable as the difference of two c.e. finite values, according to Equation (18).

Next: Approximable and Cumulatively Enumerable Up: Measures and Probability Distributions Previous: Dominant and Universal (Semi)Measures
Juergen Schmidhuber 2003-02-13