KL-randomness and effective dimension under strong reducibility

Computability theory is concerned with the relative computability of reals, and of collections of reals. The latter can be compared by various means, including Medvedev and Muchnik reducibility. Among the central collections considered are those of completions of Peano Arithmetic, Turing complete reals, Cohen generic reals, random reals, and various weakenings of randomness such as reals of positive effective Hausdorff dimension.

Perhaps the most famous open problem in algorithmic randomness [2, 9] is whether Kolmogorov–Loveland randomness is equal to Martin-Löf randomness. Here we show that at least they are Medvedev equivalent.

Randomness extraction in computability theory concerns whether reals that are close (in some metric) to randoms can compute random reals. A recent example is [4]. That paper does for Hausdorff dimension what was done for a notion intermediate between packing dimension and Hausdorff dimension in [3]. That intermediate notion, complex packing dimension, has a natural dual which we introduce in this article. Whereas our result on KL-randomness is positive, we establish some negative (non-reduction) results for our new inescapable dimension and for relativized complex packing dimension (in particular Theorem 3.11). These results are summarized in Figure 1.

Let CR, SR, KLR, and MLR be the classes of computably random, Schnorr random, Kolmogorov-Loveland random, and Martin-Löf random reals, respectively. For basic definitions from algorithmic randoness, the reader may consult two recent monographs [2, 9]. Let $\leq_{s}$ denote the uniform (strong) reducibility of mass problems known as Medvedev reducibility, and let $\leq_{w}$ denote the non-uniform (weak) version known as Muchnik reducibility. It was shown by Nies, Stephan and Terwijn [10] that $\mathrm{CR}\leq_{w}\mathrm{SR}$. Miyabe [8] obtains an interesting counterpoint by showing as his main theorem that $\mathrm{CR}\not\leq_{s}\mathrm{SR}$.

As a corollary, $\mathrm{MLR}\leq_{w}\mathrm{KLR}$. Miyabe [8] posed one open problem — is $\mathrm{MLR}\leq_{s}\mathrm{KLR}$? — which we answer in Theorem 1.2.

Let $K(\sigma)$ denote the prefix-free Kolmogorov complexity of a string $\sigma\in 2^{<\omega}$, and let $K_{s}(\sigma)$ be a computable nonincreasing approximation of $K(\sigma)$ in stages $s\in\omega$. The prefix of $A$ of length $n$ is denoted $A\upharpoonright n$.

Inspection of the proof of Theorem 1.2 shows that we do not need the full power of Turing reductions, but have a truth-table reduction with use $\varphi(n)\leq 2n$.

Let $K(\sigma)$ denote the prefix-free Kolmogorov complexity of a string $\sigma\in 2^{<\omega}$. The prefix of $A$ of length $n$ is denoted $A\upharpoonright n$.

Viewed in terms of complexity [1, 6], the Hausdorff and packing dimensions are dual to one another:

Another notion of dimension was defined in previous work by Kjos-Hanssen and Freer [3], which we review here. Let $\mathfrak{D}$ denote the collection of all infinite $\Delta^{0}_{1}$ elements of $2^{\omega}$. The complex packing dimension is defined as

This is the inescapable dimension of $A$, so named because if $\dim_{i}(A)=\alpha$, every infinite computable collection of prefixes of $A$ must contain prefixes with relative complexity arbitrarily close to $\alpha$. For such a real, there is no (computable) escape from high complexity prefixes.

As Freer and Kjos-Hanssen show in [3], for any $A\in 2^{\omega}$,

The expected analogous result also holds:

Unexpectedly, this is the best one can do. As we will see in the next section, while the Hausdorff dimension of a real is always lower than its packing dimension, any permutation is possible for the complex packing and inescapable dimensions of a real.

We begin with a proof that the inescapable and complex packing dimensions are incomparable in the following sense: $\dim_{cp}(A)\leq\dim_{cp}(B)$ does not imply $\dim_{i}(A)\leq\dim_{i}(B)$, nor vice versa. In fact we show a stronger statement:

Recall that a real $A$ meets a set of strings $S$ if there is some $\sigma\in S$ such that $\sigma$ is a prefix of $A$. Moreover, $A$ is weakly 2-generic if for each dense $\Sigma^{0}_{2}$ set of strings $S$, $A$ meets $S$ [5].

For a real $A$, let us write $A[m,n]$ to denote the string $A(m)A(m+1)\dots A(n-1)$. For two functions $f(n),g(n)$ we write $f(n)\leq^{+}g(n)$ to denote $\exists c\forall n\,f(n)\leq g(n)+c$. We write $f(n)=\mathcal{O}(g(n))$ to denote $\exists M\exists n_{0}\forall n>n_{0}\,f(n)\leq Mg(n)$. It will also be useful to have the following theorem of Schnorr at our disposal:

Finally, for a real $A$ and $n\in\omega$ we use the indicator function $1_{A}$ defined by

We say that $A$ is finite-to-one reducible to $B$ if there is a total computable function $f:\omega\to\omega$ such that the preimage of each $n\in\omega$ is finite and for all $n$, $n\in A\iff f(n)\in B$.

Notice that for any oracle $X$, the classes of infinite sets that are $\Delta^{0}_{n}(X),\Sigma^{0}_{n}(X)$ or $\Pi^{0}_{n}(X)$ are downward closed under finite-to-one reducibility, and so give rise to notions of dimension of this form. We will label these $\mathfrak{D}_{n}(X)$, $\mathfrak{S}_{n}(X)$, and $\mathfrak{P}_{n}(X)$ respectively, leaving off $X$ when $X$ is computable. Interestingly, for fixed $n$, the first two give the same notion of dimension.

By a similar analysis, the analogous result for $si$ dimensions is also true.

What about the $\Pi^{0}_{n}$ dimensions? Unlike the $\Sigma^{0}_{1}$ case, these do not collapse to any other dimension. Two lemmas will be useful in proving this. The first (which was implicit in Claims 1 and 2 of Theorem 2.1) will allow us to show that an $si$-dimension of a real is high by demonstrating a sequence that witnesses this. The second is a generalization of the segment technique, forcing a dimension to be $0$ by alternating $0$- and $R$-segments in a more intricate way, according to the prescriptions of a certain real. The constructions below proceed by selecting a real that will guarantee that one dimension is 0 while leaving room to find a witnessing sequence for another.

Recall that an infinite real $A$ is said to be immune to a class $\mathfrak{B}$ if there is no infinite member $B\in\mathfrak{B}$ such that $B\subseteq A$ as sets, or co-immune to a class $\mathfrak{B}$ if its complement is immune to $\mathfrak{B}$. We will sometimes refer to these properties as $\mathfrak{B}$-immunity or $\mathfrak{B}$-co-immunity, respectively.

Again, we will give a detailed proof of only the $\dim_{si\mathfrak{B}}$ result (though the necessary changes for $\dim_{is\mathfrak{B}}$ are detailed below). Unpacking the definition of $B$,

$B$ is here built out of segments of the form $B\left[s_{k_{n}},s_{k_{n}+2}\right]$ for odd $k$. Here a segment is a $0$-segment if $k_{n}\not\in X$, or an $A$-segment if $k_{n}\in X$, which by definition is a prefix of $A$. These segments are now placed in a more intricate order according to $X$, with a value $n$ being contained in a $0$-segment if $X(k_{n})=0$, and in an $A$-segment if $X(k_{n})=1$. With some care, this will allow us to leverage the $\mathfrak{B}$-immunity of $X_{0}$ to perform the desired complexity calculations.

Specifically, we want to show that for any $N\in\mathfrak{B}$, $\inf_{N}K(B\upharpoonright n)/n=0$. It is tempting to place the segments according to $X_{0}$ and invoke its $\mathfrak{B}$-immunity to show that for any $N\in\mathfrak{B}$, there are infinitely many $n\in N$ such that $n$ is in a $0$-segment, and argue that complexity will be low there. The problem is that we have no control over where in the $0$-segment $n$ falls. Consider in this case the start of any segment following an $A$-segment: $n=s_{k_{n}}$ for $k_{n}-1\in X_{0}$ and $k_{n}\in X_{0}$. We can break $A$ and $B$ into sections to compute

Even if $n$ is the start of a $0$-segment, if $K(A\upharpoonright n)$ is high, $K(B\upharpoonright n)$ may not be as low as needed for the proof. Our definition of $X$ avoids this problem:

With these lemmas in hand, we are ready to prove the following theorem:

The proof of analogous result for the $is$-dimensions is similar, using the same $S_{0}$ and $S$, and the real defined by $B(n)=R\left(n-2^{k_{n}^{2}}\right)\cdot 1_{\overline{S}}(k_{n})$.

It remains to show that the $\Delta^{0}_{n+1}$ and $\Pi^{0}_{n}$ dimensions are all distinct. We can use the above lemmas for this, so the only difficulty is finding sets of the appropriate arithmetic complexity with the relevant immunity properties.

Again, the analogous result for $is$-dimensions is similar:

After asking questions about the arithmetic hierarchy, it is natural to turn our attention to the Turing degrees. As the familiar notion of $B$-immunity for an oracle is exactly $\Delta^{0}_{1}(B)$-immunity for a class, we have access to the usual lemmas. We shall embed the Turing degrees into the $si$-$\Delta^{0}_{1}(A)$ dimensions (and dually, $is$-$\Delta^{0}_{1}(A)$). First, a helpful lemma:

The result for $is$-dimensions is again similar:

We can push this a little further by considering weak truth table reductions: