The Arithmetical Complexity of Dimension and Randomness

Simple item page
dc.creatorHitchcock, John M.
dc.creatorLutz, Jack H.
dc.creatorTerwijn, Sebastiaan A.
dc.date2004-08-18
dc.date.accessioned2026-07-07T03:21:41Z
dc.date.available2026-07-07T03:21:41Z
dc.descriptionConstructive 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.
dc.description20 pages
dc.identifierhttps://arxiv.org/abs/cs/0408043
dc.identifierhttp://arxiv.org/abs/cs/0408043
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32299
dc.subjectLogic in Computer Science
dc.subjectComputational Complexity
dc.titleThe Arithmetical Complexity of Dimension and Randomness
dc.typetext

Files

Collections

arXiv