Randomness and Turing degrees

The class $\{ X : Y \leq_T X \}$ is the union over $e$ of the classes $\mathcal C_e = \{ X : \Phi^X_e = Y \}$. Each $\mathcal C_e$ is Borel: $X \in \mathcal C_e$ if and only if for every $n$ there is a prefix $\tau$ of $X$ with $\Phi^\tau_e(n)\converge = Y(n)$. By subadditivity, it suffices to show that each $\mathcal C_e$ is null.

Suppose that $\lambda(\mathcal C_e) > 0$. By the density lemma (Lemma 1.6), there is a string $\sigma$ with $\lambda(\mathcal C_e \mid \sigma) > \frac12$. For $n \in \nat$ and $i \in \{0, 1\}$, let $\mathcal U_{n,i}$ be the open class generated by the strings $\tau \succeq \sigma$ with $\Phi^\tau_e(n)\converge = i$; these classes are uniformly $\Sigma^0_1$.

• $\mathcal C_e \cap [\sigma] \subseteq \mathcal U_{n, Y(n)}$, so $\lambda(\mathcal U_{n, Y(n)} \mid \sigma) > \frac12$.
• $\mathcal U_{n,0}$ and $\mathcal U_{n,1}$ are disjoint: a sequence in both would have prefixes $\tau, \tau'$ with $\Phi^\tau_e(n)\converge = 0$ and $\Phi^{\tau'}_e(n)\converge = 1$, and by monotonicity the longer of the two would give both outputs. So $\lambda(\mathcal U_{n, 1 - Y(n)} \mid \sigma) < \frac12$.

To compute $Y(n)$, enumerate $\mathcal U_{n,0}$ and $\mathcal U_{n,1}$ until the measure of the finite part of one of them inside $[\sigma]$ exceeds $2^{-|\sigma| - 1}$, and output the corresponding $i$. The search terminates by the first item, since the measure of $\mathcal U_{n, Y(n)} \cap [\sigma]$ is approached from below, and its output is $Y(n)$ by the second. This computes $Y$, a contradiction.

$\lambda(\mathcal B \mid \sigma)$ is the average of $\lambda(\mathcal B \mid \tau)$ over the $2^{k+1}$ strings $\tau \succeq \sigma$ of length $|\sigma| + k + 1$. If at most one of them had relative measure at least $2^{-k-1}$, this one being at most $1$ and the others less than $2^{-k-1}$, the average would be less than

a contradiction.

Let $\mathcal P = [T]$ with $T$ computable, and let $c$ be such that $\lambda(\mathcal P) \geq 2^{-c}$. Let $m_0 = 0$ and $m_{n+1} = m_n + c + n + 1$. For a string $\sigma$ of length $m_n$, let $A_n(\sigma)$ be the set of strings $\tau \succeq \sigma$ of length $m_{n+1}$ with $\lambda(\mathcal P \mid \tau) \geq 2^{-c-n-1}$. By Lemma 4.3 with $k = c + n$, if $\lambda(\mathcal P \mid \sigma) \geq 2^{-c-n}$, then $A_n(\sigma)$ has at least two elements.

Construction. Let $\sigma_0$ be the empty string; $\lambda(\mathcal P \mid \sigma_0) = \lambda(\mathcal P) \geq 2^{-c}$. Given $\sigma_n$ of length $m_n$ with $\lambda(\mathcal P \mid \sigma_n) \geq 2^{-c-n}$, let $\sigma_{n+1}$ be the leftmost element of $A_n(\sigma_n)$ if $X(n) = 0$, and the rightmost one if $X(n) = 1$, for the lexicographic order. It satisfies $\lambda(\mathcal P \mid \sigma_{n+1}) \geq 2^{-c-n-1}$. Let $Z = \bigcup_n \sigma_n$. Each $[\sigma_n]$ meets $\mathcal P$, since it has positive relative measure, so every prefix of $Z$ is extendible in $T$ and $Z \in \mathcal P$.

$Z \leq_T X \oplus \emptyset'$. By Proposition 1.3 (2) applied to the $\Pi^0_1$ class $\mathcal P \cap [\tau]$, the relative measure $\lambda(\mathcal P \mid \tau)$ is right-c.e., uniformly in $\tau$. So the condition $\lambda(\mathcal P \mid \tau) \geq q$, for a rational $q$, is $\Pi^0_1$: it fails if and only if some approximation from above falls below $q$. With $\emptyset'$, one computes $A_n(\sigma_n)$ from $\sigma_n$, and with $X$ one chooses $\sigma_{n+1}$.

$X \leq_T Z$. The sets $A_n(\sigma)$ are co-c.e. uniformly in $n$ and $\sigma$: there are finite sets $A_{n,s}(\sigma)$, computable from $n$, $\sigma$, $s$, decreasing in $s$, with intersection $A_n(\sigma)$. To compute $X(n)$, let $\sigma = Z \uh m_n = \sigma_n$ and $\tau = Z \uh m_{n+1} = \sigma_{n+1}$, and search for a stage $s$ at which $\tau$ is the leftmost or the rightmost element of $A_{n,s}(\sigma)$; output $0$ in the first case and $1$ in the second. Suppose $X(n) = 0$, so that $\tau$ is the leftmost element of $A_n(\sigma)$. The finitely many strings of length $m_{n+1}$ to the left of $\tau$ are not in $A_n(\sigma)$, so they leave $A_{n,s}(\sigma)$ at some stage, and $\tau$ becomes leftmost. On the other hand, $A_n(\sigma)$ has an element to the right of $\tau$, which belongs to every $A_{n,s}(\sigma)$, so $\tau$ is never the rightmost element. The search therefore returns $0$. The case $X(n) = 1$ is symmetric.

For the last statements, take for $\mathcal P$ the $\Pi^0_1$ class of random sequences of Corollary 2.5 (2), of measure at least $\frac12$. If $X \geq_T \emptyset'$, then $Z \leq_T X \oplus \emptyset' \equiv_T X$, so $Z \equiv_T X$.

($\Rightarrow$) Let $h \leq_T X$ be as in Theorem 3.4 of “Diagonally non-computable functions” (2): $h(e, m) \notin W_e$ whenever $|W_e| \leq m$. Since $K$ is approximable from above, the set of strings $\sigma$ with $K(\sigma) < n$ is c.e. uniformly in $n$, and by SMN there is a total computable function $a$ such that $W_{a(n)}$ is this set. It has fewer than $2^n$ elements, since distinct strings have distinct shortest descriptions, of length less than $n$. Let $f(n) = h(a(n), 2^n)$. Then $f \leq_T X$ and $f(n) \notin W_{a(n)}$, that is, $K(f(n)) \geq n$.

($\Leftarrow$) Let $f \leq_T X$ with $K(f(n)) \geq n$ for every $n$. The machine $M(\tau) = \Phi_{U(\tau)}(U(\tau))$ is prefix-free, since its domain is contained in that of $U$, and $M$ applied to a shortest description of $n$ gives $\Phi_n(n)$ when it converges. So there is a constant $d$ with

for every $n \geq 2$ with $\Phi_n(n)\converge$, by Proposition 3.4 of “Prefix-free complexity” (2). Let $n_0 \geq 2$ be such that $2 \log n + d' < n$ for $n \geq n_0$. For $n \geq n_0$ with $\Phi_n(n)\converge$, $K(\Phi_n(n)) < n \leq K(f(n))$, so $f(n) \neq \Phi_n(n)$. Modify $f$ on the finitely many $n < n_0$, setting $g(n) = \Phi_n(n) + 1$ if $\Phi_n(n)\converge$ and $g(n) = 0$ otherwise, and $g(n) = f(n)$ for $n \geq n_0$. The function $g$ is $X$-computable, as a finite modification of $f$, and DNC.

Let $Z$ be random. By Theorem 3.1, there is $c$ with $K(Z \uh m) \geq m - c$ for every $m$. The function $f(n) = Z \uh (n + c)$ is $Z$-computable and satisfies $K(f(n)) \geq n$, so $Z$ computes a DNC function by Theorem 4.5. The class MLR is conull (Corollary 2.5). A 1-generic set computes no DNC function, by a theorem of Demuth and Kučera proved in the course on Cohen genericity (Demuth, Kučera); hence it computes no random sequence.