Kolmogorov Complexity and Algorithmic Randomness

Choose a computable prefix-free self-delimiting coding $e\mapsto ⟨e⟩$ and define $U(⟨e⟩p)=M_e(p)$; malformed inputs diverge. Prefix-freeness makes the split into $⟨e⟩$ and $p$ unique, so this is partial computable.

For a fixed $M=M_e$, every $M$-description $p$ becomes a $U$-description of length $\mathrm{\mid }p\mathrm{\mid }+\mathrm{\mid }⟨e⟩\mathrm{\mid }$, so $U$ is optimal by Optimal description machines. Applying this twice to two optimal machines gives the additive-constant comparison.

There are ${\sum }_{i<n-c}{2}^i=2^{n-c}-1$ programs shorter than $n-c$, and each has at most one output under Description machines and plain Kolmogorov complexity.

Therefore no more strings can have such a description; division by $2^n$ in the uniform finite probability space Finite probability spaces, outcome weights, events, and event probabilities gives the bound.

Suppose for contradiction that $C_U$ is computable. For each $n$, search lexicographically among strings of length $n$ for the first $x_n$ with $C_U(x_n)\ge n$; such an $x_n$ exists because fewer than $2^n$ programs have length below $n$.

The search makes $n\mapsto x_n$ computable, so a fixed description machine maps a self-delimiting encoding of $n$ to $x_n$ using $O(\log n)$ bits. Optimality Optimal description machines transfers this to $C_U(x_n)\le O(\log n)$, contradicting $C_U(x_n)\ge n$ for large $n$.

The conditional machine $D(p,y)=U(p)$ ignores its condition. Conditional optimality therefore gives $C(x\mid y)\le C(x)+O(1)$.

Let $p$ be a shortest $U$-description of $x$ and $q$ a shortest $V$-description of $y$ conditional on $x$. Self-delimit $\mathrm{\mid }p\mathrm{\mid }$ and $\mathrm{\mid }q\mathrm{\mid }$ and concatenate the two programs. A fixed plain description machine recovers $x=U(p)$, then $y=V(q,x)$, and outputs $⟨x,y⟩$. Its description length is $\mathrm{\mid }p\mathrm{\mid }+\mathrm{\mid }q\mathrm{\mid }+O(\log (\mathrm{\mid }p\mathrm{\mid }+2)+\log (\mathrm{\mid }q\mathrm{\mid }+2))\mathrm{.}$ Optimality of $U$, supplied by Invariance theorem for plain Kolmogorov complexity, transfers this bound to $C(x,y)$ and proves the second inequality.

At depth $N$, a word $p$ excludes exactly $2^{N-\mathrm{\mid }p\mathrm{\mid }}$ leaves; prefix-freeness makes these excluded sets disjoint. Divide their total by $2^N$ and let $N$ grow to obtain the inequality.

For requests, assign the leftmost currently available node of the requested depth. The Kraft bound says fewer than all leaves are occupied, so induction never gets stuck and keeps the allocated set prefix-free, as required by Prefix-free machines and prefix complexity.

Dovetail the computations of $M_e$ on all inputs. Whenever a convergence $M_e(p)=x$ first appears, retain it only if $p$ is prefix-comparable with no previously retained input for that same $e$. The retained graph defines a partial computable machine ${\widehat{M}}_e$ with prefix-free domain. If $M_e$ already has prefix-free domain, no convergence is discarded, so ${\widehat{M}}_e=M_e$.

Choose a computable prefix-free self-delimiting code $a_e$ (for example $1^{e}0$) and set $U(a_{e}p)={\widehat{M}}_e(p)$. The universal simulation supplied by Universal and acceptable numberings, together with the effective filter in step 1.1, makes $U$ partial computable.

Distinct $a_e$ are prefix-free and each ${\widehat{M}}_e$ has prefix-free domain, so the domain of $U$ is prefix-free. For every prefix-free machine $M=M_e$, step 1.1 gives ${\widehat{M}}_e=M_e$, and therefore $K_U(x)\le K_M(x)+\mathrm{\mid }{a}_e\mathrm{\mid }$. Thus $U$ is optimal by Prefix-free machines and prefix complexity.

The concatenation construction in Basic conditional-complexity inequalities, with $x$ and $y$ exchanged, gives $C(x,y)\le C(y)+C(x\mid y)+O(\log (C(x)+2)+\log (C(y)+2))\mathrm{.}$

Put $a=C(x,y)$ and enumerate the finite set $A=\{(u,v):C(u,v)\le a\}$ by dovetailing all programs of length at most $a$; it has fewer than $2^{a+1}$ elements. Let $A_y=\{u:(u,y)\in A\}$ and $b=\lfloor {\log }_2\mathrm{\mid }{A}_y\mathrm{\mid }\rfloor$. Given $y,a,b$, the ordinal of $x$ in the enumeration of $A_y$ is a conditional description, so $C(x\mid y)\le b+O(\log (a+2))\mathrm{.}$ The set of $v$ whose fibre has at least $2^b$ elements is computably enumerable from $a,b$ and has fewer than $2^{a+1-b}$ members. The ordinal of $y$ in that enumeration gives $C(y)\le a-b+O(\log (a+2))\mathrm{.}$ Both decoder bounds transfer to the fixed machines by conditional optimality and Invariance theorem for plain Kolmogorov complexity. Adding them yields $C(x\mid y)+C(y)\le C(x,y)+O(\log (C(x,y)+2))$.

The elementary upper bounds on pair complexity make $\log (C(x,y)+2)$ no larger than the displayed logarithmic order. Combining steps 1.1 and 1.2 proves the equality. Applying it after swapping $x,y$ proves the stated symmetry.

Decode the outputs of the $e$-th partial computable function as pairs $(k,\sigma )$, discarding malformed outputs. This enumerates a c.e. relation $W_e\subseteq \mathbb{N}\times \{0,1{\}}^{\ast }$, and every c.e. relation occurs for some $e$ because Universal and acceptable numberings enumerates all partial computable functions. Hence the relations $W_e$ enumerate every uniformly effectively open candidate sequence.

For candidate $e$, at component $k$ retain a newly enumerated cylinder only when the finite union retained so far would still have measure at most $2^{-k}$. The measure of a finite cylinder union is computable by reducing its strings to a finite prefix-free set. Thus the retained relation is uniformly c.e. and always obeys the component bound. If the candidate already is a Martin-Löf test, no cylinder is ever discarded, since every finite subunion has measure at most the final measure.

Let $V_n$ be the union of all retained $e$-components at level $n+e+1$. Dovetailing the enumerations makes $(V_n)$ uniformly effectively open, and subadditivity gives $\mu (V_n)\le {\sum }_e{2}^{-(n+e+1)}=2^{-n}\mathrm{.}$ It is therefore a test by Martin-Löf tests and random sequences. If $(U_k^e)$ is a genuine test, step 2.1 does not trim it, so $U_{n+e+1}^e\subseteq V_n$ for all $n$. Take $c_e=e+1$ to obtain the stated universality.

For $k\ge 0$, let $V_k=\bigcup \{[\sigma ]:K(\sigma )<\mathrm{\mid }\sigma \mathrm{\mid }-k\}\mathrm{.}$ The sequence is uniformly effectively open: dovetail the fixed prefix machine and enumerate $\sigma$ at level $k$ when a description shorter than $\mathrm{\mid }\sigma \mathrm{\mid }-k$ appears. Choose one shortest program $p_{\sigma }$ for each such $\sigma$. These programs are distinct and belong to a prefix-free domain, so Kraft inequality and effective prefix-code allocation gives $\mu (V_k)\le {\sum }_{\sigma }{2}^{-\mathrm{\mid }\sigma \mathrm{\mid }}\le 2^{-k}{\sum }_{\sigma }{2}^{-\mathrm{\mid }{p}_{\sigma }\mathrm{\mid }}\le 2^{-k}\mathrm{.}$ Thus $(V_k)$ is a Martin-Löf test. If the deficiencies $n-K(X\upharpoonright n)$ are unbounded, then $X\in V_k$ for every $k$, so $X$ is not random.

Conversely, suppose $X$ fails a Martin-Löf test $(U_j)$. For each $k$, turn the enumeration of $U_{2k+2}$ into a computable disjoint cylinder cover: when a cylinder arrives, enumerate a finite prefix-free partition of the part not covered at earlier stages. For every resulting cylinder $[\sigma ]$, issue the request $(\sigma ,\mathrm{\mid }\sigma \mathrm{\mid }-k)$. Its length is nonnegative because one such cylinder already has measure at most $\mu (U_{2k+2})\le 2^{-2k-2}$, and the total request weight is ${\sum }_k{2}^k\mu (U_{2k+2})\le {\sum }_k{2}^{-k-2}\le 1.$ The effective allocation clause of Kraft inequality and effective prefix-code allocation therefore gives a prefix-free machine $M$ with $K_M(\sigma )\le \mathrm{\mid }\sigma \mathrm{\mid }-k$ for every request. Prefix optimality Invariance theorem for prefix complexity supplies a constant $d$ with $K(\sigma )\le \mathrm{\mid }\sigma \mathrm{\mid }-k+d$. Since $X\in U_{2k+2}$, for every $k$ one of the covering strings $\sigma \prec X$ gives deficiency at least $k-d$. Hence the prefix deficiencies of $X$ are unbounded.

Step 1.1 says bounded deficiency is necessary for randomness, while step 1.2 says nonrandomness forces unbounded deficiency. Taking contrapositives under Martin-Löf tests and random sequences proves the equivalence.

A successful martingale has $d(\epsilon )>0$, since a nonnegative martingale starting at $0$ is identically $0$. For each $n$, enumerate every string $\sigma$ with $d(\sigma )>2^{n}d(\epsilon )$ and let $U_n$ be the union of its cylinders. Strict comparison with a computable real is computably enumerable, so $U_n$ is effectively open.

The prefix-minimal threshold-crossing strings have the same union as $U_n$. The martingale conservation equation Computable martingales on binary strings bounds their total measure by $2^{-n}$ (their total capital cannot exceed initial capital), so $(U_n)$ is a Martin-Löf test.

Success puts the sequence in every level of that test, contradicting Martin-Löf randomness as defined in Martin-Löf tests and random sequences.

If an effective $s$-gale succeeds, its threshold prefix sets yield effective covers of $X$ with $s$-weight bounded; Kraft allocation Kraft inequality and effective prefix-code allocation assigns infinitely many prefixes descriptions of length at most $sn+O(\log n)$.

Conversely, infinitely many prefixes with $K(X\upharpoonright n)\le sn$ provide a c.e. Kraft-bounded request family; its allocated codes define an effective $s+\epsilon$-gale succeeding on $X$.

Taking infima over $s$ in the definition Effective Hausdorff dimension and letting $\epsilon \downarrow 0$ proves the equality; Invariance theorem for prefix complexity changes only $O(1)\mathrm{/}n$.

Choose a finite word $z$ with $C_U(z)>1$; such a word exists because there are infinitely many finite words but only three programs of length at most $1$. Define $V(0p)=U(p)$ and $V(1)=z$, undefined otherwise. Then $V$ is optimal because it simulates $U$ with one extra bit.

But $C_V(z)=1<C_U(z)$. The invariance theorem Invariance theorem for plain Kolmogorov complexity asserts only additive-constant agreement, so the absolute claim is false.

For each $n$, enumerate the single cylinder $[B\upharpoonright n]$ as $U_n$. Computability of $B$ makes $(U_n)$ uniformly effectively open and its measure is $2^{-n}$.

Thus $(U_n)$ is a Martin-Löf test and $B\in {\bigcap }_n{U}_n$, so $B$ is not Martin-Löf random by Martin-Löf tests and random sequences despite normality.