Universal TM-Induced Measures

Definition 4.16 (P-Induced Measure tex2html_wrap_inline$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).$$ (30)

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

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

Definition 4.17 (TM-Induced Semimeasures tex2html_wrap_inline$_T,^M,^E,^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 [#!Zvonkin:70!#] (survey: [#!LiVitanyi:97!#, 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.$$ (33)

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}.$$ (34)

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 enumerable values: $\mu^E(x) = CP^E(x)$ for x without any 0-bit, otherwise

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

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