Abstract:
Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^α and DIMstr^α be the classes of all sequences of dimension α and of strong dimension α, respectively. We show that DIM⁰ is properly Π⁰₂, and that for all Δ⁰₂-computable α ∈ (0,1], DIM^α is properly Π⁰₃.

To classify the strong dimension classes, we use a more powerful effective Borel hierarchy where a co-enumerable predicate is used rather than a enumerable predicate in the definition of the Σ⁰₁ level. For all Δ⁰₂-computable α ∈ [0,1), we show that DIMstr^α is properly in the Π⁰₃ level of this hierarchy. We show that DIMstr¹ is properly in the Π⁰₂ level of this hierarchy.

We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Π⁰₃.

Journal Version:

• ACM Transactions on Computational Logic, 8(2), article 13, 2007.
  [DOI link | PostScript | PDF]

Preliminary Versions:

• Technical Report cs.LO/0408043, Computing Research Repository, 2004.
  Technical Report TR04-079, Electronic Colloquium on Computational Complexity, 2004.
  

• Proceedings of the Annual Conference of the European Association for Computer Science Logic (Vienna, Austria, August 25-30, 2003), Lecture Notes in Computer Science 2803, pages 241-254. Springer-Verlag, 2003.
  [Publisher's Page]