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

## Universal Cumulatively Enumerable Measure (CEM)

Definition 4.4 (Cumulative measure tex2html_wrap_inline$C$)   For semimeasure on B* define the cumulative measure :

 (19)

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

 (20)

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

Then is the difference of two finite enumerable values, according to (20).

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 differences to Levin's related proofs that there is a universal discrete semimeasure and a universal enumerable semimeasure [#!Zvonkin:70!#,#!Levin:73a!#], and Li and Vitányi's presentation of the latter [#!LiVitanyi:97!#, p. 273 ff], attributed to J. Tyszkiewicz.

Without loss of generality, consider only EOMs without halt instruction and with fixed input encoding of B* according to Def. 2.8. Such EOMs are enumerable, and correspond to an effective enumeration of all enumerable functions from B* to . Let EOMi denote the i-th EOM in the list, and let EOMi(x,n) denote its output after n instructions when applied to . The following procedure filters out those EOMi 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 i DO in dovetail fashion:

START: let and and denote variable functions on B*. Set , and for all other . Define for undefined x'. Let z denote a string variable.

FOR DO:

(1) Lexicographically order and rename all x with :

.

(2) FOR k = 2n+1-1 down to 1 DO:

(2.1) Systematically search for the smallest such that AND if k <2n+1-1; set .

(3) For all satisfying , set . For all x with l(x) < n, set . For all x with l(x) = n, set .

If EOMi 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 [#!Levin:73a!#]):

and is an enumerable constant, e.g., or (note a slight difference to Levin's classic approach which just requests ). Then dominates every by Def. 18, and is a semimeasure according to Def. 4.1:

 (21)

also is a CEM by Def. 4.5, because

 (22)

is enumerable, since and are (dovetail over all n). That is, is approximable as the difference of two enumerable finite values, according to Equation (20).

Next: Approximable and Cumulatively Enumerable Up: Measures and Probability Distributions Previous: Dominant and Universal (Semi)Measures
Juergen Schmidhuber
2001-01-09

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI