Approximable and Cumulatively Enumerable Distributions

To deal with infinite x, we will now extend the treatment of semimeasures on B^* in the previous subsection by discussing 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₀ 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).$$ (23)

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₀ dominates P.

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 enumerable and approximable universes on 2 August 2000 in Munich). It is an extension of a modified¹ proof [#!LiVitanyi:97!#, 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₀(x):=0; $I_n:=\{y:n^2\!\leq\!y\!<\!(n\!+\!1)^2\}$. Let n be such that $x\!\in\!I_n$. Define j_tⁿ (k_tⁿ) 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ⁿ), set Q_t(x)=Q_t-1(x). Otherwise set $Q_t(x)=n\!\cdot\!P_t(j_t^n)$ for x=j_tⁿ and Q_t(x)=0 for $x\neq j_t^n$. Q_t(x) is obviously total recursive and non-negative. Since $2n\!\leq\!\vert I_n\vert$, we have

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

Summing over n we observe that if P_t is a semidistribution, so is Q_t. From some t₀ 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)$. $\Box$

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

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

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