K-trivial sets

1. This is Proposition 3.6 of “Prefix-free complexity”.
2. Exchanging $0$ and $1$ is a computable map sending $A \uh n$ to $\overline{A} \uh n$. If $B$ is a finite variant of $A$, then $B \uh n = h(A \uh n)$, where $h$ modifies the finitely many positions at which $A$ and $B$ differ. In both cases a computable function is applied, which increases $K$ by at most a constant.

Let $M$ be the prefix-free machine $\tau \mapsto |U(\tau)|$, with the same domain as $U$. By the coding theorem (Coding theorem; Levin, Chaitin), there is $c$ with $P_M(n) < 2^{c - K(n)}$ for every $n$; enlarging $c$ makes the inequality strict. Let $N$ be the number of strings $\sigma$ of length $n$ with $K(\sigma) \leq K(n) + b$. A shortest description of each of them is a description of $n$ for $M$, of length at most $K(n) + b$, and these descriptions are distinct. So $N\, 2^{-K(n) - b} \leq P_M(n) < 2^{c - K(n)}$, and $N < 2^{b + c}$.

If $A_0, \dots, A_{N-1}$ are distinct sets that are K-trivial with constant $b$, their prefixes of some length $n$ are pairwise distinct, and they are $N$ strings of length $n$ with $K(\sigma) \leq K(n) + b$. So $N < 2^{b+c}$.

The function $K$ is computable in $\emptyset'$, since $K(\sigma) \leq k$ is a $\Sigma^0_1$ property of $(\sigma, k)$. So the set $T_b$ of strings $\sigma$ with $K(\sigma \uh m) \leq K(m) + b$ for every $m \leq |\sigma|$ is a tree computable in $\emptyset'$, and its paths are the sets that are K-trivial with constant $b$. The class $[T_b]$ is finite, so each of its members is isolated. By Proposition 2.3 of “Computable members” relativized to $\emptyset'$, each member of $[T_b]$ is computable in $\emptyset'$.

Let $b$ be a common constant for $A$ and $B$, $c$ as in Theorem 1.3, and $k = b + c$. For a string $\tau$ in the domain of $U$ with $U(\tau) = n$, let $S_\tau$ be the set of strings $\sigma$ of length $n$ with $K(\sigma) \leq |\tau| + b$, listed in the order in which they are found by a fixed enumeration; this list is c.e. uniformly in $\tau$. If $\tau$ is a shortest description of $n$, then $|S_\tau| < 2^k$, and $A \uh n$ and $B \uh n$ belong to $S_\tau$.

Let $M$ be the machine that, on input $\tau \beta \gamma$ with $\tau$ in the domain of $U$ and $|\beta| = |\gamma| = k$, reads $\beta$ and $\gamma$ as numbers $i, j < 2^k$, waits for the $i$-th and $j$-th elements $\sigma, \sigma'$ of the list $S_\tau$, and outputs the interleaving $\sigma \oplus \sigma'$ of length $2n$. Its domain is prefix-free, by the argument of Proposition 3.4 of “Prefix-free complexity” (1). With $\tau$ a shortest description of $n$, and $\beta, \gamma$ the positions of $A \uh n$ and $B \uh n$ in the list, $M(\tau\beta\gamma) = (A \oplus B) \uh 2n$. Hence

For an arbitrary length $m$, let $n = \lceil m/2 \rceil$. The string $(A \oplus B) \uh m$ is $(A \oplus B) \uh 2n$ if $m$ is even, and this string with its last bit removed if $m$ is odd; both operations are computable and do not require knowing $m$, so $K((A \oplus B) \uh m) \leq^+ K((A \oplus B) \uh 2n)$. Since $n$ is computed from $m$, $K(n) \leq^+ K(m)$. So $K((A \oplus B) \uh m) \leq^+ K(m)$.

The function $g$ is computable, since it is decidable whether $U(\tau)$ converges for the first time at stage $t$ with output $n$.

$K \leq^+ g$. In the second case, let $\ell = \lfloor \log(m+1) \rfloor$ be the length of the string associated with $m$. By Proposition 3.4 of “Prefix-free complexity” (2), $K(m) \leq^+ \ell + 2 \log \ell \leq^+ 2\ell + 2 = g(m)$. In the first case, let $M$ be the machine that, on input $\tau$, waits for the least stage $t$ with $U(\tau)[t]\converge$ and outputs $\langle \tau, U(\tau), t \rangle$. It has the domain of $U$, so it is prefix-free, and $K(m) \leq^+ |\tau| = g(m)$.

$g \leq^+ K$ infinitely often. Let $\tau$ be a shortest description of $n$, $t$ its stage of convergence and $m = \langle \tau, n, t \rangle$. Then $g(m) = |\tau| = K(n)$, and $K(n) \leq^+ K(m)$ since $n$ is computed from $m$. There is one such $m$ for each $n$, so infinitely many.

($\Rightarrow$) $K(A \uh m) \leq^+ K(m) \leq^+ g(m)$.

($\Leftarrow$) Let $c$ be such that $K(A \uh m) \leq g(m) + c$ for every $m$. Given $n$, let $\tau$ be a shortest description of $n$, $t$ its stage of convergence, and $m = \langle \tau, n, t \rangle \geq n$. Then $K(A \uh m) \leq g(m) + c = K(n) + c$. The string $A \uh n$ is computed from $A \uh m$ by truncation to the length $n$, and $n$ is computed from $m$; so $K(A \uh n) \leq^+ K(A \uh m) \leq^+ K(n)$, with a constant independent of $n$.