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, maintain a finite prefix-free set $F$ of free tree nodes, initially $F=\{\epsilon \}$ for the empty word $\epsilon$. Require that its nodes have pairwise distinct lengths and that their cylinders are exactly the unallocated part of the binary tree. After finitely many requests, the total free capacity is ${\sum }_{\sigma \in F}{2}^{-\mathrm{\mid }\sigma \mathrm{\mid }}=1-{\sum }_{i\text{ already allocated}}{2}^{-n_i}$. For the next request of length $n$, this capacity is at least $2^{-n}$ by the bound on the entire request list. If every node of $F$ had length greater than $n$, distinctness of the lengths would make its capacity at most ${\sum }_{j>n}{2}^{-j}=2^{-n}$, with strict inequality because $F$ is finite. Therefore $F$ contains a node of length at most $n$. Choose the one $\sigma$ of greatest such length $m$; it is unique because the free-node lengths are distinct.

Remove $\sigma$ from $F$. Allocate the descendant $\sigma 0^{n-m}$ as the requested codeword, and insert the siblings $\sigma 0^{j}1$ for $0\le j<n-m$ into $F$. Their depths are $m+1,\dots ,n$; no existing free node has one of these depths, by maximality of $m$ among depths at most $n$. The new free nodes are prefix-free and partition exactly the part of $[\sigma ]$ outside the allocated cylinder, so both invariants and the capacity identity persist. Each step is a finite computable operation on the current finite set $F$. Processing the computable enumeration in order therefore gives distinct codewords of the requested lengths and a prefix-free effective allocation, including the empty-word case $n=0$.

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.

The collection in the supremum is nonempty because it contains $\mathrm{\varnothing }$, and all its values lie in $[0,1]$ by [F1], so the real supremum exists. Monotonicity follows by inclusion of the collections being supremized. The empty and whole-space values follow directly from $p_0(\mathrm{\varnothing })=0$ and $p_0(\mathrm{\Omega })=1$. If $C\subseteq [\sigma ]$ is clopen, [F1] gives $p_0(C)\le p_0([\sigma ])$; taking $C=[\sigma ]$ gives the reverse bound and proves the cylinder formula.

Let $U={\bigcup }_i{U}_i$, and fix $C\in \mathcal{C}$ with $C\subseteq U$. The family $\{\mathrm{\Omega }\setminus C\}\cup \{U_i:i\ge 0\}$ is an open cover of $\mathrm{\Omega }$. By [F2] finitely many $U_i$, indexed by a finite set $F$, cover $C$. Consider all prefix cylinders contained in at least one $U_i$ with $i\in F$; they cover $C$ because prefix cylinders form a base. Together with $\mathrm{\Omega }\setminus C$ they cover $\mathrm{\Omega }$, so compactness gives finitely many such cylinders covering $C$. Assign each selected cylinder to the least eligible $i\in F$, and let $C_i$ be the finite union of cylinders assigned to $i$. Then $C\subseteq {\bigcup }_{i\in F}{C}_i$ and $C_i\subseteq U_i$. By [F1], $p_0(C)\le {\sum }_{i\in F}{p}_0(C_i)\le {\sum }_{i\in F}{\mu }_o(U_i)\le {\sum }_{i\ge 0}{\mu }_o(U_i)$. Taking the supremum over $C$ proves countable subadditivity. No choice of a cylinder for each point was made; the finite selections came from the stated compactness conclusion.

If $U,V$ are disjoint and open, clopen $C_U\subseteq U$ and $C_V\subseteq V$ are disjoint, so [F1] gives $p_0(C_U)+p_0(C_V)=p_0(C_U\cup C_V)\le {\mu }_o(U\cup V)$. Taking the two suprema yields ${\mu }_o(U)+{\mu }_o(V)\le {\mu }_o(U\cup V)$; step 2.1 gives the reverse inequality. Induction yields finite additivity on pairwise disjoint opens. For a disjoint sequence, monotonicity then gives ${\mu }_o({\bigcup }_i{U}_i)\ge {\sum }_{i<k}{\mu }_o(U_i)$ for every $k$; take the supremum in $k$ and combine with step 2.1 to obtain equality.

Now assume countable choice and take the Borel measure $\mu$ of [F3]. Enumerate all prefix cylinders contained in an open $U$ in the canonical length-then-binary-value order, and let $C_k$ be the union of those among the first $k$ strings that are contained in $U$. Each $C_k$ belongs to $\mathcal{C}$, the sequence increases, and ${\bigcup }_k{C}_k=U$ by [F2]. Continuity from below of $\mu$ gives $\mu (U)={\sup }_k\mu (C_k)={\sup }_k{p}_0(C_k)\le {\mu }_o(U)$. Conversely, if $C\in \mathcal{C}$ lies in $U$, then the open cover $\{C_k:k\ge 0\}\cup \{\mathrm{\Omega }\setminus C\}$ of compact $\mathrm{\Omega }$ has a finite subcover. Since the $C_k$ increase, $C\subseteq C_k$ for some $k$. Thus $p_0(C)\le p_0(C_k)\le \mu (U)$, and taking the supremum proves ${\mu }_o(U)\le \mu (U)$.

Dovetail the universal evaluation of the $e$-th partial computable function over all natural inputs and running times. Decode any output as a pair $(k,\sigma )$ and discard malformed outputs. This uniformly enumerates a c.e. relation $W_e\subseteq \mathbb{N}\times \{0,1{\}}^{\ast }$ for each $e$. Conversely, an enumeration program for any c.e. relation appears in the numbering Universal and acceptable numberings, so the relations $W_e$ cover 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}$. Delete strings extending another string in the finite list; the remaining prefix-free cylinders are disjoint, so their rational measures $2^{-\mathrm{\mid }\sigma \mathrm{\mid }}$ sum to the exactly computable union measure. The retention rule is therefore uniform and c.e. Its finite retained unions have measure at most $2^{-k}$, and continuity from below Continuity from below for measures gives the same bound for their increasing union. If the candidate already is a Martin-Löf test, none of its cylinders is discarded, since every finite subunion is contained in its component of measure at most $2^{-k}$.

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 countable subadditivity Finite and countable subadditivity of measures 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$. Enumerate the pairs $(n,\sigma )$ satisfying $d(\sigma )>2^{n}d(\epsilon )$ and let $U_n$ be the union of the cylinders of strings enumerated with first coordinate $n$. Strict comparison of computable reals is semidecidable uniformly in $(n,\sigma )$, so one algorithm enumerates all these pairs and $(U_n)$ is uniformly effectively open.

The prefix-minimal threshold-crossing strings have the same union as $U_n$ and are prefix-free. For any finite set $S$ of them, the martingale conservation equation Computable martingales on binary strings gives ${\sum }_{\sigma \in S}{2}^{-\mathrm{\mid }\sigma \mathrm{\mid }}d(\sigma )\le d(\epsilon )$: extend the strings to one common length, where their descendant cylinders are disjoint. Since every $d(\sigma )>2^{n}d(\epsilon )$, it follows that ${\sum }_{\sigma \in S}{2}^{-\mathrm{\mid }\sigma \mathrm{\mid }}\le 2^{-n}$. Taking increasing finite subsets gives $\mu (U_n)\le 2^{-n}$, 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.

Let an effective $s$-gale $d$ succeed on $X$, and fix a rational $t>s$. For $n\ge 1$ enumerate $E_n=\{\sigma \in 2^n:d(\sigma )>1\}$, possible because $d$ is lower semicomputable. Iterating the gale identity gives ${\sum }_{\mathrm{\mid }\sigma \mathrm{\mid }=n}d(\sigma )=2^{sn}d(\mathrm{\varnothing })$, so $\mathrm{\mid }{E}_n\mathrm{\mid }<2^{sn}d(\mathrm{\varnothing })$. Choose an integer $c$ such that $\mathrm{\mid }{E}_n\mathrm{\mid }<2^{\lceil tn\rceil +c}$ for every $n$. Such a fixed $c$ exists since $t>s$ and $d(\mathrm{\varnothing })$ is finite (Effective Hausdorff dimension).

For the reverse inequality write $a={\mathrm{lim\hspace{0.17em}inf}}_{n}K(X\upharpoonright n)\mathrm{/}n$, which is finite since a self-delimiting code for $n$ followed by $n$ bits gives $K(X\upharpoonright n)\le n+O(\log n)$. Independently choose rationals $q,t$ with $a<q<t$. Let $U$ be the fixed optimal prefix-free machine. For each halted program $p$ with output $\sigma$, put mass $2^{-\mathrm{\mid }p\mathrm{\mid }}$ uniformly on the cylinder $[\sigma ]$: its value on a cylinder $[\tau ]$ is $2^{-\mathrm{\mid }p\mathrm{\mid }}$ if $\tau ⪯\sigma$, $2^{-\mathrm{\mid }p\mathrm{\mid }-\mathrm{\mid }\tau \mathrm{\mid }+\mathrm{\mid }\sigma \mathrm{\mid }}$ if $\sigma \prec \tau$, and $0$ if $\tau$ and $\sigma$ are incompatible. Denote the sum of these values over all halted $p$ by $\mu ([\tau ])$. Kraft's inequality (Kraft inequality and effective prefix-code allocation) gives $\mu ([\mathrm{\varnothing }])\le 1$; each summand is nonnegative and obeys ${\mu }_p([\tau ])={\mu }_p([\tau 0])+{\mu }_p([\tau 1])$, so the sum has the same identity.

Give $n$ a computable self-delimiting code of length $O(\log n)$, followed by a fixed-length $\lceil tn\rceil +c$-bit index into the enumeration of $E_n$. These codes form a prefix-free machine: the first code identifies $n$, and all following indices then have the same length. Its output on an index is the corresponding enumerated string when that index appears. Thus, by optimality of $K$ (Invariance theorem for prefix complexity), each $\sigma \in E_n$ has $K(\sigma )\le tn+O(\log n)$. Success of $d$ makes $d(X\upharpoonright n)>1$ at infinitely many, hence unboundedly many, lengths $n$. It follows that ${\mathrm{lim\hspace{0.17em}inf}}_{n}K(X\upharpoonright n)\mathrm{/}n\le t$. Since rational $t>s$ was arbitrary, the liminf is at most $s$, and therefore at most $\dim (X)$.

Set $d_t(\tau )=2^{t\mathrm{\mid }\tau \mathrm{\mid }}\mu ([\tau ])$. Because $t$ is rational and the halted computations can be enumerated, $d_t$ is lower semicomputable; the preceding identity makes it an effective $t$-gale (Effective Hausdorff dimension). At any $\sigma$ with a shortest program $p$, its contribution alone gives $d_t(\sigma )\ge 2^{t\mathrm{\mid }\sigma \mathrm{\mid }-K(\sigma )}$ (Prefix-free machines and prefix complexity). There are infinitely many lengths $n$ with $K(X\upharpoonright n)<qn$ by the definition of the liminf. On them $d_t(X\upharpoonright n)>2^{(t-q)n}$, which tends to infinity. Thus $d_t$ succeeds and $\dim (X)\le t$. Letting rational $t$ decrease to $a$ completes the equality.

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.