Dominant and Universal (Semi)Measures

Traditionally, the algorithmic probability of $x in B^*$ is defined as the probability of producing $x$ by a halting program for a universal TM whose input bits are selected randomly. Since some of the possible input sequences cause nonhalting computations, the individual probabilities do not add up to 1. This and related issues inspired work on semimeasures [40,45,41,17,30] as opposed to classical measures considered in traditional statistics.

The next three definitions concerning semimeasures on $B^*$ are almost but not quite identical to those of discrete semimeasures [30, p. 245 ff] and continuous semimeasures [30, p. 272 ff] based on the work of Levin and Zvonkin [45].

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),$$ (15)

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 [45] (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 [30, 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).$$ (16)

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 novel, nonenumerable but describable semimeasures dominating the c.e. ones considered in previous work [45][30, p. 245 ff, p.272 ff].