Universal TM-Induced Measures

Definition 4.16 (P-Induced Measure $mu P$)   Given a distribution $P$ on $B^{sharp}$, define a measure $mu P$ on $B^*$ as follows:

$$\mu P(x) = \sum_{z \in B^{\sharp}} P(xz).$$ (28)

Note that $overline{mu P}(x) = P(x)$ (compare Def. 4.1):

$$\mu P(\lambda) = 1;   \mu P(x) = P(x) + \mu P(x0) + \mu P(x1).$$ (29)

For those $x in B^*$ without 0-bit we have $mu P(x) = CP(x)$, for the others

$$\mu P(x) = CP(x) - CP(x').$$ (30)

Definition 4.17 (TM-Induced Semimeasures $mu_T,mu^M,mu^E,mu^G$)   Given some TM $T$, for $x in B^*$ define $mu_T(x) = mu P_T(x)$. Again we deviate a bit from Levin's $B^*$-oriented path [45] (survey: [30, p. 245 ff, p. 272 ff]) and extend $mu_T$ to $x in B^{infty}$, where we define $mu_T(x) = bar{mu}_T(x) = P_T(x)$. If $C$ denotes a set of TMs with universal element $U^C$, then we write

$$\mu^C(x) = \mu_{U^C}(x);    K\mu^C(x) := -lg \mu^C(x)  for  \mu^C(x)>0.$$ (31)

We observe that $mu^C$ is universal among all T-induced semimeasures, $T in C$. Note that

$$\mu^C(x) = \mu^C(x0) + \mu^C(x1) + P^C(x)  for x \in B^*;    \mu^C(x) = P^C(x)  for x \in B^{\infty}.$$ (32)

It will be obvious from the context when we deal with the restriction of $mu^C$ to $B^*$.

Corollary 4.2   For $x in B^*$, $mu^E(x)$ is a CEM and approximable as the difference of two c.e. values: $mu^E(x) = CP^E(x)$ for $x$ without any 0-bit, otherwise

$$\mu^E(x) = CP^E(x) - CP^E(x').$$ (33)