Levin--Schnorr characterization of Martin-Löf randomness

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.