The KC theorem and the coding theorem

Enumerate $R$ as $(\sigma_0, \ell_0), (\sigma_1, \ell_1), \dots$, one request per stage (if $R$ is finite, the construction stops). We assign to the request $(\sigma_s, \ell_s)$ a string $\tau_s$ of length $\ell_s$, and set $M(\tau_s) = \sigma_s$. Along the construction we maintain a finite set $F_s$ of free strings, with the following invariants:

1. the strings $\tau_0, \dots, \tau_{s-1}$ and the elements of $F_s$ form a prefix-free set, the $\tau_i$ being pairwise distinct;
2. the elements of $F_s$ have pairwise distinct lengths;
3. $\sum_{\rho \in F_s} 2^{-|\rho|} = 1 - \sum_{i < s} 2^{-\ell_i}$.

Initially $F_0 = \{ \varepsilon \}$ and no string is assigned; the invariants hold.

At stage $s$, the weight of $R$ gives $2^{-\ell_s} \leq 1 - \sum_{i < s} 2^{-\ell_i} = \sum_{\rho \in F_s} 2^{-|\rho|}$. Some free string has length at most $\ell_s$: otherwise, by invariant 2, the free strings have distinct lengths larger than $\ell_s$, and their weight is less than $\sum_{j > \ell_s} 2^{-j} = 2^{-\ell_s}$. Let $\rho$ be the longest free string with $|\rho| \leq \ell_s$, and $k = \ell_s - |\rho|$. Let $\tau_s = \rho\, 0^{k}$, and

The new free strings have the lengths $|\rho| + 1, \dots, \ell_s$; no element of $F_s$ had one of these lengths, by the choice of $\rho$, so invariant 2 is preserved. The strings $\tau_s$ and $\rho\, 0^j 1$, $j < k$, are pairwise incomparable extensions of $\rho$, and $\rho$ was incomparable with the other strings of invariant 1; so invariant 1 is preserved. Finally $2^{-|\rho|} = 2^{-\ell_s} + \sum_{j < k} 2^{-(|\rho| + j + 1)}$, so invariant 3 is preserved.

The construction is effective, so $M$ is a machine; its domain $\{ \tau_s \}$ is prefix-free by invariant 1, and it satisfies $R$. The construction is uniform in an index of $R$. The bound on $K$ follows from optimality: $K \leq K_M + c_M$.

Let $(f_s)$ be an approximation from above. Enumerate the request $(\sigma, f_0(\sigma) + 1)$ for each $\sigma$, and the request $(\sigma, f_{s+1}(\sigma) + 1)$ whenever $f_{s+1}(\sigma) < f_s(\sigma)$. The requests concerning $\sigma$ have pairwise distinct lengths $v + 1$, with $v$ ranging over the values taken by $f_s(\sigma)$, which are at least $f(\sigma)$. Their weight is at most $\sum_{v \geq f(\sigma)} 2^{-v-1} = 2^{-f(\sigma)}$. The total weight is at most $\sum_\sigma 2^{-f(\sigma)} \leq 1$. By Theorem 4.2, $K(\sigma) \leq^+ f(\sigma) + 1$, since the request $(\sigma, f(\sigma) + 1)$ is enumerated when the approximation reaches its limit.

Let $P_{M,s}(\sigma)$ be the sum over the descriptions $\tau$ of $\sigma$ such that $|\tau| \leq s$ and $M(\tau)[s]\converge$; it is computable, non-decreasing in $s$, with limit $P_M(\sigma)$. For each $k \geq 1$ and $\sigma$, enumerate the request $(\sigma, k + 1)$ when $P_{M,s}(\sigma) > 2^{-k}$ for the first time. Fix $\sigma$ with $P_M(\sigma) > 0$, and let $k_0$ be the least $k$ with $P_M(\sigma) > 2^{-k}$; then $k_0 \geq 1$, since $P_M(\sigma) \leq 1$. The requests about $\sigma$ are those with $k \geq k_0$, of total weight $\sum_{k \geq k_0} 2^{-k-1} = 2^{-k_0} < P_M(\sigma)$. So the request set is bounded by $\sum_\sigma P_M(\sigma) \leq 1$. By Theorem 4.2, $K(\sigma) \leq^+ k_0 + 1$. By minimality of $k_0$, $P_M(\sigma) \leq 2^{-(k_0 - 1)}$, so $k_0 \leq 1 - \log P_M(\sigma)$, and $K(\sigma) \leq^+ -\log P_M(\sigma)$.

Let $M$ be the prefix-free machine $\tau \mapsto |U(\tau)|$, with the domain of $U$. Then $P_M(n) = \sum_{|\sigma| = n} P_U(\sigma) \geq \sum_{|\sigma| = n} 2^{-K(\sigma)}$. By the coding theorem, $2^{-K(n)} \geq 2^{-c} P_M(n)$ for a constant $c$. Let $N$ be the number of strings $\sigma$ of length $n$ with $K(\sigma) < n + K(n) - k$. Each contributes more than $2^{-n - K(n) + k}$ to $P_M(n)$, so $N\, 2^{-n - K(n) + k} < P_M(n) \leq 2^{c - K(n)}$, and $N < 2^{n - k + c}$.

Settled stages. If $\Omega - \Omega_s < 2^{-n}$ and $s \geq n$, then every string $\tau$ of length at most $n$ in the domain of $U$ satisfies $U(\tau)[s]\converge$: otherwise $\tau$ is not counted in $\Omega_s$, and $\Omega \geq \Omega_s + 2^{-|\tau|} \geq \Omega_s + 2^{-n}$. So the strings of length at most $n$ in the domain of $U$ are those that converge by stage $s$.

The domain of $U$ computes $\emptyset'$. Let $M$ be the prefix-free machine with $M(1^e 0) = 0^s$, where $s$ is the least stage with $\Phi_e(e)[s]\converge$, and $M$ undefined elsewhere. Let $d$ be such that $K \leq K_M + d$. If $\Phi_e(e)$ converges at stage $s$, then $K(0^s) \leq e + 1 + d$. With the domain of $U$ as an oracle, compute the outputs of the strings of length at most $e + 1 + d$ in the domain, and let $t$ be the largest number with $0^t$ among them ($t = 0$ if there is none). Then $\Phi_e(e)\converge$ if and only if $\Phi_e(e)[t]\converge$.

$\Omega$ is irrational. If $\Omega$ were rational, then, given $n$, the search for a stage $s \geq n$ with $\Omega - \Omega_s < 2^{-n}$ would be effective, since $\Omega$ and $\Omega_s$ are rationals, and it terminates since $\Omega_s$ tends to $\Omega$. By the first paragraph, the domain of $U$ would be computable, and so would be $\emptyset'$, which is not the case.

Prefixes of $\omega$. Let $q = 0.\omega_0 \cdots \omega_{n-1}$. Since $\Omega$ is irrational, $q < \Omega < q + 2^{-n}$. Search for $s \geq n$ with $\Omega_s > q$; it exists, and then $\Omega - \Omega_s < 2^{-n}$, so $s$ is settled for $n$. This procedure only uses $\omega \uh n$, which proves 2. In particular $\omega$ computes the domain of $U$, hence $\emptyset'$.

$\omega \leq_T \emptyset'$. For a dyadic rational $q$, $q < \Omega$ holds if and only if $\Omega_s > q$ for some $s$, a c.e. condition, so $\emptyset'$ decides it; and $q \neq \Omega$, since $\Omega$ is irrational. The prefix $\omega \uh k$ is the binary expansion of the largest $q = j 2^{-k}$ with $q < \Omega$, so $\emptyset'$ computes $\omega$. This proves 1.

Incompressibility. Let $N$ be the machine that, on input $\tau$, computes $\rho = U(\tau)$ and $n = |\rho|$, runs the procedure of 2 as if $\rho$ were $\omega \uh n$, obtaining a stage $s$ if the search terminates, lists the outputs of the strings of length at most $n$ that converge by stage $s$, and outputs the first string, in the length-lexicographic order, that is not in this list. The domain of $N$ is contained in that of $U$, so $N$ is prefix-free. If $U(\tau) = \omega \uh n$, the list contains every string $\sigma$ with $K(\sigma) \leq n$, by 2, so $N(\tau)$ has complexity larger than $n$. Let $c$ be such that $K \leq K_N + c$, and let $\tau$ be a shortest description of $\omega \uh n$. Then $n < K(N(\tau)) \leq |\tau| + c = K(\omega \uh n) + c$.