TM-Induced Distributions and Convergence Probability

Suppose TM $T$'s input bits are obtained by tossing an unbiased coin whenever a new one is requested. Levin's universal discrete enumerable semimeasure [28,14,16] or semidistribution $m$ is limited to $B^*$ and halting programs:

Definition 4.11 (m)  

$$m(x) = \sum_{p: T(p)=x} 2^{-l(p)};$$ (23)

Note that $sum_x m(x) < 1$ if $T$ universal. We will now generalize this in obvious but nontraditional ways to $B^{sharp}$ and nonhalting programs for MTMs, EOMs, and GTMs.

Definition 4.12 ($P_T, KP_T$)   Suppose $T$'s input bits are obtained by tossing an unbiased coin whenever a new one is requested.

$$P_T(x) = \sum_{p: T(p) \leadsto x} 2^{-l(p)},   KP_T(x) = -lg P_T(x) for P_T(x)>0,$$ (24)

where $x, p in B^{sharp}$.

Program Continua. According to Def. 4.12, most infinite $x$ have zero probability, but not those with finite programs, such as the dyadic expansion of $0.5 sqrt{2}$. However, a nonvanishing part of the entire unit of probability mass is contributed by continua of mostly incompressible strings, such as those with cumulative probability $2^{-l(q)}$ computed by the following class of uncountably many infinite programs with a common finite prefix $q$: ``repeat forever: read and print next input bit.'' The corresponding traditional measure-oriented notation for

$$sum_{x: T(qx) leadsto x} 2^{-l(qx)} = 2^{-l(q)}$$

would be

$$int_{0.q}^{0.q + 2^{-l(q)}} dx = 2^{-l(q)}.$$

For notational simplicity, however, we will continue using the $sum$ sign to indicate summation over uncountable objects, rather than using a measure-oriented notation for probability densities. The reader should not worry about this -- the theorems in the remainder of the paper will focus on those $x in B^{sharp}$ with $P(x)>0$; density-like nonzero sums over uncountably many bitstrings, each with individual measure zero, will not play any critical role in the proofs.

Definition 4.13 (Universal TM-Induced Distributions $P^C;KP^C$)   If $C$ denotes a set of TMs with universal element $U^C$, then we write

$$P^C(x) = P_{U^C}(x);    KP^C(x) := -lg P^C(x)  for  P^C(x)>0.$$ (25)

We have $P^C(x) > 0$ for $D_C subset B^{sharp}$, the subset of C-describable $x in B^{sharp}$. The attribute universal is justified, because of the dominance $P_T(x) = O(P^C(x))$, due to the Invariance Theorem (compare Proposition 3.1).

Since all programs of EOMs and MTMs converge, $P^E$ and $P^M$ are proper probability distributions on $B^{sharp}$. For instance, $sum_x P^E(x) = 1$. $P^G$, however, is just a semidistribution. To obtain a proper probability distribution $PN_T$, one might think of normalizing by the convergence probability $Upsilon$:

Definition 4.14 (Convergence Probability)   Given GTM T, define

$$PN_T(x) = frac{sum_{T(p) leadsto x} 2^{-l(p)}} {Upsilon^T},$$

where

$$Upsilon^T = sum_{p: exists x: T(p) leadsto x} 2^{-l(p)}.$$

$Upsilon^T$ not describable. Uniquely encode each TM $T$ as a finite bitstring, and identify $M,E,G$ with the corresponding sets of bitstrings. While the function $f^M: M rightarrow B^{sharp}: f(T) = Omega^T$ is c.e., the function $f^G: G rightarrow B^{sharp}: f(T) = Upsilon^T$ is not even describable, essentially due to Theorem 2.1.

Even $P^E(x)$ and $P^M(x)$ are generally not describable for $x in B^{sharp}$, in the sense that there is no GTM $T$ that takes as an input a finite description (or program) of any M-describable or E-describable $x in B^{sharp}$ and converges towards $P^M(x)$ or $P^E(x)$. This is because in general it is not even weakly decidable (Def. 2.11) whether two programs compute the same output. If we know that one of the program outputs is finite, however, then the conditions of weak decidability are fulfilled. Hence certain TM-induced distributions on $B^*$ are describable, as will be seen next.

Definition 4.15 (TM-Induced Cumulative Distributions)   If $C$ denotes a set of TMs with universal element $U^C$, then we write (compare Def. 4.10):

$$CP^C(x) = CP_{U^C}(x).$$ (26)

Lemma 4.1   For $x in B^*$, $CP^E(x)$ is c.e.

Proof. The following algorithm computes $CP^E(x)$ (compare proof of Theorem 3.3):

Initialize the real-valued variable $V$ by 0, run all possible programs of EOM $T$ dovetail style; whenever the output of a program prefix $q$ starts with some $y succeq x$ for the first time, set $V:= V+ 2^{-l(q)}$; henceforth ignore continuations of $q$.

In this way $V$ enumerates $CP^E(x)$. Infinite $p$ are not problematic as only a finite prefix of $p$ must be read to establish $y succeq x$ if the latter indeed holds.

Similarly, facts of the form $y succ x in B^*$ can be discovered after finite time.

Corollary 4.1   For $x in B^*$, $P^E(x)$ is approximable or describable as the difference of two c.e. values:

$$P^E(x) = \sum_{y \succeq x} P^E(y) - \sum_{y \succ x} P^E(y),$$ (27)

Now we will make the connection to the previous subsection on semimeasures on $B^*$.