- •13.4 Shift complex sets
- •13.5 Partial randomness
- •13.9.1 Dimension in h-spaces
- •13.10 C-independence and Zimand’s Theorem
- •13.11 Other notions of dimension
- •13.11.1 Box counting dimension
- •13.11.3 Packing dimension
- •13.12 Packing dimension and complexity extraction
- •13.13 Clumpy trees and minimal degrees
- •13.14 Building sets of high packing dimension
- •13.15 Computable dimension and Schnorr dimension
- •13.15.1 Basics
- •13.15.2 Examples of Schnorr dimension
- •13.15.3 A machine characterization of Schnorr dimension
- •13.15.4 Schnorr dimension and computable enumerability
- •13.16 Kolmogorov complexity and the dimensions of individual strings
654 13. Algorithmic Dimension
13.15Computable dimension and Schnorr dimension
13.15.1 Basics
It is natural to consider notions of dimension obtained by replacing c.e. gales by computable ones. Recall that a martingale d s-succeeds on A if
d(A n)
lim supn 2(1−s)n = ∞ and s-succeeds strongly on A if limn 2(1−s)n = ∞. As discussed in Section 13.3, the following definitions were in a sense implicit
in the work of Schnorr [349].
Definition 13.15.1 (Lutz [252, 254], Athreya, Hitchcock, Lutz, and Mayordomo [15]). The computable Hausdor dimension of C 2ω is
dimcomp(C) = inf{s : there is a computable martingale that s-succeeds on all A C}.
The computable packing dimension of C 2ω is
Dimcomp(C) = inf{s : there is a computable martingale that s-succeeds strongly on all A C}.
For A 2ω, we write dimcomp(A) for dimcomp({A}) and refer to it as the computable Hausdor dimension of A, and similarly for packing dimension.
A di erent approach to passing from Σ01 objects to computable ones in the definition of algorithmic dimension is to consider test sets that are computable in the sense of Schnorr.
Definition 13.15.2. Let s 0 be rational.
A Schnorr s-test is a uniformly c.e. sequence {Sn}n ω of sets of strings
such that σ Sn 2−s|σ| 2−n for all n and the reals |
σ Sn 2−s|σ| are |
||||
uniformly computable. |
|
|
|
||
|
ω |
|
|
|
|
A class C 2 |
|
is Schnorr s-null if there exists a Schnorr s-test {Sn}n ω |
|||
such that C |
n Sn . |
|
|
|
|
The Schnorr 1-null sets are just the Schnorr null sets. As with Schnorr |
|||||
|
|
|
|
|
2−s|σ| = 2−n and |
tests, in the above definition we could require that |
σ Sn |
||||
have the same notion of Schnorr s-null sets. The sets S |
n in a Schnorr s-test |
||||
|
|
|
|
are actually uniformly computable, since to determine whether σ Sn it
su ces to enumerate Sn until the accumulated sum given by |
τ Sn 2−s|τ | |
||||||
exceeds 2 |
− |
n |
− |
2s σ |
| |
(assuming the measure of the nth level of the test is |
|
|
|
| |
|
|
in fact 2−n). If σ has not been enumerated so far, it cannot be in Sn. But of course the converse does not hold: there are computable sets of strings generating open sets with noncomputable measures. Indeed, we have mentioned before that every Σ01 class can be generated by a computable set of strings.
13.15. Computable dimension and Schnorr dimension |
655 |
We can adapt Definition 13.5.6 to get an s-analog of the concept of total
Solovay test introduced in Definition 7.1.9. A Solovay s-test D is total if
σ D 2 is computable.
As we saw in Section 13.5, the correspondence between tests for s-Martin- L¨of randomness and Solovay s-tests is close but not quite exact. In the Schnorr case, however, we do get an exact correspondence.
Theorem 13.15.3 (Downey, Merkle, and Reimann [125]). For any rational s 0, a class C 2ω is Schnorr s-null if and only if there is a total Solovay s-test that covers every element of C.
Proof. Let {Sn}n ω be a Schnorr s-test. Let S = |
|
n Sn. Clearly, S is |
|||||||||||||||||||||||||||||
a Solovay s-test that covers all of |
|
|
S |
|
, so it is enough to show that |
||||||||||||||||||||||||||
|
|
|
|
2 |
|
s σ |
|
|
|
|
|
|
n |
|
|
n |
|
|
|
|
|
|
|
|
|
|
|||||
|
σ S |
− | | |
is computable. It is easy to see that to compute this sum to |
||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
within 2 |
− |
n |
, it is enough to compute |
σ |
|
|
Si |
s σ |
| to within 2− |
2n |
− |
3 |
for each |
||||||||||||||||||
|
|
|
|
|
|
|
|
2− | |
|
|
|||||||||||||||||||||
i n + 1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
For the converse, let S be a total Solovay s-test Given n, compute c = |
||||||||||||||||||||||||||||||
|
|
|
|
|
|
s σ |
|
|
|
n |
2 |
ectively find a finite F |
|
S such that |
|||||||||||||||||
σ S 2− | |
|
|
| |
to within 2−n |
−1 |
. E |
s σ |
| c − 2− |
n |
2 |
. |
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
c − 2− − |
|
2− | |
|
|
− |
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
σ F |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Let S |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
n |
= S |
\ |
F . Then S |
n |
covers every set that S covers, and |
σ Sn |
2−s|σ| < |
||||||||||||||||||||||||
2 |
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
− |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sn form a Schnorr s-test whose intersection contains all sets covered by
S.
We have the following e ective version of Theorem 13.1.2.
Proposition 13.15.4 (Downey, Merkle, and Reimann [125]). For any rationals t s 0, if C is Schnorr s-null then it is also Schnorr t-null.
Proof. It su ces to show that if s t, then every Schnorr s-test is also a Schnorr t-test. Obviously, the only issue is checking the computability of the relevant sum.
Let {Sn}n ω be a Schnorr s-test. Given any rational r 0 and any n and k, let
|
mn(r) = |
|
σ Sn |
2−r|σ| |
|
||||
and |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
mnk (r) = |
|
|
|
2−r|σ|. |
|
||||
|
|
|
σ Sn∩2 k |
|
|
||||
|
|
|
|
|
|
|
|
||
It is easy to check that mk |
(t) |
|
m |
(t) |
|
mk |
(t) + 2(s−t)km |
(s). |
|
n |
|
n |
|
|
n |
n |
|
Now, mn(s) is computable, and 2(s−t)k goes to zero as k gets larger. Therefore, we can e ectively approximate mn(t) to any desired degree of precision.
656 13. Algorithmic Dimension
Thus the following definition makes sense.
Definition 13.15.5 (Downey, Merkle, and Reimann [125]). The Schnorr Hausdor dimension of C 2ω is
dimS(C) = inf{s 0 : C is Schnorr s-null}.
For A 2ω, we write dimS(A) for dimS({A}) and refer to it as the Schnorr Hausdor dimension of A.
Note that the Schnorr Hausdor dimension of any class is at most 1, since for any ε > 0 we can choose a computable sequence k0, k1, . . . such that the sets 2kn form a Schnorr 1 + ε test covering all of 2ω.
We saw in Section 8.11.2 that the concepts of computable randomness and Schnorr randomness do not coincide. That is, there are Schnorr random sets on which some computable martingale succeeds. However, the di erences vanish when it comes to Hausdor dimension.
Theorem 13.15.6 (Downey, Merkle, and Reimann [125]). For any B 2ω, we have dimS(B) = dimcomp(B).
Proof. ( ) Suppose that a computable martingale d s-succeeds on B. By Theorem 7.1.2, we may assume that d is rational-valued. We may also assume that s < 1, since the case s = 1 is trivial. It su ces to show that for any t (s, 1), we can find a Schnorr t-test that covers B. Fix such a t.
Let
Uk = {σ : 2−(1−t)|σ|d(σ) 2k}.
It is easy to see that the {Uk}k ω are uniformly computable (since d is rational-valued and computable) and cover B, so we are left with showing
that the reals σ Uk |
2−s|σ| are uniformly computable. |
|
||||||
To approximate |
|
|
s σ |
r |
|
|
|
|
σ Uk |
2− | | to within 2− , we first e ectively find an |
|||||||
|
||||||||
n |
|
r |
d(λ). Let V |
= Uk ∩ 2 |
n |
. If τ |
Uk \ V then |
|
n such that 2(1−t) 2 |
|
|
d(τ ) 2(1−t)n2k 2r+kd(λ). So by Kolmogorov’s Inequality (Theorem 6.3.3), μ(Uk) − μ(V ) 2−(r+k).
( ) Suppose dimS(B) < s < 1. (Again the case s = 1 is trivial.) We show that there is a computable martingale d that s-succeeds on B.
Let {Vk}k ω be a Schnorr s-test that covers B. Let |
|
|
|
2(1−s)|τ | |
if τ σ for some τ |
|
Vk |
dk(σ) = στ Vk 2−|τ |+(1−s)(|σ|+|τ |) |
otherwise. |
|
|
13.15. Computable dimension and Schnorr dimension |
657 |
We verify that dk is a martingale. Given σ, if there is a τ Vk such that τ σ, then clearly dk(σ0) + dk(σ1) = 2dk(σ). Otherwise,
dk(σ0) + dk(σ1)
= 2−|τ |+(1−s)(|σ|+|τ |+1) + 2−|τ |+(1−s)(|σ|+|τ |+1)
σ0τ Vk |
|
|
|
σ1τ Vk |
|
|
|
|
|
|
|
= |
2(−|ρ|+1)+(1−s)(|σ|+|ρ|) = 2dk(σ). |
||||
|
|
|
|
σρ Vk |
|
|
|
|
Furthermore, dk(λ) = |
|
τ Vk 2−|τ |+(1−s)|τ | = |
τ Vk 2−s|τ | 2−k, so d = |
|||||
k dk is also a |
martingale. It is straightforward to use the fact that |
{ |
V |
|||||
|
|
|
|
|
|
k}k ω |
is a Schnorr s-test to show that the dk are uniformly computable, and hence d is computable.
Finally, note that, for σ Vk, we have d(σ) dk(σ) = 2(1−s)|σ|, so if B k Vk , then d(B n) 2(1−s)n infinitely often, which means that d s-succeeds on B.
Thus, in contrast to randomness, the approaches to dimension via Schnorr tests and via computable martingales yield the same concept. Because of the potential confusion between the terms “e ective dimension” (which we have used to mean our primary notion of Σ01 dimension) and “computable dimension”, we will use the term “Schnorr Hausdor dimension” and the notation dimS. For uniformity, we will also refer to computable packing dimension as Schnorr packing dimension and use the notation DimS in place of Dimcomp.
It follows from the definitions that dimS(A) DimS(A) for any A. We call sets for which Schnorr Hausdor and Schnorr packing dimension coincide Schnorr regular , following [391] and [15]. It is easy to construct a nonSchnorr regular sequence; in Section 13.15.4, we will see that such sequences occur even among the c.e. sets.
13.15.2 Examples of Schnorr dimension
The easiest way to construct examples of sequences of non-integral Schnorr Hausdor dimension is by inserting zeroes into a sequence of Schnorr Hausdor dimension 1. Note that it easily follows from the definitions that every Schnorr random set has Schnorr Hausdor dimension 1. On the other hand, it is not hard to show that not every set of Schnorr Hausdor dimension 1 is Schnorr random.
A second class of examples is based on the fact that Schnorr random sets satisfy the law of large numbers, not only with respect to the uniform measure, but also with respect to other computable Bernoulli distributions. For a sequence p = (p0, p1, . . . ) of elements of (0, 1), the Bernoulli measure μp
|
σ(i)=0(1 − pi). It is straightforward to |
is defined by μp( σ ) = σ(i)=1 pi |
|
Schnorr test to obtain Schnorr randomness notions |
|
modify the definition of |
|