Approximable and Cumulatively Enumerable Distributions

To deal with infinite $x$, we will now extend the treatment of semimeasures on $B^*$ to nontraditional probability distributions on $B^{sharp}$.

Definition 4.6 (Probabilities)   A probability distribution $P$ on $x in B^{sharp}$ satisfies

$$P(x) geq 0;   sum_{x} P(x) = 1.$$

Definition 4.7 (Semidistributions)   A semidistribution $P$ on $x in B^{sharp}$ satisfies

$$P(x) geq 0;   sum_{x} P(x) leq 1.$$

Definition 4.8 (Dominant Distributions)   A distribution $P_0$ dominates another distribution $P$ if there is a constant $c_P > 0$ such that for all $x in B^{sharp}$:

$$P_0(x) \geq c_P P(x).$$ (21)

Definition 4.9 (Universal Distributions)   Let $cal P$ be a set of probability distributions on $x in B^{sharp}$. A distribution $P_0 in$ $cal P$ is universal if for all $P in$ $cal P$: $P_0$ dominates $P$.

Unfortunately it turns out that the analogue of the universal CEM Theorem 4.1 for EOMs with random input does not hold for GTMs:

Theorem 4.2   There is no universal approximable semidistribution.

Proof. The following proof is due to M. Hutter (personal communications by email following a discussion of approximable universes on 2 August 2000 in Munich). It is an extension of a modified¹ proof [30, p. 249 ff] that there is no universal recursive semimeasure.

It suffices to focus on $x in B^*$. Identify strings with integers, and assume $P(x)$ is a universal approximable semidistribution. We construct an approximable semidistribution $Q(x)$ that is not dominated by $P(x)$, thus contradicting the assumption. Let $P_0(x), P_1(x), ldots$ be a sequence of recursive functions converging to $P(x)$. We recursively define a sequence $Q_0(x), Q_1(x), ldots$ converging to $Q(x)$. The basic idea is: each contribution to $Q$ is the sum of $n$ consecutive $P$ probabilities ($n$ increasing). Define $Q_0(x):=0$; $I_n:=\{y:n^2\!leq\!y\!<\!(n\!+\!1)^2\}$. Let $n$ be such that $x\!in\!I_n$. Define $j_t^n$ $(k_t^n)$ as the element with smallest $P_t$ (largest $Q_{t-1}$) probability in this interval, i.e., $j_t^n:=\mathop{\rm minarg}_{x\in I_n}P_t(x)$ $(k_t^n:=\mathop{\rm maxarg}_{x\in I_n}Q_{t-1}(x))$. If $n\!cdot\!P_t(k_t^n)$ is less than twice and $n\!cdot\!P_t(j_t^n)$ is more than half of $Q_{t-1}(k_t^n)$, set $Q_t(x)=Q_{t-1}(x)$. Otherwise set $Q_t(x)=n\!cdot\!P_t(j_t^n)$ for $x=j_t^n$ and $Q_t(x)=0$ for $xneq j_t^n$. $Q_t(x)$ is obviously total recursive and non-negative. Since $2n\!leq\!\vert I_n\vert$, we have

$$sum_{xin I_n}Q_t(x) leq 2n\!cdot\!P_t(j_t^n) = 2n\!cdot\!min_{xin I_n}P_t(x) leq sum_{xin I_n}P_t(x).$$

Summing over $n$ we observe that if $P_t$ is a semidistribution, so is $Q_t$. From some $t_0$ on, $P_t(x)$ changes by less than a factor of 2 since $P_t(x)$ converges to $P(x)\!>\!0$. Hence $Q_t(x)$ remains unchanged for $t\!geq\!t_0$ and converges to $Q(x):=Q_infty(x)=Q_{t_0}(x)$. But $Q(j_{t_0}^n)=Q_{t_0}(j_{t_0}^n)\geq n\!\cdot\!P_{t_0}(j_{t_0}^n) \geq{{\textstyle{1\over 2}}}n\!\cdot\!P(j_{t_0}^n)$, violating our universality assumption $P(x)geq c\!cdot\!Q(x)$.

Definition 4.10 (Cumulatively Enumerable Distributions - CEDs)   A distribution $P$ on $B^{sharp}$ is a CED if $CP(x)$ is c.e. for all $x in B^*$, where

$$CP(x) := \sum_{y \in B^{\sharp}: y \succeq x} P(y)$$ (22)