658 13. Algorithmic Dimension

for arbitrary computable measures, as we did for Martin-L¨of randomness in Section 6.12.

Theorem 13.15.7 (Downey, Merkle, and Reimann [125]).

(i) Let S be Schnorr random and let Z be a computable, infinite, coinfinite set such that δZ = limn exists. Let SZ = S Z , where Z is as defined in Section 6.9. Then dimS(SZ ) = δZ .

(ii)Let p = (p0, p1, . . . ) be a sequence of uniformly computable reals in (0, 1) such that p = limn pn exists. Then for any Schnorr μp-random set B, we have dimS(B) = −(p log p + (1 − p) log(1 − p)).

Part 1 of the theorem is straightforward (using for instance the martingale characterization of Schnorr Hausdor dimension); part 2 is an easy adaption of the corresponding theorem for e ective dimension (as for example in Section 13.5). Lutz [254] proved part 2 for Martin-L¨of μp-randomness and e ective Hausdor dimension.

It is not hard to see that for the examples given in Theorem 13.15.7, the Schnorr Hausdor dimension and the Schnorr packing dimension coincide, so these examples describe Schnorr regular sets. In Section 13.15.4, we will see that there are highly irregular c.e. sets: While all c.e. sets have Schnorr Hausdor dimension 0, there are c.e. sets of Schnorr packing dimension 1.

Downey and Kach [unpublished] have noted that the method in the proof of Theorem 8.11.2 can be used to show that if a set is nonhigh, then its Schnorr Hausdor dimension equals its e ective Hausdor dimension. We will see in Section 13.15.4 that this correspondence fails for packing dimension.

13.15.3 A machine characterization of Schnorr dimension

One of the fundamental aspects of the theory of 1-randomness is the characterization of that notion in terms of initial segment Kolmogorov complexity. There is an equally important correspondence between e ective Hausdor and packing dimensions and Kolmogorov complexity, as we saw in Theorem 13.3.4 and Corollary 13.11.12. A comparably elegant initial segment complexity characterization is not possible for Schnorr randomness, because such a characterization should be relativizable, and would therefore imply that lowness for K implies lowness for Schnorr randomness, which we saw was not the case in Section 12.1.

As we saw in Section 7.1.3, however, it is possible to obtain a machine characterization of Schnorr randomness by restricting ourselves to computable measure machines, that is, prefix-free machines whose domains have computable measures. We now see that we can use such machines to characterize Schnorr dimension as well.

Recall from Theorem 7.1.15 that Downey and Gri ths [109] showed that A is Schnorr random iff KM (A n) n − O(1) for every computable

measure machine M . Building on this characterization, we can describe Schnorr dimension as asymptotic initial segment complexity with respect to computable measure machines.

Theorem 13.15.8 (Downey, Merkle, and Reimann [125]). The Schnorr Hausdor dimension of A is the infimum over all computable measure

Let {Ui}i ω be a Schnorr s-test covering A. The KC Theorem is applica-

We claim that SM is a total Solovay s-test covering A. There are infinitely

since for any σ SM \ SMs , we have 2−s|σ| < 2−KM (σ), and any minimal length M -description of σ must be in dom(M ) \dom(Ms), whence the sum of 2 over all such σ is bounded by μ( dom(M ) \ dom(Ms) ) < ε.

An analogous argument, using the correspondence between martingales and tests shown in Theorem 13.15.6, allows us to obtain a machine characterization of Schnorr packing dimension.

Theorem 13.15.9 (Downey, Merkle, and Reimann [125]). The Schnorr packing dimension of A is the infimum over all computable measure

13.15.4 Schnorr dimension and computable enumerability

For left-c.e. reals, having high e ective dimension has similar computabilitytheoretic consequences to being 1-random. For instance, as we have seen,

660 13. Algorithmic Dimension

every left-c.e. real of positive e ective dimension is Turing complete. For Schnorr dimension, a straightforward generalization of Corollary 8.11.4 shows that if A is left-c.e. and dimS(A) > 0, then A is high.

Computably enumerable sets are usually of marginal interest in the context of algorithmic randomness, one reason being that they cannot be random relative to most notions of randomness. For instance, we have the following.

Proposition 13.15.10 (Folklore). No c.e. set is Schnorr random.

Proof. Let A be c.e. We may assume that A is infinite, and hence contains an infinite computable subset {b0 < b1 < · · · }. Let Gn = {σ 2bn : i <

This proof does not immediately extend to showing that a c.e. set A must have Schnorr Hausdor dimension 0. Defining coverings from the enumeration of A directly might not work either, since the dimension factor leads longer strings to be weighted more, so, depending on the enumeration, we might not get a Schnorr s-covering. However, we can exploit the somewhat predictable nature of A to define for each s > 0 a computable martingale that s-succeeds on A.

Theorem 13.15.11 (Downey, Merkle, and Reimann [125]). Every c.e. set has Schnorr Hausdor dimension 0.

Proof. Let s Q>0. Let γ > 21−s − 1 be rational. Partition N into consecutive disjoint intervals I0, I1, . . . so that there is an ε > 0 for which, letting in = |In| and jn = i0 + i1 + · · · + in, we have

To have this hold, it is enough to have In be much larger than In−1, for example by letting |In| = 2|I0|+···+|In−1|.

d(σ0) = d(σ1) = d(σ). If |σ| Ik, then wait for an s such that |As ∩ Ink | > qink . If |σ| As, then let d(σ0) = 0 and d(σ1) = 2d(σ). Otherwise, let

d(σ0) = (1 + γ)d(σ) and d(σ1) = (1 − γ)d(σ).