Universal Cumulatively Enumerable Measure (CEM)

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

$$C\mu(x) := \sum_{y \succeq x:~ l(y)=l(x)} \mu(y) + \sum_{y \succ x:~ l(y) < l(x)} \bar{\mu}(y).$$ (19)

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

$$\mu(x) = C\mu(x) ~if~x=11...1; ~~else~~ \mu(x) = C\mu(x) - C\mu(x').$$ (20)

Definition 4.5 (CEMs)   Semimeasure $\mu$ is a CEM if $C\mu(x)$ is enumerable for all $x \in B^*$.  

Then $\mu(x)$ 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 $B^{\sharp}$. 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 $x \in B^*$. 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.

FOR all i DO in dovetail fashion:

START: let $V\mu_i(x)$ and $V\bar{\mu}_i(x)$ and $VC\mu_i(x)$ denote variable functions on B^*. Set $V\mu_i(\lambda):= V\bar{\mu}_i(\lambda) := VC\mu_i(\lambda):= 1$, and $V\mu_i(x):= V\bar{\mu}_i(x) := VC\mu_i(x):= 0$ for all other $x \in B^*$. Define $VC\mu_i(x') := 0$ for undefined x'. Let z denote a string variable.

FOR $n = 1, 2, \ldots$ DO:

(1) Lexicographically order and rename all x with $l(x) \leq n$:

$x^1 := \lambda \prec x^2 := 0 \prec x^3 \prec \ldots \prec x^{2^{n+1}-1} := \underbrace {11...1}_n$.

(2) FOR k = 2ⁿ⁺¹-1 down to 1 DO:

(2.1) Systematically search for the smallest $m \geq n$ such that $z :=EOM_i(x^k,m) \neq \lambda$ AND $0.z \geq VC\mu_i(x^{k+1})$ if k <2ⁿ⁺¹-1; set $VC\mu_i(x^k) := 0.z$.

(3) For all $x \succ \lambda$ satisfying $l(x) \leq n$, set $V\mu_i(x) := VC\mu_i(x) - VC\mu_i(x')$. For all x with l(x) < n, set $V\bar{\mu}_i(x) := V\mu_i(x) - V\mu_i(x1) - V\mu_i(x0)$. For all x with l(x) = n, set $V\bar{\mu}_i(x) := V\mu_i(x)$.

If EOM_i indeed represents a CEM $\mu_i$ then each search process in (2.1) will terminate, and the $VC\mu_i(x)$ will enumerate the $C\mu_i(x)$ from below, and the $V\mu_i(x)$ and $V\bar{\mu}_i(x)$ will approximate the true $\mu_i(x)$ and $\bar{\mu}_i(x)$, respectively, not necessarily from below though. Otherwise there will be a nonterminating search at some point, leaving $V\mu_i$ from the previous loop as a trivial CEM. Hence we can enumerate all CEMs, and only those. Now define (compare [#!Levin:73a!#]):

$$\mu_0(x) = \sum_{n>0} \alpha_n \mu_n(x), ~~ \bar{\mu}_0(x) = ... ...bar{\mu}_n(x), ~~ ~where~ \alpha_n > 0,~ \sum_n \alpha_n = 1,$$

and $\alpha_n$ is an enumerable constant, e.g., $\alpha_n = \frac{6}{\pi n^2}$ or $\alpha_n = \frac{1}{n(n+1)}$ (note a slight difference to Levin's classic approach which just requests $\sum_n \alpha_n \leq 1$). Then $\mu_0$ dominates every $\mu_n$ by Def. 18, and is a semimeasure according to Def. 4.1:

$$\mu_0(\lambda) = 1;~ \mu_0(x) \geq 0;~ \mu_0(x) = \sum_{n>0... ...1) + \bar{\mu}_n(x)] = \mu_0(x0) + \mu_0(x1) + \bar{\mu}_0(x).$$ (21)

$\mu_0$ also is a CEM by Def. 4.5, because

$$C\mu_0(x) = \sum_{y \succeq x:~l(x)=l(y)} ~~ \sum_{n>0} \alp... ...y \succ x:~l(x)>l(y)} ~~ \sum_{n>0} \alpha_n \bar{\mu}_n(y) =$$

$$\sum_{n>0} \alpha_n \left( \sum_{y \succeq x:~l(x)=l(y)} \mu... ...l(y)} \bar{\mu}_n(y) \right) = \sum_{n>0} \alpha_n C\mu_n(x)$$ (22)

is enumerable, since $\alpha_n$ and $C\mu_n(x)$ are (dovetail over all n). That is, $\mu_0(x)$ is approximable as the difference of two enumerable finite values, according to Equation (20). $\Box$

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