Computer Science – Logic in Computer Science
Scientific paper
2004-08-18
Computer Science
Logic in Computer Science
20 pages
Scientific paper
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^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong dimension alpha, respectively. We show that DIM^0 is properly Pi^0_2, and that for all Delta^0_2-computable alpha in (0,1], DIM^alpha is properly Pi^0_3. 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 Sigma^0_1 level. For all Delta^0_2-computable alpha in [0,1), we show that DIMstr^alpha is properly in the Pi^0_3 level of this hierarchy. We show that DIMstr^1 is properly in the Pi^0_2 level of this hierarchy. We also prove that the class of Schnorr random sequences and the class of computably random sequences are properly Pi^0_3.
Hitchcock John M.
Lutz Jack H.
Terwijn Sebastiaan A.
No associations
LandOfFree
The Arithmetical Complexity of Dimension and Randomness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Arithmetical Complexity of Dimension and Randomness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Arithmetical Complexity of Dimension and Randomness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-595495