Lowness for randomness

1. With oracle $A$, the string $A \uh n$ is computed from $n$, so $K^A(A \uh n) \leq^+ K^A(n) \leq^+ K(n)$. If $A$ is low for K, then $K(A \uh n) \leq^+ K^A(A \uh n) \leq^+ K(n)$.
2. $\mathrm{MLR}^A \subseteq \mathrm{MLR}$ for every $A$, since a test without oracle is a test relative to $A$. Conversely, let $Z \in \mathrm{MLR}$, so that $K(Z \uh n) \geq n - c$. If $A$ is low for K, then $K^A(Z \uh n) \geq K(Z \uh n) - d \geq n - c - d$, and $Z \in \mathrm{MLR}^A$ by the relativized Levin–Schnorr theorem.
3. By the Kučera–Gács theorem (Kučera, Gács), some $Z \in \mathrm{MLR}$ computes $A$, and $\mathrm{MLR} = \mathrm{MLR}^A$.
4. If $B \leq_T A$ and $A$ is low for K, then $K \leq^+ K^A \leq^+ K^B$.

Let $Z \in \mathrm{MLR}^A$ and $\Phi$ a Turing functional with $\Phi^Z = A$. For a string $\eta$ and a string $\rho$, write $\Phi^\eta[s] \succeq \rho$ if $\Phi^\eta(i)[s]\converge = \rho(i)$ for every $i < |\rho|$.

The construction. Fix a parameter $d \in \nat$. For each triple $(\rho, \tau, x)$ with $U^\rho(\tau)\converge = x$ we enumerate a finite or infinite set of strings $C = C^\rho_{\tau, x}$, the hungry set of the triple, which aims at a measure $2^{-|\tau| - d}$. Each triple is first considered at the stage $s_0$ at which the computation $U^\rho(\tau)\converge = x$ is found. At each stage $s \geq s_0$, the triples considered so far are processed in turn. For the triple $(\rho, \tau, x)$, each string $\eta$ of length $s$ such that

1. $\Phi^\eta[s] \succeq \rho$,
2. $[\eta]$ is disjoint from the classes $[C']^{\prec}$ of all hungry sets $C'$, in their current state, and
3. $\lambda([C]^{\prec}) + 2^{-s} \leq 2^{-|\tau| - d}$,

is added to $C$, the strings being examined in lexicographic order. At the end of the processing of the triple, if $\lambda([C]^{\prec}) \geq 2^{-|\tau| - d - 1}$ and no request has yet been made for this triple, the request $(x, |\tau| + d + 1)$ is enumerated into a set $R_d$.

At stage $s$, every string in a hungry set has length at most $s$, so for $|\eta| = s$ the cylinder $[\eta]$ is either contained in or disjoint from each class $[C']^{\prec}$; condition 2 is decidable. By condition 2, the classes $[C]^{\prec}$ of distinct hungry sets are pairwise disjoint, and by condition 3, $\lambda([C^\rho_{\tau, x}]^{\prec}) \leq 2^{-|\tau| - d}$.

$R_d$ is a bounded request set. A request $(x, |\tau| + d + 1)$ is made for a triple only when its hungry set has measure at least $2^{-|\tau| - d - 1}$, the weight of the request. Since the hungry sets are disjoint, the total weight of $R_d$ is at most $\lambda\big(\bigcup [C^\rho_{\tau, x}]^{\prec}\big) \leq 1$.

A test relative to $A$. Let $\mathcal V_d$ be the union of the classes $[C^\rho_{\tau, x}]^{\prec}$ over the triples with $\rho \prec A$, for the construction with parameter $d$. It is $\Sigma^0_1(A)$, uniformly in $d$. For each $\tau \in \dom U^A$ there is exactly one triple $(\rho, \tau, x)$ with $\rho \prec A$, so

So $(\mathcal V_d)$ is a Martin-Löf test relative to $A$, and since $Z \in \mathrm{MLR}^A$, there is $d$ with $Z \notin \mathcal V_d$. Fix this $d$.

Every hungry set of a true computation becomes half full. Let $\rho \prec A$ with $U^\rho(\tau)\converge = x$, and suppose that the hungry set $C = C^\rho_{\tau, x}$ never reaches measure $2^{-|\tau| - d - 1}$. Since $\Phi^Z = A \succ \rho$, there is a stage $s$, after the triple is first considered, with $\Phi^{Z \uh s}[s] \succeq \rho$ and $2^{-s} \leq 2^{-|\tau| - d - 1}$. Let $\eta = Z \uh s$, and consider the processing of the triple at stage $s$. Condition 1 holds for $\eta$. If $[\eta]$ were contained in a hungry set $C' = C^{\rho'}_{\tau', x'}$, then some $\eta' \preceq \eta$ was added to $C'$, so $\Phi^{\eta'} \succeq \rho'$ and, since $\eta' \prec Z$, $\rho' \prec \Phi^Z = A$; then $Z \in [C']^{\prec} \subseteq \mathcal V_d$, a contradiction. So condition 2 holds. Condition 3 holds since $\lambda([C]^{\prec}) + 2^{-s} < 2^{-|\tau| - d - 1} + 2^{-|\tau| - d - 1}$. So $\eta$ is added to $C$, and $Z \in [C]^{\prec} \subseteq \mathcal V_d$, again a contradiction.

Conclusion. For every $\tau \in \dom U^A$ with $U^A(\tau) = x$, the triple with $\rho \prec A$ has its hungry set half full, and the request $(x, |\tau| + d + 1)$ belongs to $R_d$. By the KC theorem applied to the c.e. bounded request set $R_d$, $K(x) \leq |\tau| + d + O(1)$. Taking $\tau$ a shortest description of $x$ relative to $A$ gives $K(x) \leq^+ K^A(x)$.

By Proposition 3.2 (2) and (3), and Theorem 3.3.

(1 ⇔ 2) by Theorem 3.5 and Proposition 3.2 (1); the other equivalences by Corollary 3.4. Closure downward holds for low for K sets by Proposition 3.2 (4), and closure under join for K-trivial sets by Proposition 1.5.