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 $Cmu$)   For semimeasure $mu$ on $B^*$ define the cumulative measure $Cmu$:

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

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').$$ (18)

Definition 4.5 (CEMs)   Semimeasure $mu$ is a CEM if $Cmu(x)$ is c.e. for all $x in B^*$.

Then $mu(x)$ 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 $B^*$ according to Def. 2.8. Such EOMs are c.e., and correspond to an effective enumeration of all c.e. 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 $Vmu_i(x)$ and $Vbar{mu}_i(x)$ and $VCmu_i(x)$ denote variable functions on $B^*$. Set $Vmu_i(lambda):= Vbar{mu}_i(lambda) := VCmu_i(lambda):= 1$, and $Vmu_i(x):= Vbar{mu}_i(x) := VCmu_i(x):= 0$ for all other $x in B^*$. Define $VCmu_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^{n+1}-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 VCmu_i(x^{k+1})$ if $k <2^{n+1}-1$; set $VCmu_i(x^k) := 0.z$.

(3) For all $x succ lambda$ satisfying $l(x) leq n$, set $Vmu_i(x) := VCmu_i(x) - VCmu_i(x')$. For all $x$ with $l(x) < n$, set $Vbar{mu}_i(x) := Vmu_i(x) - Vmu_i(x1) - Vmu_i(x0)$. For all $x$ with $l(x) = n$, set $Vbar{mu}_i(x) := Vmu_i(x)$.

If $EOM_i$ indeed represents a CEM $mu_i$ then each search process in (2.1) will terminate, and the $VCmu_i(x)$ will enumerate the $Cmu_i(x)$ from below, and the $Vmu_i(x)$ and $Vbar{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 $Vmu_i$ from the previous loop as a trivial CEM. Hence we can enumerate all CEMs, and only those. Now define (compare [28]):

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

and $alpha_n$ is a c.e. 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 approach which just requests $sum_n alpha_n leq 1$). Then $mu_0$ dominates every $mu_n$ by Def. 16, and is a semimeasure according to Def. 4.1: $mu_0(lambda) = 1$; $mu_0(x) geq 0$; and

$$\mu_0(x) = \sum_{n>0} \alpha_n [ \mu_n(x0) + \mu_n(x1) + \bar{\mu}_n(x)] = \mu_0(x0) + \mu_0(x1) + \bar{\mu}_0(x).$$ (19)

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

$$Cmu_0(x) = sum_{y succeq x: l(x)=l(y)}    sum_{n>0} alpha_n... ...sum_{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)} \m... ...l(y)} \bar{\mu}_n(y) \right) = \sum_{n>0} \alpha_n C\mu_n(x)$$ (20)

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