(19) |

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

**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 *EOM*_{i} denote the *i*-th EOM in the list, and let
*EOM*_{i}(*x*,*n*) denote its output
after *n* instructions when applied to .
The following procedure filters out those *EOM*_{i} that already represent
CEMs, and transforms the others into representations
of CEMs, such that we obtain a way of generating all and only CEMs.

If

FORalliDOin dovetail fashion:

START:let and and denote variable functions onB^{*}. Set , and for all other . Define for undefinedx'. Letzdenote a string variable.

FORDO:

(1)Lexicographically order and rename allxwith :.

(2)FORk= 2^{n+1}-1 down to 1DO:

(2.1)Systematically search for the smallest such thatANDifk<2^{n+1}-1; set .

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

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

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