Dominant and Universal (Semi)Measures

The next three definitions concerning semimeasures on B^* are almost but not quite identical to those of discrete semimeasures [#!LiVitanyi:97!#, p. 245 ff] and continuous semimeasures [#!LiVitanyi:97!#, p. 272 ff] based on the work of Levin and Zvonkin [#!Zvonkin:70!#].

Definition 4.1 (Semimeasures)   A (binary) semimeasure $\mu$ is a function $B^* \rightarrow [0,1]$ that satisfies:

$$\mu(\lambda) = 1;~~ \mu(x) \geq 0;~~ \mu(x) = \mu(x0) + \mu(x1) + \bar{\mu}(x),$$ (17)

where $\bar{\mu}$ is a function $B^* \rightarrow [0,1]$ satisfying $0 \leq \bar{\mu}(x) \leq \mu(x)$.

A notational difference to the approach of Levin [#!Zvonkin:70!#] (who writes $\mu(x) \leq \mu(x0) + \mu(x1)$) is the explicit introduction of $\bar{\mu}$. Compare the introduction of an undefined element u by Li and Vitanyi [#!LiVitanyi:97!#, p. 281]. Note that $\sum_{x \in B^*} \bar{\mu}(x) \leq 1$. Later we will discuss the interesting case $\bar{\mu}(x)=P(x)$, the a priori probability of x.

Definition 4.2 (Dominant Semimeasures)   A semimeasure $\mu_0$ dominates another semimeasure $\mu$ if there is a constant $c_{\mu}$ such that for all $x \in B^*$

$$\mu_0(x) > c_{\mu} \mu(x).$$ (18)

Definition 4.3 (Universal Semimeasures)   Let $\cal M$ be a set of semimeasures on B^*. A semimeasure $\mu_0 \in$ $\cal M$ is universal if it dominates all $\mu \in$ $\cal M$.

In what follows, we will introduce describable semimeasures dominating those considered in previous work ([#!Zvonkin:70!#], [#!LiVitanyi:97!#, p. 245 ff, p.272 ff]).

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