next up previous
Next: Universal CEM vs EOM Up: Measures and Probability Distributions Previous: TM-Induced Distributions and Convergence

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:
\begin{displaymath}
\mu P(x) = \sum_{z \in B^{\sharp}} P(xz).
\end{displaymath} (28)

Note that $overline{mu P}(x) = P(x)$ (compare Def. 4.1):
\begin{displaymath}
\mu P(\lambda) = 1;   \mu P(x) = P(x) + \mu P(x0) + \mu P(x1).
\end{displaymath} (29)

For those $x in B^*$ without 0-bit we have $ mu P(x) = CP(x)$, for the others
\begin{displaymath}
\mu P(x) = CP(x) - CP(x').
\end{displaymath} (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
\begin{displaymath}
\mu^C(x) = \mu_{U^C}(x);   
K\mu^C(x) := -lg \mu^C(x)  for  \mu^C(x)>0.
\end{displaymath} (31)

We observe that $mu^C$ is universal among all T-induced semimeasures, $T in C$. Note that
\begin{displaymath}
\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}.
\end{displaymath} (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
\begin{displaymath}
\mu^E(x) = CP^E(x) - CP^E(x').
\end{displaymath} (33)


next up previous
Next: Universal CEM vs EOM Up: Measures and Probability Distributions Previous: TM-Induced Distributions and Convergence
Juergen Schmidhuber 2003-02-13